# Exams

## DESIGN AND ANALYSIS OF ALGORITHMS Com S 311

Exams

All Com S 311 exams will be closed-book and closed-notes. Scratch papers will be distributed.
Calculators are NOT allowed.

Exams will be held together for both lecture sections.

 Exam Date Sample Exam A Sample Exam B Problems Solutions problems Solutions problems Solutions Exam 1 Oct 6 S01 exam1 - S03 exam1 - - [sol] Exam 2 Nov 10 S01 exam2 - F02 exam2 - - [sol] Exam 3 Dec 17 F02 exam3 - S03 exam3 - - -

Exam 1

The emphasis is on understanding and applying the covered techniques rather than on sheer memorization. Complex formulae and theorems (such as the Master Theorem), if they appear on the exam, will be available to you with adequate descriptions.

• Schedule
 Date Monday, October 6, 2003 Time All Sections 8:00pm - 10:00pm Place 2245 Coover
• Topics
• Basics (Chapters 1, 2, 3)
• asymptotic (big-O, big-Theta, big-Omega) notation
• common functions (floors & ceilings, logarithms, etc)
• time and space complexity
• algorithm analysis (best case, worst case, average case)
• divide-and-conquer
• loop invariants
• Summations (Appendix A)
• summation formulae and properties
• arithmetic and geometric series
• bounding summations (telescoping, induction, splitting, approximation by integrals)
• Recurrences (Chapter 4.1, 4.2, 4.3)
• setting up recurrences for algorithms
• the substition and iteration methods
• recursion trees
• the Master Theorem
• Comparison-Based Sorting Algorithms (Chapters 2, 6, 7)
• Insertion sort
• Mergesort
• Heapsort
• Quicksort (Partition)
• Order Statistics (Chapter 9.1, 9.2)
• finding minimum, maximum, and median
• Selection, linear time randomized algorithm

Exam 2

• Schedule
 Date Monday, November 10, 2003 Time All Sections 8:00pm - 10:00pm Place 2245 Coover
• Topics
• Sorting in Linear Time (Chapter 8.1, 8.2, 8.3)
• Lower bound for sorting
• Counting sort
• Binary Search Trees (Chapter 12.1, 12.2, 12.3)
• Binary-search-tree property
• Successor and Predecessor
• Insertion and Deletion
• Red-Black Trees (Chapter 13.1, 13.2, 13.3)
• Red-black properties
• Black-height
• Rotations
• Insertion
• Augmenting Data Structures (Chapter 14.1, 14.2)
• Dynamic order statistics
• Augmenting red-black trees
• Dynamic Programming (Chapter 15.2, 15.3, 15.4)
• Optimal substructure
• Overlapping subproblems
• Bottom-up solution
• Memoization
• Matrix-chain multiplication
• Longest common subsequence
• 0-1 knapsack
• Greedy Algorithms (Chapter 16.1, 16.2)
• Greedy-choice property
• Optimal substructure
• Greedy algorithms vs. dynamic programming
• Activity selection
• Fractional knapsack
• Graphs and Trees (Appendix B.4 and B.5)
• Undirected and directed graphs
• Paths and cycles
• Connected components
• Free and rooted trees
• Elementary Graph Algorithms (Chapter 22.1)
• Representations of graphs

Exam 3

• Schedule
 Date Wednesday, December 17, 2003 Time All Sections 7:00pm - 9:00pm Place 1414 Mol Bio
• Topics
• Elementary Graph Algorithms (Chapter 22.2, 22.3, 22.4)
• Depth-first search
• Topological sort
• Minimum Spanning Tree (Chapter 23)
• Cuts and light edges
• Proving the greedy property
• Prim's algorithm
• Array and heap implementations
• Kruskal's algorithm
• Union-Find data structure
• Single Source Shortest Paths (Chapter 24.1, 24.3)
• Dijkstra's algorithm
• Bellman-Ford algorithm
• Relaxation
• Shortest Paths tree
• All Pairs Shortest Paths (Chapter 25.1, 25.2)
• Using Dynamic Programming
• Floyd-Warshall algorithm
• String Matching (Chapter 32.1, 32.3, 32.4)
• Brute force algorithm
• String matching with finite automata
• Knuth-Morris-Pratt algorithm
• prefix function
• Computational Geometry (Chapter 33.1 - 33.3)
• Cross and dot products
• Line segment intersection
• Line sweeping
• Convex hull, Graham's scan, Jarvis's march
• NP-Completness (Chapter 34)
• Polynomial time
• definition of P, NP and NP-complete
• polymomial-time reductions
• NP-complete problems