Duke University
COMPSCI 330
Introduction to the Design and Analysis of Algorithms
Spring 2021
Overview
Algorithms are a cornerstone of the computational sciences and the need for efficient algorithms is ubiquitous in modern technology. However, the primary goals of algorithm design, the resources that need to be optimized, and even the model of computation varies widely between application areas. In this course, we will study some of the fundamental principles of algorithm design that appear in multiple areas and have had broad impact. In addition, we will focus on the mathematical tools that are frequently used in the theoretical analysis of algorithms, and study how such analysis, in turn, influences algorithm design. The course will be at an undergraduate level.
Course Staff
The email address to reach the course staff is compsci330-staff@cs.duke.edu We prefer that you use this email address or Piazza unless your query/request is specifically for one of the members of the course staff. In the latter case, please use the relevant email address(es) below.
Instructors
Debmalya Panigrahi debmalya@cs.duke.edu
Teaching Associate
Kate O'Hanlon cco9@duke.edu
Graduate Teaching Assistants (TAs)
Undergraduate Teaching Assistants (UTAs)
Syllabus
Introduction
History of Algorithms
Asymptotic and Worst-case Analysis
Basic Algorithm Design Techniques
Divide and Conquer
Greedy Algorithms
Dynamic Programming
Graph Algorithms
Graph Representations
Graph Traversal and Applications
Shortest Path
Minimum Spanning Tree
Network Flows
Randomized Algorithms
Monte Carlo and Las Vegas Algorithms
Hashing
Linear Programming
Design of Linear Programs
Solving Linear Programs (basics)
Linear Programming Duality
Intractability
NP-completeness
Polynomial-time Reductions
Approximation Algorithms