# CS 3158 Design and Analysis of Algorithms

### Fall 1998 College of Computing 102 MWF 3:00-4:00

Catalogue Description:
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

## General Information

The goals of this course are to facilitate the students developing a well-organized understanding of the design and analysis of algorithms. After this course, students should be able to
• 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.

## Grading

Your final grade is made up of two major components, exams and homework, and one minor component, class participation. Weighting of these components is described below.

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.

### Examinations

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 Assignments

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.

### Animation Projects

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.

### Class Participation

Reading assignments will be specified for each week. You are expected to come to class prepared - that is, having read and having made an attempt to understand the material. You should be ready to discuss the material covered in the lectures and reading. Good class participation has the potential to "bump up" a borderline grade.

### Summary

Component Non-graduating Graduating
Written HWs 24% 32%
Algo. visualizations 17% 27%
Midterm Exam 24% 41%
Final exam 35%

## Disclaimer

The professor reserves the right to modify any of these plans as need be during the course of the class.

### Contact Information:

John Stasko
stasko@cc.gatech.edu
College of Computing
Georgia Institute of Technology
Atlanta, GA 30332-0280