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
MW 12:30pm - 1:45pm, SN 014
Regular Office Hours: Mon/Wed 2:00pm-3:00pm
- TA: Kok-Lim Low
(SN323, 962-1918, lowk@cs.unc.edu;
Office Hours: Wed 2-3:00pm & Thur 3-5:00pm)
- 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 (Jan. 6, 1999)
Asymptotic Notation, Summation, D&C (Jan. 11, 1999)
Recurrence (Part I) (Jan. 13, 1999)
MLK JR. DAY (no class) (Jan. 18, 1999)
Recurrence (Part II) (Jan. 20, 1999)
Probability (Jan. 25, 1999)
Intro to Sorting (Jan. 27, 1999)
HeapSort (Feb. 1, 1999)
QuickSort (Feb. 3, 1999)
Linear-Time Sort (Feb. 8, 1999)
Selection (Feb. 10, 1999)
Hash Tables (Feb. 15, 1999)
Hash Tables (Feb. 17, 1999)
Binary Search Trees (Feb. 22, 1999)
Red-Black Trees (I) (Feb. 24, 1999)
R-B Trees (II) & Graph Representations (March 1, 1999)
A Case Study (March 3, 1999)
SPRING BREAK (March 8-12, 1999)
Elementary Graph Algorithms (I) (March 15, 1999)
Midterm Review (March 17, 1999)
Elementary Graph Algorithms (II) (March 22, 1999)
Midterm (March 24, 1999)
Graph Algorithms (March 29, 1999)
Greedy Algorithms (March 31, 1999)
Minimum Spanning Trees (Apr. 5, 1999)
Kruskal's & Prim's Algorithms (Apr. 7, 1999)
Shortest Paths & Dijkstra's Algorithm (Apr. 12, 1999)
Dynamic Programming (I) (Apr. 14, 1999)
Dynamic Programming (II) (Apr. 19, 1999)
Algorithms in Real World (Apr. 21, 1998)
In-Class Review Exercises (Apr. 26, 1998)
Comprehensive Review (Apr. 28, 1999)
Grading
The class grade of each student is determined by
Homework: 30%
Quizzes: 15%
Midterm: 20%
Final: 35%
Class Participation: Extra Credits
Homework Assignments
Homework 1 (due on Jan. 27, 1999)
Homework 2 (due on Feb. 17, 1999)
Homework 3 (due on Mar. 17, 1999)
Homework 4 (due on Apr. 12, 1999)
Homework 5 (due on Apr. 28, 1999)
Bonus Course Project (due on Apr. 30, 1999)
Examinations
Quiz #1 (Jan. 27, 1999)
Quiz #2 (Feb. 15, 1999)
Practice Midterm/Quiz #3 (Mar. 15-17, 1999)
Midterm (March 24, 1999)
Quiz #4 (April 5, 1999)
Practice Final/Quiz #5 (April 26, 1999)
Final (4:00-7:00pm, May 4, 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 (Jan. 6, 1999)
Solutions to In-Class Exercises (Jan. 25, 1999)
Notes on Elementary Sorting Methods (Jan. 27, 1999)
Notes on Articulation Points and Biconnected Components (March 29, 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.