CS:3330 Exam 1 Announcement
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,