DESIGN AND ANALYSIS OF ALGORITHMS
Com S 311
Exams
All Com S 311 exams will be closedbook and closednotes. 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 
 
 
 

Exam 2 
Nov 10 
 
 
 

Exam 3 
Dec 17 
 
 
 
 
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 (bigO, bigTheta, bigOmega) notation
 common functions (floors & ceilings, logarithms, etc)
 time and space complexity
 algorithm analysis (best case, worst case, average case)
 divideandconquer
 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
 ComparisonBased 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
 Basics (Chapters 1, 2, 3)
 Grading
 Each problem will be graded by the same instructor or TA like homeworks.
 The grader list will be announced here after grading is finished.
 Grader list
 Problem 1: Balaji Venkatachalam
 Problem 2: Zhi Liu
 Problem 3: Taehyung Kim
 Problem 4: Fangcheng Tang
 Problem 5: Fangcheng Tang
 Problem 6: Fangcheng Tang
 Problem 7: Soma Chaudhuri
 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
 Radix sort
 Binary Search Trees (Chapter 12.1, 12.2, 12.3)
 Binarysearchtree property
 Successor and Predecessor
 Insertion and Deletion
 RedBlack Trees (Chapter 13.1, 13.2, 13.3)
 Redblack properties
 Blackheight
 Rotations
 Insertion
 Augmenting Data Structures (Chapter 14.1, 14.2)
 Dynamic order statistics
 Augmenting redblack trees
 Dynamic Programming (Chapter 15.2, 15.3, 15.4)
 Optimal substructure
 Overlapping subproblems
 Bottomup solution
 Memoization
 Matrixchain multiplication
 Longest common subsequence
 01 knapsack
 Greedy Algorithms (Chapter 16.1, 16.2)
 Greedychoice 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
 Sorting in Linear Time (Chapter 8.1, 8.2, 8.3)
 Grading
 Each problem will be graded by the same instructor or TA like homeworks.
 The grader list will be announced here after grading is finished.
 Grader list
 Problem 1: Jun Ge
 Problem 2: Taehyung Kim
 Problem 3: Fangcheng Tang
 Problem 4: Taehyung Kim
 Problem 5 (a)(b): Zhi Liu , (c): Soma Chaudhuri
 Problem 6 (a)(c): Zhi Liu , (d)(e): Soma Chaudhuri
 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)
 Breadthfirst search
 Depthfirst 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
 UnionFind data structure
 Single Source Shortest Paths (Chapter 24.1, 24.3)
 Dijkstra's algorithm
 BellmanFord algorithm
 Relaxation
 Shortest Paths tree
 All Pairs Shortest Paths (Chapter 25.1, 25.2)
 Using Dynamic Programming
 FloydWarshall algorithm
 String Matching (Chapter 32.1, 32.3, 32.4)
 Brute force algorithm
 String matching with finite automata
 KnuthMorrisPratt 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
 NPCompletness (Chapter 34)
 Polynomial time
 definition of P, NP and NPcomplete
 polymomialtime reductions
 NPcomplete problems
 Elementary Graph Algorithms (Chapter 22.2, 22.3, 22.4)
Grading
 Each problem will be graded by the same instructor or TA like homeworks.
 The grader list will be announced here after grading is finished.
Iowa State University  Computer Science Department  Top of this page