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 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

• 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
• 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: Tae-hyung Kim
    • Problem 4: Fangcheng Tang
    • Problem 5: Fangcheng Tang
    • Problem 6: Fangcheng Tang
    • Problem 7: Soma Chaudhuri

Exam 2

• Schedule

• 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)
    • 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
• 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: Tae-hyung Kim
    • Problem 3: Fangcheng Tang
    • Problem 4: Tae-hyung Kim
    • Problem 5 (a)-(b): Zhi Liu , (c): Soma Chaudhuri
    • Problem 6 (a)-(c): Zhi Liu , (d)-(e): Soma Chaudhuri

Exam 3

• Schedule

• Topics
  • Elementary Graph Algorithms (Chapter 22.2, 22.3, 22.4)
    • Breadth-first search
    • 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

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