CS 330 • Fall 2023

INTRO TO DESIGN & ANALYSIS OF ALGORITHMS

Time: Fall 2023, Mon & Wed: 1:25-2:40pm
Location: LSRC B101

image01

Instructors & Teaching Associates

Pankaj Agarwal

Professor of Computer Science and Mathematics

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

Brandon Fain

Assistant Professor of the Practice of Computer Science

Website | Email
Office Hours: TBA

Alex Chao

Teaching Associate

Email
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, dynamic programming, greedy algorithms, parallel algorithms, randomized algorithms

Graph algorithms:

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

Intractability:

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

Large scale computing:

Clustering, hashing, sketching, streaming, approximation algorithms

Prerequisites

CPS 201
CPS 230, equivalent or approved substitute courses
This course requires undergraduate background in data structures as well as a certain amount of mathematical sophistication. See more details about prerequisites and getting started.

Textbooks

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

Reference Books

[CY] G. Cormode and K. Yi, Small Summaries for Big Data. Cambridge University Press, 2020.
[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
[Ph] J. Phillips, Mathematical foundations for data analysis. Springer, 2021.

Grading

Exams Part 1: 25%
Exams Part 2: 25%
Assignments: 20%
Graded S/U (8 out of 10).
Case Study: 15%
1 deliverable.
Lecture Quizzes Participation: 9%
6 drops.
Recitation Participation: 5%
3 drops.
Course Surveys: 1%
2 total