Design and Analysis of Algorithms

College of Computing 102

MWF 3:00-4:00

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
- 253 College of Computing
- 894-5617
- Office Hours MWF 2:30-3:00, 4:00-4:30, or by appt.
**Teaching Assistant**- Ashley Taylor
- 225A College of Computing
- 894-9389
- Office hours Tue Thu 1-2 (held on 1st floor)

General Info | Grading | Exams | HWs | Projects | Class Participation | Grading Summary | Disclaimer

- Evaluate algorithms based on their complexity and asymptotic growth rate.
- Develop recurrence relations summarizing algorithms' complexity.
- Solve those recurrence relations using a variety of methods.
- Know how to utilize the algorithmic methods of divide and conquer, dynamic programming, and greedy heuristics.
- Understand fundamental algorithms in sorting, graphs, and string matching.

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