Final Exam Study Guide
CSE 521: Algorithms
Spring 2003

Final Exam, June 11, 2003, 10:30 - 12:20

• Policies
  • The final exam is open book (CLRS) and open notes. Open notes includes homeworks and their solutions, thumbnails of lectures, and your own personal notes. Nothing else is allowed.
  • The exam begins promptly at 10:30 and ends at 12:20.
• Topics covered
  • Network flow. Ford/Fulkerson and Edmonds/Karp algorithms. Max flow - min cut theorem. Reductions of problems to network flow.
  • Linear programming. The simplex algorithm. Duality theorem. Reduction of problems to network flow.
  • Algorithms for polynomials and the fast Fourier transform algorithm. Evaluation, interpolation, multiplication, and division of polynomials. Roots of unity. The Fourier transform and its applications.
  • Number theoretic algorithms. Integer arithmetic and bit complexity. Euclid's algorithm and its extension. Basic number theory including the additive and multiplicative modular groups. Chinese remainder theorem. Mixed radix arithmetic. RSA public key encryption.
  • Computational Geometry algorithms. Plane sweep algorithms. Line segment intersection. Convex hull. Voronoi diagram. Randomized incremental algorithms. K-d trees and their applications.
  • Approximation algorithms. Approximation ratio. NPO, APX, PTAS, FPTAS classifications of optimization problems. Ad hoc algorithms for Euclidean traveling salesman and vertex cover. Non-approximability of traveling salesman. Linear programming relaxation. FPTAS for subset sum approximation.
  • On-line algorithms. Competitive ratio. Ad-hoc on-line algorithms for edge coloring and load balancing. Analysis of page replacement algorithms: LRU, LIFO, and FIFO. Competitive analysis of list update. Use of potential functions.
  • Arithmetic coding. Basics of entropy. The arithmetic coding algorithm. Dealing with context, adaptivity, and scaling.
  • Optimal binary search trees: Basics of dynamic programming. O(n^3) dynamic program for the optimal binary search tree. It's improvement to O(n^2) using monotonicity. Binary comparison search trees.
  • PQ-trees and the contiguous ordering problem.
• Study suggestions
  • Look at my old 589 exam to get an idea of problems I might ask about any material for which there was no homework. Final exam from 589
  • Study the homeworks and their solutions because some of the exam questions will be related to the homework.
  • Work in study groups to help each other out in preparation. Give each other problems to do in an exam setting. After doing the problems alone, critique each others answers.

  ---

  ladner@cs.washington (Last Update: )