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

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

    • 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
  • Disjoint Sets
  • Sorting and Ordering
  • Heapsort
  • Quicksort
  • Linear-Time Sort
  • Selection
  • Design Techniques
  • Divide and Conquer
  • Dynamic Programming
  • Greedy Algorithms
  • Graph Algorithms
  • Randomized Algorithms
  • Approximation Methods
    • 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)


    • Errata for Textbook

    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.