• Questions
  
  Q1 : Parenthesis Matching (12 + 3 points)
  
  Your task is to write and analyse an algorithm to verify parenthesis matching in a mathematical expression. Your algorithm must take as input a mathematical expression expressed as a string, and output a boolean result. True indicates that there are no mismatched parentheses in the input string. False indicates that a parenthesis mismatch occurs in the string. The recommended data structure for this problem is a stack.
  

1. Write your algorithm in pseudocode.
   

2.  Analyse your algorithm and give its worst-case runtime complexity.
   

3.  Encode this algorithm in Java. In this and all future questions, the underlying data structure (in this case a stack) must have its own class. You are free to implement the stack however you like, so long as the API is preserved.
   

Q2 : Big O(meg(thet)a)

For each of the following:

(65n4 +2n+3)/(n+1) ∈Θ(n3) (1)

45nlogn + 2n + 1 ∈ Θ(nlogn) (2) 

n2 ∈/ Θ(logn) (3) 

nn ∈/ Θ(2n) (4)

1. (2 points each) Demonstrate the statement using only the definitions of O(f(n)), Ω(f(n)), and Θ(f(n)). 2. (1 point each) Demonstrate the statement using limit rules.

Selection Sort 

Adapt the Selection Sort algorithm given in class (Topic 4) to operate over a doubly linked list. For the purposes of pseudocode, you may assume access to the full DLL API, and may assume the class maintains pointers to the head and tail of the list.

•  Write this algorithm as pseudocode.
  

• Give a worst-case runtime complexity for your algorithm.
  

•  Encode this algorithm in Java. You may also need to implement a doubly linked list class if you don’t already have one kicking around.