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.
Intractability: Easy and hard problems, NP-Completeness, reducibility, approximation algorithms.
References:
Sample Exams: