Duke Logo

Chittaranjan Tripathy


[ Announcements | Administration | Lecture Schedule and Homeworks | Solutions | Additional Readings]

Course Description

This undergraduate course covers the basic techniques for designing algorithms and data structures for a wide range of problems, and analyzing their time and space complexity. The emphasis of this course is on problem solving, algorithm design and analysis, not on programming. The course covers the following topics in-depth:

  • Algorithm Design Techniques: Divide-and-conquer, recurrence relations, prune and search, greedy algorithms, dynamic programming, randomization
  • Data Structures: Binary search tree, red-black tree, skip list, hashing, union-find, amortization
  • Graph Algorithms: Graph search, minimum spanning tree, shortest path
  • Geometric Algorithms: Closest pair, Convex hull
  • Algebraic Algorithms: polynomial multiplication, FFT, primality testing, cryptography and RSA
  • Intractability: NP-Completeness, Approximation algorithms

  • Announcements


    Administration

    Instructor

    Chittaranjan Tripathy (please call me Chittu)
    email: chittu AT cs dot duke dot edu
    TA

    No TA
    Lectures

    LSRC D106, Mon.Tue.Wed.Thu 2:00PM-3:15PM
    Recitations

    LSRC D106, Fri 2:00PM-3:15PM
    Office Hours

    LSRC D240, Tue.Wed 3:30PM-4:30PM
    Textbooks

    Required:    [DPV] Algorithms. S. Dasgupta, C. Papadimitriou and U. Vazirani.  
    Optional:    [CLRS] Introduction to Algorithms, Third Edition. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.  

    Prerequisites

    Either CPS 201 and 230, or equivalent courses, or prior knowledge of discrete mathematics, probability, and programming; else, talk to the instructor.

    Workload and Grading

    Class Interaction. [5 points]
    Weekly Homework Assignments. [30 points]
    First In-class Closed-book Midterm Exam. [15 points]
    Second In-class Closed-book Midterm Exam. [15 points]
    In-class Closed-book Final Exam. [35 points]

    Late Homework Policy

    No credits for late submissions.
    Collaboration on Homework Assignments and the Duke University Honor Code

    You will learn the most if you solve as many extra problems as you can. All homework assignment solutions submitted for grading purpose should be your own. You are encouraged to form small groups to discuss and solve the problems from the textbooks or homework assignments, but you must write up your own solutions. Please indicate clearly in your solution sheet who you collaborated with, or what other written material (not listed in the course website) you have consulted, in order to solve each homework problem. You may not consult solutions on the internet or any other electronic sources.
    Writing and Submitting Assignments

    You are strongly encouraged to use LaTeX or MS-Word for typing the solutions to the assignments, and submit them in PDF or PS file format. If you prefer to hand-write them, then write the solutions clearly and legibly. Please note that short and to-the-point answers often get more credits than long and rambling answers.

    Lecture Schedule and Homeworks

    We will plan the individual lectures on weekly basis. The individual lectures will be added (weekly) as the course progresses. Please check back often to get the latest schedule.

    Week, Lecture(L)/Recitation(R)
    and Date

    Homework Due
    & Exams

    Topics Covered/To be Covered

    References/Readings

     
    Week 1 L01 May 15, Wednesday Introduction and Overview
    Administrativia
    History of Algorithms
    Models of Computation
    [DPV:0]
    L02 May 16, Thursday Asymptotic Notation
    Solving Recurrences
    [DPV:0,2] [CLRS:3,4]
    For background on induction: [Er:Induction]
    R01 May 17, Friday More on Solving Recurrences [DPV:2] [CLRS:4]
     
    Week 2 L03 May 20, Monday Solving Linear Recurrences
    Homogeneous
    Inhomogeneous
    [DPV:0]
    L04 May 21, Tuesday Divide-and-Conquer Algorithms
    Merge sort
    Powering a number
    Computing nth Fibonacci number
    Matrix multiplication
       – Naive algorithms
       – Strassen's algorithm
    [DPV:2] [CLRS:4]
    L05 May 22, Wednesday Integer Multiplication
    Naive algorithms
    Karatsuba multiplication
    Toom-Cook generalization
    Polynomial Multiplication
    Naive algorithms
    Divide-and-conquer polynomial multiplication
    Introduction to Fast Fourier Transform (FFT)
    [DPV:2] [CLRS:30]
    L06 May 23, Thursday Fast Fourier Transform (FFT)
    Application of FFT to polynomial multiplication
    [DPV:2] [CLRS:30]
    R02 May 24, Friday Homework 01 out FFT Continued... [DPV:2] [CLRS:30]
     
    Week 3 May 27, Monday No Class Today
    L07 May 28, Tuesday Divide-and-Conquer in Computational Geometry
    Convex hulls in 2D
    [CLRS:33]
    [additional notes given in class]
    L08 May 29, Wednesday Randomized Algorithms
    Las Vegas
    Monte Carlo
    Atlantic City
    Quicksort
    Deterministic
    Randomized
    Analysis of running time
    Lower Bounds for Comparison-Based Sorting Algorithms
    [DPV:2] [CLRS:7,8] [Er:Lower Bounds]
    L09 May 30, Thursday Prune-and-Search: Linear-Time Selection
    Randomized
    Deterministic
    [DPV:2] [CLRS:9] [Ed:3]
    R03 Jun 31, Friday Homework 01 due
    Homework 02 out
    Binary Search Trees, Red-Black Trees [CLRS:12,13] [Ed:7]
     
    Week 4 L11 Jun 03, Monday Skip Lists [Er:Skip Lists]
    L12 Jun 04, Tuesday Amortized Analysis [CLRS:17] [Er:Amortized Analysis]
    Jun 05, Wednesday First Midterm Exam Covers L01-L09, R01-R02 [Exam Information and Cheat Sheet ]
    L13 Jun 06, Thursday Priority Queue Data Structures
    Data Structures for Disjoint Sets
    [DPV:4] [CLRS:6,20,21]
    R04 Jun 07, Friday Homework 02 due
    Homework 03 out
    Dynamic Programming [DPV:6] [CLRS:15]
     
    Week 5 L14 Jun 10, Monday Greedy Algorithms [DPV:5] [CLRS:16]
    L15 Jun 10, Tuesay Graphs
    Representations
    Directed Graphs
    Breadth-first search
    Depth-first search
    [DPV:3] [CLRS:22]
    L16 Jun 12, Wednesday Graphs Continued...
    Topological sort
    Strongly connected components
    [DPV:3] [CLRS:22]
    L17 Jun 13, Thursday Minimum Spanning Tree Algorithms [DPV:5] [CLRS:23]
    R05 Jun 14, Friday Homework 03 due
    Homework 04 out
    Shortest Path Algorithms [DPV:4,6] [CLRS:24,25]
     
    Week 6
    Jun 17, Monday Second Midterm Exam Covers L10-L17, R03-R04 [Exam Information and Cheat Sheet]
    L18 Jun 18, Tuesay Shortest Path Algorithms Continued... [DPV:4,6] [CLRS:24,25]
    L19 Jun 19, Wednesday Intractability and NP Completeness [DPV:8] [CLRS:34]
    L20 Jun 20, Thursday Intractability and NP Completeness Continued... [DPV:8] [CLRS:34]
    R06 Jun 21, Friday Homework 04 due Coping with NP-Completeness [DPV:9] [CLRS:35]
     
    Week 7
    L21 Jun 24, Monday Advanced Topics
    Review of the Course
    Jun ???, ??? Final Exam Covers Everything [Exam Information and Cheat Sheet]


    Solutions to Homework Assignments and Exam Problems

    Graded homeworks and exams, and sample solutions will be provided in class in hard-copy format.

    Readings: Reference Books, Lecture Notes and Videos

    [CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2009.

    MIT Video Lectures on Introduction to Algorithms Course

    [KT] J. Kleinberg and Éva Tardos. Algorithm Design. Addison Wesley, 1 edition, 2006.

    [AHU] A. Aho, J. Hopcroft, and J. Ullman. Design and Analysis of Algorithms. Addison Wesley, 1974.

    [Ed] H. Edelsbrunner. CPS230 Lecture Notes. Duke University, 2008.

    [Er] J. Erickson. CPS473G: Algorithms Lecture Notes. UIUC.

    [Ta] R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial Mathematics, 1987.

    [BB] G. Brassard and P. Bratley. Fundamentals of Algorithmics. Prentice Hall; 1996.