Exam 1 for CS:3330 "Algorithms" will be held on Feb 20th (Tuesday) from 6:30 pm to 8:30 pm in W128 CB (Chemistry Building).

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 150 points, which is 15% 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 30 points per problem).

• Problem 1. On comparing or classifying functions by their growth rates, on appropriately using asymptotic notation (Big O, Omega, and Theta), on identifying the input size of a problem, and on figuring out if an algorithm is efficient by expressing its running time as a function of its input size.
  

• Problem 2. On evaluating the running time of given code fragments or functions.
  

• Problem 3. On numerical algorithms including addition, subtraction, multiplication, and division of large numbers, the modulo power algorithm, the modulo Fibonacci algorithm, and the primality testing algorithm based on Fermat's Little Theorem.

• Problem 4. On designing and analyzing simple randomized algorithm (Las Vegas and/or Monte Carlo), including primality testing, balanced partition (Quiz 2), randomized quicksort, randomized selection, and other randomized algorithms you've seen in homeworks.

• Problem 5. On designing a "divide-and-conquer" algorithm, setting up a recurrence for it, solving recurrences visually, by unrolling, or by using the Master Theorem.