Professor. Vijaya Ramachandran (vlr"at"cs, TAY 3.152, 471-9554).
Office Hours. Mondays 12:30-1:30 and Wednesdays 1:30-2:30.

Teaching Assistant. Pooja Mucherla (poojauta"at"cs).
TA Office Hours. Tuesdays 10:30-11:30 and Thursdays 9-10, place TBA.

Textbook. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, McGraw-Hill, New York, NY, Second Edition, 2001.
A list of known errata and bugs can be accessed from http://mitpress.mit.edu/algorithms/index.html

COURSE OUTLINE. This course will cover the theoretical aspects of algorithm design and analysis. We will study general techniques for algorithm design such as divide-and-conquer, greedy and dynamic programming, as well as randomized algorithms and amortized analysis, and we will study the correctness and efficiency of important data structures and algorithms, with special emphasis on graph algorithms. We will also have a brief introduction to the theory of NP-completeness, and we will study the design of approximation algorithms for NP-hard problems. There will be no programming project.

Who should take this course? This is an upper-division course in computer science theory.
-- Students who like mathematics will like this course.
-- This is an important course for graduate school. Graduate students at UTCS are required to have upper division undergraduate theory background in either algorithms or theory of computation. Graduate CS programs at most other Universities require theory background of upper division undergraduate algorithms.
-- Since it provides the theoretical basis for many algorithms this course is also useful for students planning to go into industry.

Blackboard. Course material will be posted on Blackboard, which is accessible through UTDirect. Any email messages will be sent to the class through Blackboard, so please monitor messages sent to your UT email address.

Grading. The course grade will be based on the following.

• Six homework assignments (20%) -- the lowest score will be excluded, and each of the remaining five will count for 4%
• Six quizzes (15%) -- the lowest score will be excluded, and each of the remaining five will count for 3%
• In-class participation (5%)
• Two in-class tests and a final exam (60%) -- the lowest score will be excluded, and each of the remaining two will count for 30%

Key Dates.

• First Test: Wednesday, February 27, 11:00-12:30.
• Second Test: Wednesday, April 9, 11:00-12:30.
• Final Exam: Thursday, May 8, 2-5.
• Quizzes: January 23, February 4, February 13, March 19, March 31, April 23.

Please make a note of these dates -- there will be no make-up quiz, test or exam. These dates and the dates for the homeworks are also listed on the course schedule webpage.

Homework assignments. Homework solutions must be submitted by 4 p.m. on their due-date in the drop-off box on Taylor breezeway. Be sure to submit your homeworks on time; late homeworks will not receive credit.

Homework collaboration. Students may discuss the problem sets with one another, but solutions must be written up separately. Each problem should be accompanied by a statement that lists the individuals with whom the problem was discussed. If a key idea was obtained from another book or paper (other than the course textbook), then the source of that idea should be cited, and then should be written in your own words. If no outside source was consulted, then a statement to this effect should be made. Note that there is no penalty for discussing with others; you are, in fact, encouraged to do so. But be sure to acknowledge these discussions in your write-up, and also do not copy solutions from others.

Pair Homeworks. For many of the homeworks you will work in pairs. Only one solution should be submitted for each pair, but all of the above rules on collaboration apply. Indicate for each problem in the problem set, who has written the solution, and with whom the problem was discussed, both within the pair and outside of the pair. Please share the writing equally.
Please note that you are responsible for submitting all solutions on time even if your partner is unable to write up their portion of the solutions for any reason. So be in touch and work closely with your partner.

In-class participation. Comments and answers to questions related to class material are encouraged in class and will contribute towards in-class participation. Additionally, there will be some opportunities for students to present a problem solution at the beginning of a class, and follow up with a posting of the solution to the web Blackboard discussion group.

Tests and Final Exam. All three are open book and you can consult your textbook, class handouts, and your personal notes. The top two scores from these three will count towards your final grade. The final exam is cumulative, and will cover the entire semester's material. The first test will be on all material covered until the date of the test, and the second test will be on all material until the date of the test, and not covered for the first test.

At least half of each in-class test and the final exam will be based closely on material covered in class and in the homework problems.

Quizzes. The quizzes are closed-book, and will examine your understanding of the material covered in class.

Statement on Scholastic Dishonesty. Anyone who violates the rules on the homeworks or who cheats in the in-class tests or final exam is in danger of receiving an F for the course. Additional penalties may be levied by the Computer Sciences department and the University.