Duke Logo

Chittaranjan Tripathy


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

Course Description

This undergraduate course, which is also colisted as a graduate level course for non-CS students (e.g. from Electrical and Computer Engineering, Computational Biology and Bioinformatics, Fuqua [Business] School), 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. This 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 and Number Theoretic Algorithms: polynomial multiplication, FFT, polynomial identity testing, 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

    Sudhanshu Garg
    email: sgarg AT cs dot duke dot edu
    UTA

    Alessio Santoro
    email: alessio DOT santoro AT duke dot edu
    Lectures

    LSRC D106, Wed.Fri 10:05AM-11:20AM
    Recitations

    LSRC D106, Mon 10:05AM-11:20AM
    Office Hours

    Chittu: LSRC D301, Wed 3:30PM-4:30PM, Thu 11:30AM-12:30PM
    Sudhanshu: LSRC D229, Wed 5:00PM-6:00PM, Thu 5:00PM-6:00PM
    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. Duke Honor Code applies to all the work you submit for evaluation.
    Writing and Submitting Assignments

    You are strongly encouraged to use LaTeX or other good word processor 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.
    Course Page, Email, Feedback

    Please check the course homepage frequently for any announcements, supplemental notes, readings, homework, etc. Important announcements will be sent by email. The following email id reaches every one in the class including the TAs and the instructor: compsci330 AT cs dot UniversityName dot edu. Please use this for posting general comments meant to be read by everyone in the class. Please use the instructor's or the TA's email id for specific questions. We welcome your suggestions and feedback on all aspects of the course. Your suggestions will improve the quality of the course. Please do not hesitate to provide your suggestions either in person, or via anonymous feedback.

    Lecture Schedule and Homeworks

    The schedule below is tentative (clearly not final before the day of the corresponding lecture). We will plan the individual lectures on weekly basis. The individual lectures will be added/modified/re-prioritized 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 Aug 29, Wednesday Introduction and Overview
    Administrativia
    History of Algorithms
    Models of Computation
    [DPV:0]
    L02 Aug 31, Friday Asymptotic Notation
    Solving Recurrences
    Handwritten Note (L02)
    [DPV:0,2] [CLRS:3,4]
    For background on induction: [Er:Induction]
     
    Week 2 R01 Sep 03, Monday More on Solving Recurrences [DPV:2] [CLRS:4]
    L03 Spe 05, Wednesday Solving Linear Recurrences
    Homogeneous
    Inhomogeneous
    Handwritten Note (L03)
    [DPV:0]
    L04 Sep 07, Friday Homework 01 out Divide-and-Conquer Algorithms
    Merge sort
    Powering a number
    Computing nth Fibonacci number
    Matrix multiplication
       – Naive algorithms
       – Strassen's algorithm
    Handwritten Note (L04)
    [DPV:2] [CLRS:4]
     
    Week 3 R02 Sep 10, Monday Problems on recurrences and Divide-and-conquer algorithms Handwritten Note (L05)
    [DPV:2] [CLRS:4]
    L05 Sep 12, 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 Sep 14, Friday Homework 01 due Fast Fourier Transform (FFT)
    Application of FFT to polynomial multiplication
    Handwritten Note (L06)
    Examples
    [DPV:2] [CLRS:30]
     
    Week 4 R03 Sep 17, Monday Problems on polynomials and FFT [DPV:2] [CLRS:30]
    L07 Sep 19, Wednesday Divide-and-Conquer in Computational Geometry
    Convex hulls in 2D
    [DVP:2] [CLRS:33]
    [additional notes given in class]
    L08 Sep 21, Friday Homework 02 out Divide-and-Conquer in Computational Geometry
    Convex hulls in 2D...
    Two Other Algorithms
    Graham Scan
    Jarvis's march (gift wrapping)
    [CLRS:12,13] [Ed:7]
     
    Week 5 R04 Sep 24, Monday Problems on convex hulls, iNTro to probability [CLRS:12,13] [Ed:7]
    L09 Sep 26, 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]
    L10 Sep 28, Friday Homework 02 due
    Homework 03 out
    Prune-and-Search: Linear-Time Selection
    Randomized
    Deterministic
    [DPV:2] [CLRS:9] [Ed:3]
     
    Week 6 R05 Oct 01, Monday Problems on randomized algorithms
    L11 Oct 03, Wednesday Polynomial Identity Testing
    L12 Oct 05, Friday
    Number Theoretic Algorithms: Basics, Euclid's Algorithm [DVP:1] [CLRS:31]
     
    Week 7 R06 Oct 08, Monday Homework 03 due Midterm1 review
    Oct 10, Wednesday First Midterm Exam Covers up to: Prune-and-Search: Linear-Time Selection [Exam Information and Cheat Sheet]
    L13 Oct 12, Friday Extended-Euclid Algorithm, Modular Exponentiation [DVP:1] [CLRS:31]
     
    Week 8 Oct 15, Monday No Class: Fall Break
    L14 Oct 17, Wednesday Primality Testing, RSA [DVP:1] [CLRS:31]
    Handwritten Note: Number Theoretic Algorithms
    L15 Oct 19, Friday Binary Search Trees, Red-Black Trees [CLRS:12,13] [Ed:7]
    Handwritten Note: BSTs and Red-Black Trees
     
    Week 9 R07 Oct 22, Monday Homework 04 out Skip Lists [Er:Skip Lists]
    Handwritten Note: Skip Lists
    L16 Oct 24, Wednesday Amortized Analysis [CLRS:17] [Er:Amortized Analysis]
    Handwritten Note: Amortized Analysis
    L17 Oct 26, Friday Priority Queue Data Structures
    Data Structures for Disjoint Sets
    Continuation of previous class
    [DPV:4] [CLRS:6,20,21]
     
    Week 10 R08 Oct 29, Monday Dynamic programming [DPV:6] [CLRS:15]
    Handwritten Note: Dynamic Programming
    L18 Oct 31, Wednesday Homework 04 due
    Homework 05 out
    Greedy Algorithms [DPV:5] [CLRS:16] i
    Handwritten Note: Greedy Algorithms
    L19 Nov 02, Friday Graphs
    Representations
    Directed Graphs
    Depth-first search (DFS)
    Properties of DFS
    [DPV:3] [CLRS:22]
    Handwritten Note: DFS
     
    Week 11 R09 Nov 05, Monday Graphs Continued...
    Topological sort
    Strongly connected components
    [DPV:3,5] [CLRS:15,22]
    Handwritten Note:SCC
    L20 Nov 07, Wednesday Homework 05 due Minimum Spanning Tree Algorithms
    Two Greedy Algorithms: Prim's Algorithm and Kruskal's Algorithm
    [DPV:3] [CLRS:22]
    Handwritten Note: MST
    L21 Nov 09, Friday Homework 06 out Minimum Spanning Tree Algorithms Continued...
    Shortest Paths in Graphs
    [DPV:5] [CLRS:23]
     
    Week 12 R10 Nov 12, Monday Problems on MST and SP [DPV:3,5] [CLRS:15,22]
    L22 Nov 14, Wednesday Shortest Path Algorithms
    Bellman-Ford Algorithm
    Dijkstra's Algorithm
    Breadth-first search (BFS) as simplified Dijkstra's Algorithm
    [DPV:4,6] [CLRS:24,25]
    Handwritten Note: SSSP
    Nov 16, Friday Second Midterm Exam Covers L13-L21, R07-R10 [Exam Information and Cheat Sheet]
     
    Week 13 R11 Nov 19, Monday All-pairs Shortest Paths
    Floyd-Warshall algorithm
    Problems on shortest paths
    [DPV:4,6] [CLRS:24,25]
    Handwritten Note: APSP
    Nov 21, Wednesday No Class: Thanksgiving break
    Nov 23, Friday No Class: Thanksgiving break
     
    Week 14 R12 Nov 26, Monday Problems on shortest paths [DPV:8] [CLRS:34]
    L24 Nov 28, Wednesday Intractability and NP Completeness, Reductions [DPV:8] [CLRS:34]
    L25 Nov 30, Friday Homework 06 due
    Homework 07 out
    More on Reductions [DPV:9] [CLRS:35]
     
    Week 15 R13 Dec 03, Monday Problems on Reductions
    L26 Dec 05, Wednesday Coping with NP-Completeness
    Approximation Algorithms
    [DPV:8] [CLRS:34]
    L27 Dec 07, Friday Homework 07 due Approximation Algorithms...
    Review of the Course
    [DPV:9] [CLRS:35]
     
    Week 16 Satruday Dec 15
    2:00 PM - 5:00 PM
    Also see this
    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.

    For background material in discrete mathematics and writing proofs, the following material can be useful:

    [LLM] E. Lehman, F. T. Leighton, and A. R. Meyer. Mathematics for Computer Science (MIT 6.042) . 2012.

    [Ro] K. H. Rosen. Discrete Mathematics and Its Applications. 7th Edition; McGraw-Hill; 2011.

    [Ve] D. J. Velleman. How to Prove It: A Structured Approach. 2nd Edition; Cambridge University Press; 2006.