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
Background Survey Sheet is available
HERE
- TA: Suddha Basu
(SN008, 962-xxx, skbasu@cs.unc.edu;
Office Hours: Monday/Wednesday 2:00-3:30pm)
- Extra Help Sessions: Tuesday or Thursday at 5pm in SN014
- Prerequisites: Discrete Mathematics (MATH 81) and Data
Structures (COMP 121)
- Textbook: Introduction to Algorithms, 2nd Edition
by Cormen, Leiserson, Rivest, and Stein. 2002, MIT Press & McGraw-Hill
Publishing, ISBN#0-07-013151-1.
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 30, 2005)
Asymptotic Notation, Summation, D&C (Sept 1, 2005)
Recurrence (Part I) (Sept 6, 2005)
Recurrence (Part II) (Sept 8, 2005)
Recurrence (Part III) (Sept 13, 2005)
Probability (Sept 15, 2005)
Sorting (Sept 20, 2005)
Heapsort (Sept 22, 2005)
Quicksort (Sept 27, 2005)
Linear-Time Sort (Sept 29, 2005)
Linear-Time Sort (Oct 4, 2005)
Selection (Oct 6, 2005)
Algorithms in Networking (Oct 11, 2005)
Hash Tables (Oct 13, 2005)
No Class (Make-up through Extended Classes) (Oct 18, 2005)
FALL BREAK (Oct. 20-23, 2005)
Hash Tables &
Binary Search Trees (Extended Class; Oct 25, 2005)
Red-Black Trees (Extended Class; (Oct 27, 2005)
Midterm Review (Nov 1, 2005)
In-class Midterm Exam (Nov 3, 2005)
Graph Representation & Elementary Graph Algorithms (I) (Nov 8, 2005)
Elementary Graph Algorithms (II) (Nov 10, 2005)
Graph Algorithms (III) & Greedy Algorithms
(Nov 15, 2005)
Greedy Algorithms (Nov 17, 2005)
Shortest Paths & Dijkstra's Algorithm (Nov 22, 2005)
THANKSGIVING BREAK (Nov 23-27, 2005)
Minimum Spanning Trees (Nov 29, 2005)
Kruskal's & Prim's Algorithm
and Dynamic Programming (I)
(Dec 1, 2005)
Dynamic Programming (I) (Dec 6, 2005)
Dynamic Programming (II) and
Review
(Dec 8, 2005)
Grading
The class grade of each student is determined by
Homework: 25%
Quizzes: 15%
Midterm: 20%
Final: 40%
Class Participation: 5% Extra Credit
Bonus Project: 5% Extra Credit
Homework Assignments
Homework 1 (due on Thursday, Sept 8, 2005)
Homework 2 (due on Tuesday, Sept 20, 2005)
Homework 3 (due on Thursday, Oct 6, 2005)
Homework 4 (due on Thursday, Oct 27, 2005)
Homework 5 (due on Thursday, Nov 17, 2005)
Homework 6 (due on Thursday, Dec 1, 2005)
Homework 7 (due on Monday, Dec 12, 2005)
Examinations
Quiz #1 (Tuesday, Sept 20, 2005)
Quiz #2 (Tuesday, Oct 4, 2005)
Quiz #3 (Tuesday, Oct 25, 2005)
Midterm (Thursday, Nov 3, 2005)
Quiz #4 (Thursday, Nov 17, 2005)
Quiz #5 (Tuesday, Dec 6, 2005)
Final (4:00pm-7:00pm on Thursday, Dec 15, 2005)
Extra Help Sessions
Thursday, September 08, 2005
Thursday, September 15, 2005
Thursday, September 29, 2005
Thursday, October 13, 2005
Tuesday, November 1, 2005
Tuesday, November 15, 2005 (SN011)
Tuesday, November 29, 2005 (SN011)
Thursday, December 8, 2005 (SN011)
Monday, December 12, 2005, 3:30pm-5:00pm (SN115)
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 30, 2005)
Solutions to
Exercises Given in Lecture 3 (September 6, 2005)
Solutions to
Exercises Given in Lecture 4 (September 8, 2005)
Notes on
Sorting (October 4, 2005)
Practice Midterm (October 6, 2005)
Supplementary
Notes on Dynamic Programming (December 1-6, 2005)
Practice Final (December 8, 2005)
For more information, contact
Ming C. Lin,
lin@cs.unc.edu.
Copyright 2005.
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.