2011-2012 Qualifying Examination: Algorithms

2011-2012 Algorithms Ph.D. Qualifying Examination
Department of Computer Science, Virginia Tech

Exam committee

Philosophy of Examination

This exam is based on a set of chapters on the set cover problem from a book (see below).
Each student is responsible for reading beyond the set of assigned chapters so as to thoroughly understand the problem area.
Each student will be evaluated on his/her written paper synthesizing the chapters and via a written exam.

Process and Format

Students must register for this exam. Send your request to register to Lenwood S. Heath. Students currently registered are here:
1. Sudip Saha --- Synthesis paper received --- Committee will schedule written exam
Students must do the following:
1. Write a synthesis of the assigned chapters as a 5-6 page paper, written in 11 point or larger font.
2. On a specific day, take a written exam administered by the committee and based on the chapters and your synthesis paper.
Grading: Written synthesis: 50%. Written exam: 50%.

Schedule

11/21/2011: This page made available.
12/2/2011: Exam details made available.
12/9/2011: Last day to register for the exam. Send your request to Lenwood S. Heath.
1/22/2012: Synthesis paper due. Send your paper as a PDF to Lenwood S. Heath.
TBA: Written exam.
2/15/2012: Exam results due to GPC.

Before each of the dates above make sure you check this page for updates.

Book

The exam is based on chapters from this book:

Approximation Algorithms, Vijay V. Vazirani. Springer-Verlag, 2001.

The chapters for you to master are