CS331: ALGORITHMS AND COMPLEXITY, Spring 2017

Professor Vijaya Ramachandran

Department of Computer Science, UT-Austin

COURSE DESCRIPTION 

Time/Location/Unique number. MW 11-12:30, MEZ B0.306, unique numbers 52066 and 52067.

Discussion Sessions. #52066 F 1-2  in JGB 2.202; #52067 F 2-3 in  JGB 2.202.

Prerequisites. The following coursework with a grade of at least C-:  Computer Science 429 (or 310) or 429H (or 310H); Mathematics 362K or Statistics and Data Sciences 321 (or Statistics and Scientific Computation 321); and credit with a grade of at least C- or registration for: Mathematics 340L, 341, or Statistics and Data Sciences 329C (or Statistics and Scientific Computation 329C).

Professor. Vijaya Ramachandran (vlr"at"cs, GDC 4.430, 471-9554)
Office Hours. TBD.

Teaching Assistant. Udit Agarwal (udit"at"cs.utexas.edu)
TA Office Hours.  TBD.

Textbook.  Jon Kleinberg and Eva Tardos, Algorithm Design, Pearson Education, 2006.

COURSE OUTLINE. This course will cover the basic aspects of the theory of algorithms, including divide-and-conquer, greedy, and dynamic programming, several graph algorithms, randomized algorithms, and approximation algorithms, together with an introduction to undecidability, and to NP-completeness. Here is a high-level course schedule. 

COURSE SCHEDULE.  

This is a theory course and there is no programming content. This course carries the Quantitative Reasoning (QR) flag: establishing the correctness of algorithms and rigorous bounds on their running times, and deriving proofs of NP-completeness and undecidability are important components of this course. 

Coursework. The course grade will be based on the following coursework. 

• Two in-class tests 
• Final exam 
• Problem sets
  

Course Grade. The course grade will be computed as follows: 

• The two tests and the final exam will all be treated equally.
  The top two scores among the three will each contribute 30 points, and the lowest score among the three will contribute 16 points, for a total of 76 points for the three. 
• The problem sets will account for a total of 24 points. There will be 9 problem sets, but only the 8 top scores will be used, each worth 3 points.
• The final grade will be assigned based on the above components, and plus and minus grades will be used.

Key Dates. (Please make a note of these dates -- there will be no make-up test or exam.)

• First Test: Monday, February  27, 7:30-9 p.m. 
• Second Test: Monday, April 17, 7:30-9 p.m.
• Final Exam: Wednesday, May 10,  2-5 p.m.
  

Additional Information on Coursework. 

• At least half of the material in the tests and final exam will build directly on material seen in class and in the problem sets. 
• The second test will mainly cover the material not included in the first test. (Basic background material seen prior to the first test will be included in the second test.)  
• The final exam is comprehensive, and will  cover material  seen throughout the semester.
• You are allowed one sheet of personal notes for each of the two tests, and no other material. You can bring two sheets of notes to the final exam (and no other material). No electronic devices are allowed for the tests and exam, including calculators and cellphones.
• Collaboration on Problem Sets. Students may discuss the problem sets with one another, but solutions must be written up separately. Please include a statement at the start of your solution to each problem that lists the individuals with whom the problem was discussed.  Note that there is no penalty for discussing with other students in the class; you are, in fact, encouraged to do so. But be sure to acknowledge these discussions in your write-up.
  Do not copy solutions from others -- this would be a serious case of scholastic dishonesty. 
• More on Problem Sets. You should not consult any source outside the class. This means that you should not search the web for answers, or ask for help from people not taking this class.

Canvas. All class-related course material will be on Canvas.

Piazza Discussion Board. We will use Piazza for discussions. Please reserve your email messages to the instructor and TA for matters that concern only you. For queries relating to class material, please post to the discussion board on Piazza so that everyone can benefit from the query and the responses. Students are encouraged to post comments and queries about class material on the Piazza discussion board. 

Grading Queries. Any questions on grading should be brought to the attention of the TA or the instructor no later than a week after the graded material is returned to the class. 

Students with Disabilities. Students with disabilities may request appropriate academic accommodations from the Division of Diversity and Community Engagement, Services for Students with Disabilities, 471-6259, http://www.utexas.edu/diversity/ddce/ssd
If you intend to notify me of such accommodations, please do so by February 1. 

Accommodations for Religious Holidays. If you must miss a class or an examination in order to observe a religious holy day, you will be given an opportunity to complete the missed work within a reasonable time before or after the absence.
If you intend to make use of such accommodations, please let me know by February 1. 

Statement on Scholastic Dishonesty. Anyone who violates the rules for the problem sets or who cheats in the  tests or final exam is in danger of receiving an F for the course. Additional penalties may be levied by the Computer Science Department and the University.
The departmental code of conduct posted at http://www.cs.utexas.edu/academics/conduct will apply unless superseded by the rules stated for this course in this course description.