CS 330 • Spring 2023

INTRO TO DESIGN & ANALYSIS OF ALGORITHMS

Time: Spring 2023, Tues, Thurs: 1:45-3:00pm
Location: Gross Hall 107

image01

Instructors

Pankaj Agarwal

Pankaj Agarwal

Professor of Computer Science and Mathematics

Website
Office Hours:
Mondays: 2:00 PM - 3:00 PM via Zoom
Thursdays: 11:00 AM - Noon in LSRC D214A

Brandon Fain

Brandon Fain

Assistant Professor of the Practice of Computer Science

Website
Office Hours:
(Hybrid, via Zoom or in LSRC D104)
Tuesdays: 11:00 AM - Noon
Thursdays: 3:30 PM - 4:30 PM

Kate O'Hanlon

Kate O'Hanlon

Lecturer

Office Hours: TBA

Teaching Assistants

Please see Staff page.

Contact Information

Please see the Communication Policy.

Course Synopsis

This undergraduate course covers techniques for designing and analyzing algorithms and data structures
for a wide range of problems. Topics include:

Design techniques:

Divide-and-conquer, greedy algorithms, dynamic programming, local search, and randomization

Data structures:

Balanced binary tree, hashing

Graph algorithms:

Graph traversal, strongly connected components, shortest path, minimum spanning tree, max flows and minimum cuts, matching

Optimization:

Linear programming, duality, gradient descent

Large scale computing:

Streaming, sketching, minimum spanning tree, parallel and distributed algorithms, external memory algorithms

Intractability:

Easy and hard problems, decision problems, NP-Completeness, reducibility

Prerequisites

  • CPS 201
  • CPS 230
    or approved substitute courses
  • This course requires undergraduate background in data structures as well as a certain amount of mathematical sophistication.

Textbooks

  • [DPV] S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms. McGraw Hill, 2006
  • [Er]     J. Erickson, Algorithms, 2019

Reference Books

  • [CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2009.
  • [KT]      J. Kleinberg and E. Tardos, Algorithm Design. Addison Wesley, 2005
  • [RN]      S. Russell, Artificial intelligence: a modern approach. Pearson Education, Inc., 2010.
  • [Ph]      J. Phillips, Mathematical foundations for data analysis. Springer, 2021.
  • [Roth1982]   A. Roth, The economics of matching: Stability and incentives. Mathematics of operations research 7.4 (1982): 617-628, 1984.
  • [BV]   S. Boyd and L. Vandenberghe, Convex optimization. Cambridge University Press, 2004.
  • [CY]   G. Cormode and K. Yi, Small Summaries for Big Data. Cambridge University Press, 2020.

Grading

  • Two midterm exams: 25%
    Final Exam: 25%
    Both midterms and final are in-class closed-book exams.
  • Assignments (best 6 out of 8): 25%
  • Project: 15%
  • Recitation: 5%
  • Class Exercises: 5%
Duke Computer Science

© 2022 Theme by GraphBerry