Department of Computer Science
College of Arts and Sciences
The University of North Carolina at Chapel Hill
COMP122: Algorithms and Analysis
COMP 122: ALGORITHMS AND ANALYSIS
TR 3:30pm - 4:45pm, SN 014
Office Hours: TR 2:00pm-3:15pm or By Appointments
- TA: David
O'Brien (SN044, 962-1963, obrien@cs.unc.edu;
Office Hours: MWF 10:05-11:00am & TR 2:30-3:25pm)
- TA: Liang-Wei
Su (SN044, 962-1953, lwsu@cs.unc.edu;
Office Hours: MW 3:30-5:00pm)
- Extra Help Sessions: Thursday 5:00-6:00pm & Friday
1:00-2:00pm in SN014
- Prerequisites: Discrete Mathematics (MATH 81) and Data
Structures (COMP 121)
- Textbook: Introduction to Algorithms
by Cormen, Leiserson and Rivest. 1990, McGraw-Hill Publishing, Inc.
ISBN#0-07-013143-0.
Course Overview:
The goal of this class is to present fundamental problem-solving techniques,
for designing efficient computer algorithms, proving their correctness,
and analyzing their performance (e.g. running time, storage requirement, etc.).
We will study asymptotic complexity and mathematical analysis of algorithms,
design techniques, data structures, and possible applications.
The list of topics includes:
Each topic will be motivated by an interesting example, then studied
about its basic concepts and accompanied by analysis.
Lectures and Approximate Schedule
Here is a list of lecture topics (subject to
changes). Schedule and information on each topic (e.g. readings, web
pointers) will be added during the semester before each class.
Course Overview (Aug 19, 1999)
Asymptotic Notation, Summation, D&C (Aug 24, 1999)
Recurrence (Part I) (Aug 26, 1999)
Recurrence (Part II) (Aug 31, 1999)
Probability (Sept 2, 1999)
Intro to Sorting (Sept 7, 1999)
HeapSort (Sept 9, 1999)
QuickSort (Sept 14, 1999)
No Class due to Floyd (Sept 16, 1999)
Linear-Time Sort (Sept 21, 1999)
Selection (Sept 23, 1999)
Hash Tables (Sept 28, 1999)
Hash Tables & Binary Search Trees (Sept 30, 1999)
BSTs & Red-Black Trees (I) (Oct 5, 1999)
Red-Black Trees (II) (Oct 7, 1999)
Case Study (Oct 12, 1999)
FALL BREAK (Oct. 14-17, 1999)
Mid-Term Review (Oct 19, 1999)
Midterm Exam (Oct 21, 1999)
Graph Representation & Elementary Graph Algorithms (I) (Oct 26, 1999)
Elementary Graph Algorithms (II) (Oct 28, 1999)
More Graph Algorithms (Nov 2, 1999)
Greedy Algorithms (Nov 4, 1999)
Shortest Paths & Dijkstra's Algorithm (Nov 9, 1999)
Algorithms in Real World (Nov 11, 1998)
Minimum Spanning Trees (Nov 16, 1999)
Kruskal's & Prim's Algorithm (Nov 18, 1999)
Dynamic Programming (I) (Nov 23, 1999)
THANKSGIVING BREAK (Nov 24-28, 1999)
Dynamic Programming (II) (Nov 30, 1999)
Project Demos & Comprehensive Review (Dec 2, 1998)
Final Review Exercises (Dec 7, 1999)
Grading
The class grade of each student is determined by
Homework: 30%
Quizzes: 15%
Midterm: 20%
Final: 35%
Class Participation: 5% Extra Credit
Bonus Course Project: 5% Extra Credit
Homework Assignments
Homework 1 (due on Tuesday, Aug 31, 1999)
Homework 2 (due on Tuesday, Sept 14, 1999)
Homework 3 (due on Tuesday, Sept 28, 1999)
Homework 4 (due on Tuesday, Oct 12, 1999)
Homework 5 (due on Tuesday, Nov 9, 1999)
Homework 6 (due on Tuesday, Nov 30, 1999)
Homework 7 (due on Thursday, Dec 2, 1999)
Examinations
Quiz #1 (Tuesday, Sept 7, 1999)
Quiz #2 (Thursday, Sept 23, 1999)
Quiz #3 (Thursday, Oct 7, 1999)
Midterm (Thursday, Oct 21, 1999)
Quiz #4 (Tuesday, Nov 16, 1999)
Quiz #5 (Tuesday, Nov 30, 1999)
Final (12:00-3:00pm, Thursday, Dec 16, 1999)
Additional Reference Materials
Other reference books:
The Design and Analysis of Computer Algorithms,
by Aho, Hopcroft and Ullman.
Algorithms, by Sedgewick
Algorithmics -- Theory & Practice, by Brassard & Bratley
Writing Efficient Programs, by Bentley
The Science of Programming, by Gries
The Craft of Programming, by Reynolds
Handouts and lecture notes used in class:
Course Syllabus (August 19, 1999)
Solutions to
Exercises Given in Lecture 3 (August 26, 1999)
Solutions to
Exercises Given in Lecture 4 (August 31, 1999)
Notes on Elementary Sorting Methods (September 7, 1999)
Practice Midterm (October 12, 1999)
Notes on Articulation Points and Biconnected Components (November 2, 1999)
Supplementary
Notes on Dynamic Programming (November 23, 1999)
Practice Final (November 23, 1999)
For more information, contact
Ming C. Lin,
lin@cs.unc.edu.
Copyright 1999.
Personal use of this material is permitted. However, permission to
reprint/republish this material for advertising or promotional purposes
or for creating new collective works for resale or redistribution to servers or
lists, or to reuse any copyrighted component of this work in other works
must be obtained from the author.
This material is presented to ensure timely dissemination of scholarly
and technical work. Copyright and all rights therein are retained by authors or
by other copyright holders. All persons copying this information are
expected to adhere to the terms and constraints invoked by each author's
copyright. In most cases, these works may not be reposted without the
explicit permission of the copyright holder.