Professor. Vijaya Ramachandran (vlr"at"cs), TAY 3.152A, 471-9554.
Office Hours. Tuesdays 11-noon, Thursdays 3-4.

Teaching Assistant. Rezaul Alam Chowdhury (shaikat"at"cs).
TA Office Hours. Wednesdays noon-1 and Fridays 10-11, in ESB 229, Desk 2.

Textbook and Course Material.

• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, Second Edition, McGraw-Hill, New York, NY, 2001. (A list of known errata and bugs can be accessed from http://mitpress.mit.edu /algorithms/index.html)
• Selected journal and conference papers, which will be distributed to the class.
• Lecture notes, which will be posted on Blackboard.

Prerequisites. Graduate standing, and an undergraduate algorithms course such as CS357.

Grading.

• Problem sets (25%)
• Class participation (10%)
• 3 tests (65%): The first and second tests are worth 20% each, and the third test is worth 25%.

Blackboard. Class notes will be posted on Blackboard, which can be accessed through UTDirect.
Solutions to problems presented in class (see below) should be posted on the discussion board in Blackboard.

Problem Sets.

• Students may discuss homework problems with one another, but solutions must be written up separately.
• For each problem, the solution must be accompanied by a statement naming the people with whom the problem was discussed and the books or other sources that were consulted in order to solve the problem. If you solve a problem entirely on your own, you should state this fact.
• Some of the problem sets will be designated to be solved in pairs. For these problem sets, students will pair up and each pair will submit one solution. The same rules as above apply to these problem sets, but additionally, the students in each pair will collaborate to solve all problems, and should share equally in writing up the solutions.
• Homeworks should be placed in the homework drop-off box in Taylor breezeway by 2 p.m. on the day they are due.
  Please state clearly the course number (CS388G) and the names of the instructor and TA on the first page of your homework.

Class Participation. The class participation grade will be based primarily on solving problems in class, and additionally on attendance and on contributions to classroom discussions.

Solving problems in class:

• Students must sign up to present solutions to problems at the beginning of class on certain dates. This is typically a 5 to 10 minute presentation of the solution to a problem assigned during the previous class.
• After presenting an assigned problem solution in class, you will need to post the solution to the web Blackboard discussion group within two days after the class presentation.
• Follow-up discussion on these posted solutions on Blackboard by other students is welcome and encouraged.

In-class Tests. The first test and second test will be closed-book. One sheet of notes is allowed, but should contain no proofs or algorithms. The third test will be open-book. Dates for the three tests:

• First test in-class on Wednesday, October 5, worth 20%
• Second test during the second week of November to be scheduled outside class hours, worth 20%; date and time will be finalized by mid-September in consultation with the class. Tentative date: Friday, November 11, 3-4:15 p.m.
• Third test during the last week of classes to be scheduled outside class hours, worth 25%; date and time will be finalized by mid-September in consultation with the class. Tentative date: Friday, December 9, 3-4:15 p.m.

Course Outline. Here is an approximate course schedule.

• Divide and conquer; recurrence relations (about 1 week)
• Randomized algorithms (about 3 weeks)
• Data structures: hashing, amortized analysis, Fibonacci heap, disjoint sets data structure and the `alpha' technique, splay trees (about 3 weeks)
• External-memory algorithms; on-line algorithms (about 2 weeks)
• Greedy algorithms, matroids, dynamic programming (about 2 weeks)
• Maximum flow, maximum matching, linear programming (about 2 weeks)
• NP-completeness, proof of Cook's theorem, topics in approximation algorithms for NP-hard problems (about 2 weeks).

Course URL. http://www.cs.utexas.edu/~vlr/f05.388g