Professor. Vijaya Ramachandran (vlr"at"cs, TAY 3.152, 471-9554).
Office Hours. Tuesdays and Thursdays 10:30-11:30 am.

Teaching Assistant. Aibo Tian (atian"at"cs.utexas.edu)
Office Hours. Mondays 12:30 - 1:30 pm and Fridays 9:30 - 10:30 am at Desk 3, ENS 31NQ.

Proctor. Jackie Tsay (j.tsay"at"mail.utexas.edu)
Proctor Review Hour. Mondays 11:30 - 12:30 at whiteboard in Taylor Hall basement.
Additionally, there is an ACM study session in Tay 3.128 on Mondays 5-7 pm for all theory courses, including CS357. Your proctor as well as other tutors will be available to help you at the study session.

Textbook. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, McGraw-Hill, New York, NY, Third Edition, 2009.

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.

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.

Discussion Board. There is a discussion board on Blackboard, and students are encouraged to post queries about class material there. Feel free to post comments and responses to queries, and note that useful participation on the discussion board will contribute towards your class participation score. This discussion board will also be monitored by your TA and proctor, who will post comments and responses as needed.

Please reserve your email messages to the instructor, TA, and proctor for matters that concern only you. For queries relating to class material, please post to the discussion board so that everyone can benefit from the query and the responses.

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

• Six homework assignments (25%) -- the lowest score will be excluded, and each of the remaining five will count for 5%
• Six mini-tests (15%) -- the lowest score will be excluded, and each of the remaining five will count for 3%
• In-class participation, including attendance (5%)
• Two in-class tests and a final exam (55%) -- the lowest score will be count for 5%, and each of the remaining two will count for 25%

Key Dates. We will hold the in-class tests outside class hours in the evening to allow for double seating.
The two in-class tests and the final exam will be 90 minute tests, but they are scheduled in larger time-slots to allow students to take more time to write their solutions carefully.

• First Test: 7-9 p.m. on Tuesday, March 9.
  Class on January 19 will account for this test given outside of class hours.
• Second Test: 7-9 p.m. on Tuesday, April 20.
  Class on Thursday, April 22 is cancelled to account for this test.
• Final Exam: Saturday, May 15, 9 am - noon.
• Mini-tests: In class during class hours on January 28, February 9, February 23, March 23, April 6, April 29.
  The first and last mini-tests are on Thursdays, and the remaining mini-tests are on the Tuesday following the day the homework is handout out.

Please make a note of all of these dates -- there will be no make-up mini-test, 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 1 pm on their due-date in the drop-off box on Taylor breezeway.
You can submit a homework late for a 20% penalty in your score. Late homeworks must be submitted by 1 pm the day after the due-date. There will be no credit given for a homework submitted more than 24 hours after the time is was due.

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.
If you fail to include a collaboration statement in the homework you turn in, you will receive a 10% penalty in your score.

Pair Homeworks. For many of the homeworks you will have the option to 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. In the case of pair homeworks, we expect both partners to contributed significantly towards solving the problems and writing the solutions; the statement on collaboration and the writing of solutions should reflect this.
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. Attendance will be taken at each class, and will contribute towards the class participation score. Two class absences are allowed with no penalty.
Comments and answers to questions related to class material are encouraged in class and can contribute towards to the in-class participation.

Tests and Final Exam. All three are closed book. You are allowed to bring one sheet of notes to each of the first two tests, and 3 sheets of notes for the final exam.

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.
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.

Mini-tests. The mini-tests are open-book, and will examine your understanding of the material covered in class.

Grades. The following lower bounds apply to cut-offs for grades:
90% for A, 85% for A-, 80% for B+, 75% for B, 70% for B-, 65% for C+, 60% for C, 55% for C-.
You are guaranteed the stated grade if you receive a total score that matches or exceeds its cut-off. It is possible that some of these cut-offs may be slightly lowered but they will not be raised.

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. See http://www.cs.utexas.edu/academics/conduct/

Webpages.

Course Description (this page): http://www.cs.utexas.edu/~vlr/s10.357/index.html

Course Schedule: http://www.cs.utexas.edu/~vlr/s10.357/sched.html