Old Well


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


Instructor: Ming C. Lin

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
  • Lectures and Approximate Schedule
  • Grading
  • Homework Assignments
  • Examinations
  • Extra Help Sessions
  • Additional Reference Materials

  • 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:
  • Algorithm Analysis
  • Asymptotic Notation
  • Recurrence Relation
  • Probability & Combinatorics
  • Proof Techniques
  • Inherent Complexity
  • Data Structures
  • Lists
  • Trees
  • Graphs
  • heaps
  • Hash Tables
  • Sorting and Ordering
  • Heapsort
  • Quicksort
  • Linear-Time Sort
  • Selection
  • Design Techniques
  • Divide and Conquer
  • Dynamic Programming
  • Greedy Algorithms
  • Graph Algorithms
  • Randomized Algorithms
  • 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)

  • Errata for Textbook


    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.