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 | 7 and 8 | Basic sorting methods: Heapsort. Review for exam. |
6 | Above | Midterm (Oct. 26). Quicksort. |
7 | 16 | Techniques for problem solving: dynamic programming: MatrixChain, LCS |
8 | 17.1-17.3 | Techniques for problem solving: greedy heuristics. |
9 | 23 | Elementary graph algorithms. |
10 | 24 and 25 | Minimum spanning trees. Single-source shortest paths. |
11 | 34 | String matching algorithms. Misc topics. |
12 | All above | Final Examination: week of December 7-11. |
Below is a link to the actual day-by-day course conntent. Included are the actual lecture notes from the Xerox LiveBoard, plus the audio and video from class. You will need the RealPlayer audio/video internet play tool to hear the audio stream and see the video. Connect to get RealPlayer software.
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.
Two examinations are planned (see summary below). Most exam questions will reflect the material covered in lectures, the readings, and homework. It would be a good idea to study the exercises at the end of each section in preparing for an examination.
Midterm | October 26 | 20% | Chapters 1-5, 7-8 |
Final | week of December 7-11 | 35% | All of the above and 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 used. Each problem will be 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 24% of your total grade.
This quarter we will also be doing assignments that will help understand the algorithms presented throughout the course. You will be responsible for creating a visualization of a few important algorithms. For this, you will be using some graphics tools that will not require a background in computer graphics. Each assignment will have more details about the animations. This component is worth 17% of the 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 | 24% | 32% |
Algo. visualizations | 17% | 27% |
Midterm Exam | 24% | 41% |
Final exam | 35% |