CS 336 (Algorithms and Complexity), Fall 2013, Professor Warnow

Course Description

Instructor: Tandy Warnow Office: GDC 4.510, Email: tandy@cs.utexas.edu.

Office hours: W 12:30-1:30

Teaching Assistant: TBD

Class meets: MW 11 AM - 12:30 PM, GDC 1.304

Discussion sections: Fridays 10-11 (JGB 2.202) and 12-1 (GDC 4.302)

Course website: http://www.cs.utexas.edu/users/tandy/331-2013.html

Course Description: This is a required course for CS undergraduates, and covers algorithm design and techniques, as well as computational complexity. I will include algorithms from computational biology to illustrate algorithm design techniques. The course also requires a final project from each student, in which groups of 3-4 students per group implement and test a heuristic for an NP-hard computational biology problem.

Pre-requisites: the following courses with a grade of at least C- in each: CS 313H or 313K; 312, 314 or 314H; and M 408C, 408N, or 427L; and SSC 321 or M362K. Finally, M340L is required as a pre-requisite or co-requisite.

Textbook: Algorithm Design, by Jon Kleinberg and Eva Tardos

Tentative Syllabus

• Review of pre-requisites (graphs, reading and writing mathematics, running time, combinatorial counting, and proof techniques): 1 week
• Greedy Algorithms: 2 weeks
• Dynamic Programming: 2.5 weeks
• Divide-and-conquer: 1 week
• NP-hardness and polynomial reductions: 2 weeks
• Approximation algorithms: 1.5 weeks
• Randomized algorithms: 1 week
• Undecidability: 1 week

Grading

• Homework (20%)
• Exam I: September 30 (15%)
• Exam II: October 28 (15%)
• Exam III: November 20 (15%)
• Final Project: due Nov 27 (10%)
• Final exam (25%)

Details

• Homework:
  • Homeworks will include programming assignments, algorithm design, and theoretical analyses of algorithms (both running time and correctness). I will provide instructions on how to submit programming assignments later.
  • The theory portions of each homework are due in class, on the day they are due; these can also be submitted by email (in PDF form) in advance of the class if desired. Late theory homeworks will not be accepted under any circumstances.
  • The programming assignments are also due at this time. However, unlike the theory homeworks, you are permitted a total of 10 late days for the programming assignments, provided that no individual programming assignment is more than 7 days late.
  • You are allowed to collaborate with other students from this course on your homeworks, but you must identify (in writing) the names of all students who worked with you, and you must write up your solutions entirely separately. (Identical or near-identical solutions will be unacceptable and not receive credit.)
• Quizzes: these may not be annouonced in advance, but will not count towards your grade.
• Final Project: Groups of at most 3-4 students can work together on this. The project will be to develop and test heuristics for one of two NP-hard problems (Maximum Weight Quartet Compatibility and Maximum Parsimony). Note - there are many very good heuristics for maximum parsimony, but fewer good heuristics for maximum weight quartet compatibility. Therefore, there's a possibility you might develop a technique that is publishable and useful if you work on the maximum weight quartet compatibility problem! Some of the programming assignments that are assigned as homework will be usable in this final project. The final project also has a writing component, in which you describe your heuristics and how well they performed on the test data that I will provide. A PDF for your final project is due on November 27, in class, and a short presentation of the project in class on December 2 or December 4.
• Exams: closed book - no notes, no phones, and no internet access during the exam.

Policies

• You are responsible for all the material taught in the class, and not all of it is covered in the textbook. If you miss a class meeting, please be sure to obtain notes from one of your fellow students. You can also download the presentation given by the instructor by the evening after the class.
• If you will not be able to attend class for some reason that reasonably you would know about in advance (e.g., a religious holiday or sporting event in which you are a participant), you should tell me about this in the first week of class, so that I can try to accomodate your schedule. (Observed religious holidays will always be accomodated.)
• Please do not use your cellphone while in the class -- it is distracting to the other students, and unnecessary.

Academic honesty

• Please see Professor Elaine Rich's discussion of academic honesty and appropriate conduct.
• Most importantly, do not, under any circumstances, submit work that is not your own work. Penalties for cheating are very serious, and cheating becomes part of your permanent university record.

Course notes

• Please see this for some terminology (from a previous class), especially helpful for talking about graphs.
• Professor Dan Gusfield of the University of California at Davis has written a delightful and informative discussion on induction proofs called ``Why Johny can't induct". Please click here to download the pdf.

Class Presentations

• August 28 and September 4: Basics (PPT) (PDF)
• September 9-11: Dynamic Programming Algorithms (PPT) (PDF)
• September 16-18: Recursion and Divide-and-Conquer algorithms (PPTX) (PDF)
• September 23-25: Graph Algorithms (PPT) (PDF)
• September 30: Exam 1
• October 2-7: Minimum Spanning Tree (PPT) (PDF)
• October 9: All-pairs shortest path DP algorithms (PPT) (PDF)
• October 14: Computing your Erdos Number (aka Dijkstra's Algorithm) (PPTX) (PDF)
• October 16-21: Randomized algorithms (PPT) (PDF)
• October 28: Exam 2
• October 30 to Nov 11: NP-hardness (PPT) (PDF)
• November 13 and 18: Approximation algorithms (PPT) (PDF)
• November 20: Exam 3
• November 25 and 27: Undecidability (Final projects are due on November 27) (See www.cgl.uwaterloo.ca/~csk/halt)
• December 2 and 4: Review for final exam