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 100 and 102, 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 16, Wednesday Introduction and Overview
    Administrativia
    History of Algorithms
    Models of Computation
    [DPV:0]
    L02 May 17, Thursday Homework 01 out Asymptotic Notation
    Solving Recurrences
    [DPV:0,2] [CLRS:3,4]
    For background on induction: [Er:Induction]
    R01 May 18, Friday More on Solving Recurrences [DPV:2] [CLRS:4]
     
    Week 2 L03 May 21, Monday Solving Linear Recurrences
    Homogeneous
    Inhomogeneous
    [DPV:0]
    L04 May 22, 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 23, 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 24, Thursday Homework 01 due
    Homework 02 out Homework 02 out
    Fast Fourier Transform (FFT)
    Application of FFT to polynomial multiplication
    [DPV:2] [CLRS:30]
    R02 May 25, Friday FFT Continued... [DPV:2] [CLRS:30]
     
    Week 3 May 28, Monday No Class Today
    L07 May 29, Tuesday Divide-and-Conquer in Computational Geometry
    Convex hulls in 2D
    Closest pair of points in 2D
    [CLRS:33]
    [additional notes given in class]
    L08 May 30, 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 31, Thursday Homework 02 due
    Homework 03 out
    Prune-and-Search: Linear-Time Selection
    Randomized
    Deterministic
    [DPV:2] [CLRS:9] [Ed:3]
    R03 Jun 01, Friday Binary Search Trees, Red-Black Trees [CLRS:12,13] [Ed:7]
     
    Week 4 Jun 04, Monday First Midterm Exam Covers L01-L09, R01-R02 [Exam Information and Cheat Sheet ]
    L11 Jun 05, Tuesay Skip Lists [Er:Skip Lists]
    L12 Jun 06, Wednesday Amortized Analysis [CLRS:17] [Er:Amortized Analysis]
    L13 Jun 07, Thursday Homework 03 due
    Homework 04 out
    Priority Queue Data Structures
    Data Structures for Disjoint Sets
    [DPV:4] [CLRS:6,20,21]
    R04 Jun 08, Friday Dynamic Programming [DPV:6] [CLRS:15]
     
    Week 5 L14 Jun 11, Monday Greedy Algorithms [DPV:5] [CLRS:16]
    L15 Jun 12, Tuesay Graphs
    Representations
    Directed Graphs
    Breadth-first search
    Depth-first search
    [DPV:3] [CLRS:22]
    L16 Jun 13, Wednesday Graphs Continued...
    Topological sort
    Strongly connected components
    [DPV:3] [CLRS:22]
    L17 Jun 14, Thursday Homework 04 due
    Homework 05 out
    Minimum Spanning Tree Algorithms [DPV:5] [CLRS:23]
    R05 Jun 15, Friday Shortest Path Algorithms [DPV:4,6] [CLRS:24,25]
     
    Week 6
    Jun 18, Monday Second Midterm Exam Covers L10-L17, R03-R04 [Exam Information and Cheat Sheet]
    L18 Jun 19, Tuesay Shortest Path Algorithms Continued... [DPV:4,6] [CLRS:24,25]
    L19 Jun 20, Wednesday Intractability and NP Completeness [DPV:8] [CLRS:34]
    L20 Jun 21, Thursday Homework 05 due
    Homework 06 out (will not be graded)
    Intractability and NP Completeness Continued... [DPV:8] [CLRS:34]
    R06 Jun 22, Friday Coping with NP-Completeness [DPV:9] [CLRS:35]
     
    Week 7
    L21 Jun 25, Monday Advanced Topics
    Review of the Course
    Jun 28, Thursday 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.