CS378 - Algorithms and Complexity (Spring 2013)

Added later: This class is now CS 331.
Syllabus: Detailed syllabus in pdf (revised Feb 7)
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Phone: 471-9729
Office: GDC 4.508
Office Hours: MW 4-5, or by appointment.
TAs: Eshan Chattopadhyay, eshanc@cs.utexas.edu, Office Hours: Thursday 12-1, GDC 4.440 (4th floor lobby).
Muhibur Rasheed, muhibur@cs.utexas.edu, Office Hours: Tuesday 10-11, GDC 1.302.
Fangkai Yang, fkyang@cs.utexas.edu, Office Hours: Tuesday 1-2, GDC 3.802C.
Logistics: MWF 3-4.
ECJ 1.202.
Unique Number (Discussion Section Time; TA): 53536 (F 11-12; TAs alternate), 53537 (F 12-1; Eshan), 53538 (F 2-3; Fangkai), 53539 (F 2-3; Muhibur).
Course web page: http://www.cs.utexas.edu/~diz/378
Text: Kleinberg and Tardos, Algorithm Design
Course Topics:
Topic Chapter(s) Approximate Time
Introduction 1.1, 2 1 week
Basic Graph Algorithms 3 1 week
Greedy Algorithms 4 2 weeks
Divide and Conquer 5 1-2 weeks
Dynamic Programming 6 1-2 weeks
Undecidability N/A 1 week
NP and Computational Intractibility 8, 9.1 1-2 weeks
Approximation Algorithms 11 1 week
Randomized Algorithms 13 1-2 weeks

May 1 lecture: Slides: The Power of Randomness in Computation
Companion essay: Can Random Coin Flips Speed Up a Computer?
Grading: 45%: 3 In-Class Exams
40%: Final Exam
15%: Homework
Homework: There will be a problem set almost every week, posted on Blackboard.

Collaboration policy: While you should first think about the problems on your own, you are encouraged to discuss the problems with your classmates. However, you must write up your own solutions. In particular, nobody should email partial or full solutions to anybody. You must acknowledge any collaboration by writing your collaborators' names on the front page of the assignment. You don't lose points by having collaborators.

Citation policy: Try to solve the problems without reading any published literature or websites, besides the class text and links off of the class web page. If, however, you do use a solution or part of a solution that you found in the literature or on the web, you must cite it. Furthermore, you must write up the solution in your own words. You will get at most half credit for any solution found in the literature or on the web.

Submission policy: Homeworks are due at the beginning of class.

Late policy: Late homeworks will not be accepted.

Exams: The three in-class exams will be given on the following dates: Exam 1 on Friday, February 8; Exam 2 on Wednesday, March 20; and Exam 3 on Friday, April 12. The final exam will be cumulative, and given on Wednesday, May 8, from 7-10pm in FAC 21. No make-up exams will be given, so plan accordingly. You may bring a single, 8.5x11 inch, handwritten sheet of paper (you may use both sides). For the final exam, you may bring four such sheets. No calculators are allowed (they won't be necessary).
Piazza: We will be using Piazza for class discussion. The system is highly catered to getting you help fast and efficiently from classmates, the TAs, and myself. Rather than emailing questions to the teaching staff, please post your questions on Piazza. If you have any problems or feedback for the developers, email team@piazza.com. Find our class page at: https://piazza.com/utexas/spring2013/cs378algorithmsandcomplexity/home.

Last modified: May 7, 2015.