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:00pm or By Appointments
- TA: Avneesh Sud
(SN373, 962-1849, sud@cs.unc.edu;
Office Hours: Tuesday 12:30pm-1:45pm; Wednesday 11:00am-12:15pm)
- Extra Help Sessions: Tuesday or Thursday at 5pm 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 22, 2000)
Asymptotic Notation, Summation, D&C (Aug 24, 2000)
Recurrence (Part I) (Aug 29, 2000)
Recurrence (Part II) (Aug 31, 2000)
Recurrence (Part III) & Probability (Sept 5, 2000)
Probability & Intro to Sorting (Sept 7, 2000)
Sorting (Sept 12, 2000)
Heapsort (Sept 14, 2000)
Quicksort (Sept 19, 2000)
Linear-Time Sort (Sept 21, 2000)
Linear-Time Sort (Sept 26, 2000)
Selection (Sept 28, 2000)
Hash Tables (Oct 3, 2000)
FALL BREAK (Oct. 5-8, 2000)
Hash Tables & Binary Search Trees (Oct 10, 2000)
Binary Search Trees (Oct 12, 2000)
Midterm Review(Oct 17, 2000)
Red-Black Trees (Oct 19, 2000)
In-Class Midterm (Oct 24, 2000)
Red-Black Trees & Graph Representations (Oct 26, 2000)
Elementary Graph Algorithms (I) (Oct 31, 2000)
Elementary Graph Algorithms (II) (Nov 2, 2000)
Graph Algorithms (III) & Greedy Algorithms
(Nov 7, 2000)
Greedy Algorithms (Nov 9, 2000)
Shortest Paths & Dijkstra's Algorithm (Nov 14, 2000)
Minimum Spanning Trees (Nov 16, 2000)
Kruskal's & Prim's Algorithm (Nov 21, 2000)
THANKSGIVING BREAK (Nov 23-26, 2000)
Dynamic Programming (I) (Nov 28, 2000)
Dynamic Programming (II) (Nov 30, 2000)
Algorithms in Real-World (Dec 5, 2000)
Final Review Exercises (Dec 7, 2000)
Grading
The class grade of each student is determined by
Homework: 30%
Quizzes: 15%
Midterm: 20%
Final: 35%
Class Participation: 5% Extra Credit
Bonus Project: 5% Extra Credit
Homework Assignments
Homework 1 (due on Thursday, August 31, 2000)
Homework 2 (due on Thursday, Sept 14, 2000)
Homework 3 (due on Thursday, Sept 28, 2000)
Homework 4 (due on Tuesday, Oct 17, 2000)
Homework 5 (due on Tuesday, Nov 21, 2000)
Homework 6 (due on Thursday, Nov 30, 2000)
Homework 7 (due on Thursday, Dec 7, 2000)
Examinations
Quiz #1 (Tuesday, Sept 12, 2000)
Quiz #2 (Thursday, Sept 28, 2000)
Midterm (Tuesday, Oct 19, 2000)
Quiz #3 (Thursday, Nov 2, 2000)
Quiz #4 (Thursday, Nov 16, 2000)
Final (4:00pm-7:00pm on Friday, Dec 15 & Tuesday, Dec 19, 2000)
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 22, 2000)
Solutions to
Exercises Given in Lecture 3 (August 29, 2000)
Solutions to
Exercises Given in Lecture 4 (August 31, 2000)
Practice Midterm (October 3, 2000)
Notes on Articulation Points and Biconnected Components (November XX, 2000)
Supplementary
Notes on Dynamic Programming (November 21, 2000)
Practice Final (November 30, 2000)
For more information, contact
Ming C. Lin,
lin@cs.unc.edu.
Copyright 2000.
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.