Catalogue Description:
3-0-3. Prerequisites: CS 1155 and either CS 2201 or one of the
following: CS 2360, CS 2390, or CS 2430; MATH 3012.
Introduction to the mathematical analysis of computer algorithms,
correctness, complexity, asymptotic lower bounds, efficient data
structures, and combinatorial algorithms. NP-complete problems.
Instructor:
John Stasko
stasko@cc.gatech.edu
Room 253 College of Computing
894-5617
Office hours: MWF 3-4
Teaching Assistant:
Ion Mandoiu
mandoiu@cc.gatech.edu
Room 153 College of Computing
894-2573 [1]
Office hours: Thursday 12-1 [2]
Problem session: Monday 5-6, Room 102
[1]NOTE: This is a shared phone among a large number
of graduate students. Don't expect the person that answers to know
where your TA is.
[2]TA office hours are held in the TA's office, which is
a shared area with other students around the back of the first floor
of the CoC building.
You are expected to purchase the required text: Introduction to Algorithms, by Cormen, Leiserson and Rivest, McGraw-Hill, 1990. There is no excuse for ignorance of the assigned reading material.
An approximate syllabus appears below. Some changes should be expected. Any changes in reading assignments will be announced in class.
| Week (approx) | Reading | Topics |
|---|---|---|
| 1 | 1 | Introduction to the design and analysis of algorithms. |
| 2 | 2 and 3 | Measuring the asymptotic growth of functions. The basic techniques for manipulating bounded summations. |
| 3 | 4.1-4.3 | Solving recurrence relations. |
| 4 | 5 | The basic structures of computing: sets, relations, functions, graphs and trees. |
| 5 | Above | Midterm (Jan 31) |
| 6 | 7 and 8 | Basic sorting methods: Heapsort and quicksort. |
| 7 | 16 and 17.1-17.3 | Techniques for problem solving: dynamic programming and greedy heuristics. |
| 8 | 23 | Elementary graph algorithms. |
| 9 | 24 and 25 | Minimum spanning trees. Single-source shortest paths. |
| 10 | 34 | String matching algorithms. |
| 11 | All above | Final Examination: week of March 11-15. |
Students are expected to attend class, to do their own work at all times and to follow the university's codes of academic conduct. Cases of suspected collaboration or cheating will be immediately forwarded to the Dean of Student Affairs, and will be pursued to resolution. This is an unpleasant process for all involved, so please do not put yourself in this situation.
Students are expected to conduct themselves in a professional manner-this entails showing up for exams at the appointed time. Late make-up exams will not be given, so beware of circumstances such as ``My alarm didn't go off,'' or ``I thought the exam was Thursday.'' If some form of prior commitment does not allow a student to take an exam at the given time, PRIOR arrangements should be made with the instructor.
Extra work, after the quarter, is not allowed to ``bring up'' a grade. A student's grade shall be earned from their performance solely on the quarter's assignments.
Grading is determined by a quarter long accumulation of points, weighed in percentage as stated for each assignment or exam. Determinations of the individual category breakdowns will be determined by looking for gaps or clumps in the final averages.
| Midterm | January 31 | 20% | Chapters 1-5 |
| Final | week of March 11-15 | 35% | All of the above and 7-8,16-17,23-25,30,33,34 |
Homework format: All assignments must be turned in on 8.5" x 11" paper (no tear outs from spiral bound notebooks), stapled in the upper left hand corner, and clearly labeled in the upper righthand corner of the front with your name. Assignments which do not meet this format are subject to penalty.
Homework Due Date: Homework will be assigned just about each week and will be due the Wednesday of the following week at the beginning of class. Turning in assignments late is strongly discouraged and will be penalized heavily (probably half off).
Homework Grading: A simplified grading scheme is be used. Each problem will graded from 0 to 5 points (unless otherwise specified).
Quibbling over homework grades is not recommended. More specifically: do not complain about your grade on a homework assignment unless you are sure that there is a big discrepancy in what has been judged and what is deserved. Also, do not seek a change of grade involving only a point or two for the whole assignment; it honestly isn't that critical for such small differences. (Exception: simple mis-totaling of the overall grade for the assignment.)
Overall Homework Grade: The overall homework grade is computed by curving the SUM of all assignments. During the quarter, preliminary calculations will be given to indicate your grade up to that point. The final grade depends on all the assignments taken together. The written homework will count for 28% of your total grade.
Visualizations must be turned in electronically. To be on time, the electronic submission must be done before the start of class on the due date. Programs can be late a maximum of 1 class period. Each animation will be evaluated on a scale of 0 to 10 points. A late program will have its score reduced by 2 points. This system is designed to strongly encourage on-time submissions. Note: It is amazingly easy to discover "duplicate" programs.
| Component | Non-graduating | Graduating |
|---|---|---|
| Written HWs | 25% | 35% |
| Algo. visualizations | 17% | 30% |
| Midterm Exam | 20% | 35% |
| Final exam | 35% |