CS357: ALGORITHMS
The University
of Texas at Austin
Department
of Computer Sciences
January 19, 2007
COURSE DESCRIPTION
Professor. Vijaya Ramachandran
(vlr"at"cs, TAY 3.152, 471-9554).
Office Hours. Mondays 3:00-4:00 and Wednesdays 1:30-2:30.
Teaching Assistant.
Sumeet Rao
(sumeetrao"at"gmail.com).
TA Office Hours. Tuesdays noon-1:00 and Thursdays 10:30-11:30
in ESB 229, Desk 1.
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 in this course.
Who should take this course?
This is an upper-division elective 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 to class will be sent through Blackboard, so please monitor messages sent to your UT email address.
Homework assignments. Homework solutions should be presented in a clear and concise manner. Every algorithm you present should be accompanied by a proof of correctness.
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.
If no outside
source was consulted, then a statement to this effect should be made.
In short, there should be a statement accompanying each submitted problem
solution declaring the nature of the outside sources, if any, that were
consulted while working on the solution.
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. Questions and comments related to class material are encouraged during lectures. Additionally, each student will need to sign up to present a problem solution on the blackboard in class, and will need to post the solution to the web Blackboard discussion group within two days after the class presentation. Follow-up discussion on posted solutions on Blackboard by other students is welcome and encouraged.
Tests and Final Exam. The in-class tests and final exam will be closed-book. The final exam is cumulative, and will cover the entire semester's material.
You are allowed one sheet of notes for each in-class test and three sheets of notes for the final exam. The sheets of notes can contain definitions and statements of lemmas and theorems; they should not contain algorithms or proofs.
The material covered in class and in the problem sets and in the class problem presentations will comprise at least half of each in-class test and the final exam.
Grading. The course grade will be based on the following.
Key Dates.
Please make a note of these dates -- there will be no make-up test or exam. These dates and the dates for the homeworks are also listed in the course schedule, whose URL is given below.
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.
Course URL. http://www.cs.utexas.edu/~vlr/s07.357/index.html
The course schedule will be available at http://www.cs.utexas.edu/~vlr/s07.357/sched.html
Course notes are available at http://www.cs.utexas.edu/~vlr/s07.357/notes.