The course will focus on faster exact algorithms for NP-hard problems. Since we don't expect exact algorithms for these problems to run in polynomial time, we consider getting a finer-grained understanding of how to solve these problems:
We have 4-5 HWs, some solved with collaboration, others solved individually. We will probably have students scribe lecture notes, and also do course projects. (These will typically involve reading research papers with the goal of either surveying a topic, or solving some problems.) Your grade will depend on these HWs, scribe notes, project, and class participation.
We will use Parameterized Algorithms by Cygan et al. for part of the course, but will follow other papers and course notes as neeeded.
15-451 or an equivalent undergraduate class in
Algorithms. Proficiency in basic combinatorics, probability, and
linear algebra. Perhaps mathematical maturity/curiosity and
problem-solving skills are the most important. That way you can make up for gaps in
your knowledge yourself. It is natural to not know everything, or for
you to get rusty on concepts, but you should learn how to learn.
If you
are interested but not sure you are ready for the course, come and
talk to one of us.
One major goal of the course (and of all courses) is that you will have fun taking it and learning this new cool material, as much as we hope to have fun teaching it. Part of making sure you have fun involves taking care of yourself. Do your best to maintain a healthy lifestyle this semester by eating well, exercising, avoiding drugs and alcohol, getting enough sleep and taking some time to relax. This will help you achieve your goals and cope with stress.
If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support. Counseling and Psychological Services (CaPS) is here to help: call 412-268-2922 and visit http://www.cmu.edu/counseling/. Consider reaching out to a friend, faculty or family member you trust for help getting connected to the support that can help.
If you have a disability and are registered with the Office of
Disability Resources, I encourage you to use their online system to
notify me of your accommodations and come and see us to
discuss your needs with me as early in the semester as possible. Since
this is a fast-moving course, we should discuss how to make things work
out. We will work with you to ensure that accommodations are provided as
appropriate. If you suspect that you may have a disability and would
benefit from accommodations but are not yet registered with the Office
of Disability Resources, We encourage you to contact them at
access@andrew.cmu.edu.