The midterm exam for CS:5350 "Design and Analysis of Algorithms" will be held on March 3rd (Th) from 6:30 pm to 8:30 pm in 125 Trowbridge Hall.

During the exam you can use any written/printed material you bring, including books, lecture notes and solutions, handwritten notes, etc. Make sure you bring everything that you feel you will need to the exam because you will not be allowed to share or borrow material with classmates during the exam. You will have to turn off and remove from your vicinity all electronic devices including cell phones, lap tops, calculators, dictionaries, etc.

The exam is worth 250 points, which is 25% of your final grade. Here is a brief description of the structure of the exam. The first two problems are worth 20 points each and the remaining two are worth 30 points each. Points will be equally divided among multiple parts of a problem.

• Problem 1. You will be given "high level" description of different divide-and-conquer algorithms and you will be asked to choose one with the best asymptotic running time. This problem will test your skills of converting a "high level" description of a divide-and-conquer algorithm into a recurrence relation and solving it.

• Problem 2. You will be given a problem on a sequence and asked to design a divide-and-conquer algorithm for it. Classic examples of "divide-and-conquer" algorithms on sequences are binary search and merge sort.

• Problem 3. You will be given a problem and asked to produce a "1-dimensional" dynamic programming solution for it. A "1-dimensonal" dynamic programming solution refers to the fact that the subproblems are characterized by a single parameter and therefore the solutions of these subproblems can be stored in an array (1-dimensional table). Our solution to the Weighted Interval Scheduling problem is a good example of a 1-dimensional dynamic programming solution.

• Problem 4. You'll be given a problem and will be led through a "2-dimensional" dynamic programming solution to the problem. You'll be provided guidance that will help you identify subproblems and the connection between optimal solutions to these subproblems. Examples of "2-dimensional" dynamic programming solutions you have seen are (i) least common subsequence problem and (ii) Problem 2 in HW4.