Exam 1 for CS:3330 "Algorithms" will be held on Sept 24th (Thursday) from 6:30 pm to 8:30 pm in 101 BBE (Biology Building East).

During the exam you can use any written/printed material you bring, including books and lecture notes; in other words, this is an open book/notes exam. 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 200 points, which is 20% of your final grade. Here is a brief description of the structure of the exam. Points will be equally divided among the 5 problems (so 40 points per problem).

• Problem 1. On comparing or classifying functions by their growth rates and on appropriately using the asymptotic notation (Big Oh, Omega, and Theta).
  Sample problems: Problems 1-5 in Chapter 2, Problem 4 in HW1 and Problem 4 in HW2.

• Problem 2. One evaluating the running time of given code fragments or functions.
  Sample problems: Problem 6 in Chapter 2, Problem 5 in HW1, Problem 3 in HW2.

• Problem 3. On designing an algorithm for a simple problem on lists/arrays with a specific running time. For this problem you will be expected to have some familiarity with basic algorithms on lists (e.g., sorting in O(n log n) time, binary search in O(log n) time, linear search/finding the maximum/merging sorted lists in O(n) time).
  Sample problems: Problem 6 in HW1 and Problem 5 in HW2.

• Problem 4. On designing and analyzing a simple randomized algorithm (Las Vegas and/or Monte Carlo).
  Sample problems: The BalancedPartition problem discussed in class and Problem 6 in HW2.

• Problem 5. On variants of the Stable marriage problem.
  Sample problems: Problems 1-8 from Chapter 1,