Duke University
Duke University
COMPSCI 330
COMPSCI 330
Introduction to the Design and Analysis of Algorithms
Introduction to the Design and Analysis of Algorithms
Fall 2022
Fall 2022
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.
Email: debmalya@cs.duke.edu
Office hour: Wednesday 4-5 pm in LSRC D203
Email: cco9@duke.edu
Email: ruoxu.cen@duke.edu
Email: jinze.cui@duke.edu
Email: rajas.pandey@duke.edu
Email: lu.wang400@duke.edu
Eric Chai
Chavez Yi Wei Cheong
Zimeng Fan
Kevin Feng
Louis Hu
Nathan Huang
Vincent Li
Kegan Lovell
Kerry Lu
Billy Luqiu
Nathan Nguyen
Yunhong Shan
Matthew Wang
Yingjie Xu
Jeffrey Zhou
Xingyu/Jupiter Zhu
Cristal Zhu
Luke Zhuo
TA office hours are held 6PM-8PM Sunday-Thursday.
Here is the schedule with locations: https://docs.google.com/spreadsheets/d/e/2PACX-1vTQkXBSMGG6dgVYSeLhUaaLT3M2fJRy3Qq0RclX5bzv4SJ1FXqxUkonCMS9eIw0F7dvZq6-40wVrP0y/pubhtml
You are required to use the department queueing app OhHai for office hours. Instructions are here: https://docs.google.com/document/d/e/2PACX-1vQlpxZSpf6KdmONmbEBm6jTy313hqhuIgJCSVU6J4F2WKhBHg3ObPOfMlj6iV3QaLxTy25iei0lY1At/pub
Divide, Conquer, and Recombine, Recurrence relations, Memoization
Sorting Algorithms
Median-finding
Dynamic substructure, Recursive Formulation, Dynamic Programming Table, Iterative Implementation
Equivalence of Shortest Path in a DAG
Shortest Path Algorithms: Dijkstra's Algorithm, Bellman-Ford Algorithm
All-Pairs Shortest Paths: Floyd-Warshall algorithm
Interval Coloring, Interval Scheduling
Minimum Spanning Tree: Cut and Cycle Properties, Kruskal's Algorithm, Prim's Algorithm
Huffman coding
Depth-first-search, Kosaraju's algorithm for Strongly Connected Components
Breadth-first-search, Graph Distances
Maximum bipartite matching: Hopcroft-Karp algorithm
Maximum s-t flow and minimum s-t cut: Ford-Fulkerson algorithm
Linear Programming formulations, basics of simplex, ellipsoid, and interior point algorithms
Integer linear programs and relaxations
Linear programming duality, application to flows, cuts, and matchings
Birthday paradox, Coupon collector, Balls in bins processes
Las Vegas algorithms: Randomized quicksort
Monte Carlo algorithms: Karger's minimum cut algorithm
Universal Hashing
Basics of complexity classes P and NP, NP-completeness
Polynomial-time reductions
Combinatorial algorithms: maximal matching, vertex cover
Linear Programming: vertex cover, set cover