Joydeep Ghosh
Algorithms
ghosh AT ece ADOT utexas ANOTHERDOT edu
Fall 2007
ACES 3.118
Unique No. 16890
Office Hours: MW 2:00-3:00pm
TTh 11-12:30p  ENS 115

Teaching Assistants and Office Hrs: 
Shweta Agrawal (shweta.a"at"gmail.com), M 12:30-2pm, Tu 2-3:30; Wed 3-4:30; ACES 5.424
Archis Apte (archis"at"mail.utexas.edu), M 2-3pm, Tu and Th: 3:30-5; ACES 3.102.
TA Webpage:

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
Additional Resource: Jon Kleinberg and Éva Tardos, Algorithm Design, Addison Wesley, 2005

COURSE OUTLINE. This course will cover the theoretical and practical aspects of algorithm design and analysis. We will study general techniques for algorithm design such as divide-and-conquer, greedy and dynamic programming,  and we will study the correctness and efficiency of important data structures and algorithms, with special emphasis on graph algorithms. In parallel with the study of algorithms will be programming assignments on algorithm development and testing.

PRE-REQs: This course is intended for undergraduate students who have taken EE322C. You should be comfortable writing, compiling, and debugging C programs of a moderate complexity (hundreds of lines).

GRADING POLICY; IMPORTANT DATES:
40%    Homeworks including Programming Assignments
15%    Final Project, Due Dec 6. No full/partial credit for late submission.
20%    Test 1; Oct 18, in class
25%    Test 2; Nov 29, in class

In-class tests are closed book/notes. No calculators/computers/PDA. However you are allowed one one-sided sheet of notes for each in-class test. The sheets of notes can contain definitions and statements of lemmas and theorems, and equations; they should not contain algorithms or proofs.

Collaboration:
1. Written homework: Try to solve the problems by yourself. If you find a particular problem very difficult, you may discuss it with other students; if you choose to do so, please indicate this on the submission. (Even in this case, you should write your solutions independently.)  If you obtain your solution with help from another source (e.g., a book or website), please cite this in the write-up.
2. Programming assignments: These will be done in groups of two. Again, while you may discuss your approach with other groups, there should be no sharing of code. You should not use code other than that which you write by yourself, or given to you by us.

Late assignment policy: All HWs are due at the beginning of class on the due date. Late programming assignments (with exception of final project, as noted above) will be penalized 25% up to the first 24 hours, 50% for 24 to 48 hours, with no credit received after that. The late penalty may be waived for extremely exceptional circumstances (e.g.your  medical emergency or death  in near family, evidenced by letter from doctor or obituary notice) but only if you contact the instructor before the penalty is incurred.

ACADEMIC DISHONESTY AND POLICIES ON CHEATING: Faculty in the ECE Department are committed to detecting and responding to all instances of scholastic dishonesty and will pursue cases of scholastic dishonesty in accordance with university policy. Scholastic dishonesty, in all its forms, is a blight on our entire academic community. All parties in our community -- faculty, staff, and students -- are responsible for creating an environment that educates outstanding engineers, and this goal entails excellence in technical skills, self-giving citizenry, and ethical integrity. Industry wants engineers who are competent and fully trustworthy, and both qualities must be developed day by day throughout an entire lifetime. Scholastic dishonesty includes, but is not limited to, cheating, plagiarism, collusion, falsifying academic records, or any act designed to give an unfair academic advantage to the student. The fact that you are in this class as an engineering student is testament to your abilities. Penalties for scholastic dishonesty are severe and can include, but are not limited to, a written reprimand, a zero on the assignment/exam, re-taking the exam in question, an F in the course, or expulsion from the University. Don't jeopardize your career by an act of scholastic dishonesty. Details about academic integrity and what constitutes scholastic dishonesty can be found at the website for the UT Dean of Students Office and the General Information Catalog, Section 11-802.

The default policy on cheating to be followed in this course is: The first time I spot a case of cheating, e.g. copying a homework solution from the web, or cheating in an exam, the cheater gets a zero for the entire assignment/exam. If this person is caught cheating a second time, then he/she gets an F for the course.

Tentative Course Outline and Class Notes

I will use the board as well as overheads; Some notes are linked below, and may be updated before class. Additional materials provided through blackboard.