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:
- Sudip Saha
--- Synthesis paper received --- Committee will schedule written exam
-
Students must do the following:
-
Write a synthesis
of the assigned chapters
as a 5-6 page paper,
written in 11 point or larger font.
-
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
- Chapter 2: Set Cover
- Chapter 13: Set Cover via Dual Fitting
- Chapter 14: Rounding Applied to Set Cover
- Chapter 15: Set Cover via the Primal-Dual Schema