COMPSCI 530 – Algorithms Qualifying Exam
Monday, August 20, 2012
9:00 am - 12:00 noon
D106

Exam is Closed Book

Qualifying Exam Syllabus for COMPSCI 530

Design Techniques: Divide-and-conquer, recurrence relations, greedy algorithms, dynamic programming, randomization.

Sorting and searching: various sorting algorithms, worst case and average case analysis, linear time selection.

Data structures: Heaps, binary search trees, height balanced trees, amortization, union-find, hashing.

Graph algorithms: graph traversal, biconnectivity, strongly connected components, topological sorting, minimum spanning trees, shortest paths, max flow, min cut.

• Geometric algorithms: closest pair, convex hull
• Algebraic algorithms: polynomial multiplication, FFT

Intractability: Easy and hard problems, NP-Completeness, reducibility, approximation algorithms.

References:

• T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, MIT Press. (Chapters 1-13, 15-17, 21-26, 34-35).
• S. Dasgupta, C. Papadimitriou, U. Vazirani, Algorithms, McGraw-Hill.
• J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley (Chapters 1-8, 11.1-11.4).

Sample Exams:

Fall 2011

Fall 2010

Fall 2009