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:15pm or By Appointments


TA: David O'Brien (SN044, 962-1963, obrien@cs.unc.edu; Office Hours: MWF 10:05-11:00am & TR 2:30-3:25pm)
TA: Liang-Wei Su (SN044, 962-1953, lwsu@cs.unc.edu; Office Hours: MW 3:30-5:00pm)
Extra Help Sessions: Thursday 5:00-6:00pm & Friday 1:00-2:00pm 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
  • Lectures and Approximate Schedule
  • Grading
  • Homework Assignments
  • Examinations
  • Algorithm Animation
  • 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 19, 1999)
  • Asymptotic Notation, Summation, D&C (Aug 24, 1999)
  • Recurrence (Part I) (Aug 26, 1999)
  • Recurrence (Part II) (Aug 31, 1999)
  • Probability (Sept 2, 1999)
  • Intro to Sorting (Sept 7, 1999)
  • HeapSort (Sept 9, 1999)
  • QuickSort (Sept 14, 1999)
  • No Class due to Floyd (Sept 16, 1999)
  • Linear-Time Sort (Sept 21, 1999)
  • Selection (Sept 23, 1999)
  • Hash Tables (Sept 28, 1999)
  • Hash Tables & Binary Search Trees (Sept 30, 1999)
  • BSTs & Red-Black Trees (I) (Oct 5, 1999)
  • Red-Black Trees (II) (Oct 7, 1999)
  • Case Study (Oct 12, 1999)
  • FALL BREAK (Oct. 14-17, 1999)
  • Mid-Term Review (Oct 19, 1999)
  • Midterm Exam (Oct 21, 1999)
  • Graph Representation & Elementary Graph Algorithms (I) (Oct 26, 1999)
  • Elementary Graph Algorithms (II) (Oct 28, 1999)
  • More Graph Algorithms (Nov 2, 1999)
  • Greedy Algorithms (Nov 4, 1999)
  • Shortest Paths & Dijkstra's Algorithm (Nov 9, 1999)
  • Algorithms in Real World (Nov 11, 1998)
  • Minimum Spanning Trees (Nov 16, 1999)
  • Kruskal's & Prim's Algorithm (Nov 18, 1999)
  • Dynamic Programming (I) (Nov 23, 1999)
  • THANKSGIVING BREAK (Nov 24-28, 1999)
  • Dynamic Programming (II) (Nov 30, 1999)
  • Project Demos & Comprehensive Review (Dec 2, 1998)
  • Final Review Exercises (Dec 7, 1999)

    • Grading

    The class grade of each student is determined by
  • Homework: 30%
  • Quizzes: 15%
  • Midterm: 20%
  • Final: 35%
  • Class Participation: 5% Extra Credit
  • Bonus Course Project: 5% Extra Credit

    • Homework Assignments

  • Homework 1 (due on Tuesday, Aug 31, 1999)
  • Homework 2 (due on Tuesday, Sept 14, 1999)
  • Homework 3 (due on Tuesday, Sept 28, 1999)
  • Homework 4 (due on Tuesday, Oct 12, 1999)
  • Homework 5 (due on Tuesday, Nov 9, 1999)
  • Homework 6 (due on Tuesday, Nov 30, 1999)
  • Homework 7 (due on Thursday, Dec 2, 1999)

    • Examinations

  • Quiz #1 (Tuesday, Sept 7, 1999)
  • Quiz #2 (Thursday, Sept 23, 1999)
  • Quiz #3 (Thursday, Oct 7, 1999)
  • Midterm (Thursday, Oct 21, 1999)
  • Quiz #4 (Tuesday, Nov 16, 1999)
  • Quiz #5 (Tuesday, Nov 30, 1999)
  • Final (12:00-3:00pm, Thursday, Dec 16, 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 (August 19, 1999)
  • Solutions to Exercises Given in Lecture 3 (August 26, 1999)
  • Solutions to Exercises Given in Lecture 4 (August 31, 1999)
  • Notes on Elementary Sorting Methods (September 7, 1999)
  • Practice Midterm (October 12, 1999)
  • Notes on Articulation Points and Biconnected Components (November 2, 1999)
  • Supplementary Notes on Dynamic Programming (November 23, 1999)
  • Practice Final (November 23, 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.