Many problems arising in computer science are NP-hard and therefore we do not expect efficient algorithms
for solving them exactly. This has led to the study of approximation algorithms where algorithms are
supposed to run fast but can return approximate solutions. This course provides a broad overview of the
main techniques involved in designing and analyzing such algorithms. It also explore connections between
algorithms and mathematical fields such as algebra, geometry, and probability.
A first course on algorithms and mathematical maturity to read and write proofs will be assumed.
Dartmouth Courses: COSC 31, COSC 30.
Textbooks and Material
There is no required textbook, but there are two excellent textbooks on the subject.
- Approximation Algorithms by Vijay V. Vazirani
- The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys
We will try to provide some notes of our own.
|1/5||Introduction, Steiner Tree|
|1/10||Local Search : Cut Problems|
|1/12||Non-oblivious Local Search|
(maybe, will see how Monday's lecture goes)
|1/28||Finish up GAP.|
|1/31||Randomized Rounding : Set Cover + Independent Set|
|2/18 - 2/19||
Musings on hardness
Class will be held in Filene (Moore B13) in the 12-slot (MWF, 12:50p - 1:55p, X hour : T 1:20-2:10)
DeepC : Calendly link (Tue, Thu, 5p - 6p, zoom or physical)
Let me know before the end of the second week of the term if you will need a disability-related accommodation or service. In order for accommodations to be authorized, students are required to consult with Student Accessibility Services ("SAS" <firstname.lastname@example.org>; SAS website; phone: 603-646-9900) and to email me their SAS accommodation form. We will then work together with SAS if accommodations need to be modified based on the online learning environment. If students have questions about whether they are eligible for accommodations, they should contact the SAS office. All inquiries and discussions will remain confidential.
We recognize that the academic environment at Dartmouth is challenging, that our terms are intensive, and that classes are not the only demanding part of your life. There are a number of resources available to you on campus to support your wellness, including: your undergraduate dean, Counseling and Human Development, and the Student Wellness Center. I encourage you to use these resources and come speak with me to take care of yourself throughout the term.
While the COVID-19 pandemic has already changed how this course is structured, it has the potential to result in further personal impact which may prevent you from continuing engagement in the class. This may be due to contraction of the disease by you or a loved one, increased familial responsibilities, financial difficulties, or impacts on your mental/emotional health.
I have structured the course so that, hopefully, these disruptions will not prevent you from successfully learning the material.
In the event that you are directly or indirectly impacted by COVID-19 in such a way that will affect your performance in the course, it is imperative that you reach out to me as soon as possible. You may also reach out to your undergraduate Dean if that would make you more comfortable. We cannot assist you if we don’t know there is a problem. Our first priority is your health and security. We will work to put you in touch with appropriate resources to assist you.
Some students may wish to take part in religious observances that occur during this academic term. If you have a religious observance that conflicts with your participation in the course, please meet with me before the end of the second week of the term to discuss appropriate accommodations.
To assist with calendar planning and awareness of our diverse religious and spiritual community, the list of holy days for 2020/2021 can be found at https://students.dartmouth.edu/tucker/spiritual-life/about-spiritual-life/holy-day-calendar. The list represents major holy days which may impact accommodation of campus events in general, as well as student course attendance, exams, Commencement and participation in activities 2020-2021. Thank you for your consideration. If you have any questions about these dates or other concerns, please contact Rabbi Daveen Litwin, Dean and Chaplain of the Tucker Center for Spiritual and Ethical Life.
The syllabus page shows a table-oriented view of the course schedule, and the basics of course grading. You can add any other comments, notes, or thoughts you have about the course structure, course policies or anything else.
To add some comments, click the "Edit" link at the top.