- A knowledge of python or some other programming language. All course examples will be in python.
Presents data structures and related algorithms, beginning with a brief review of dynamic memory allocation. Discusses the fundamental data structures in detail, including the abstract representation of algorithms, and implementation methods. Focuses on understanding the application of the abstract data structure and the circumstances that affect implementation decisions. Covers lists, stacks, queues, trees, hash tables, and graphs. Covers recursion and searching and sorting algorithms in detail. Emphasizes data abstraction and encapsulation in code design. Explores external storage structures, time permitting.
This is an introductory course in algorithms. The focus of this course is on learning algorithm design techniques for solving computational problems.
This course teaches techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics covered include sorting, search trees, heaps, hashing, divide-and-conquer, dynamic programming, amortized analysis, graph algorithms, shortest paths, network flow, randomized algorithms, data structures, approximation algorithms, and graph search.
We will cover theory as well as implement, simulate, and visualize algorithms using python. There will be weekly homework assignments, two in-class midterm exams, a final exam, and a research project.
- Get exposed to a range of computational problems that arise in very diverse applications
- Learn how to formulate problems precisely from somewhat informal descriptions
- Learn new algorithmic design techniques used to solve the computational problems
- Learn proof techniques critical for reasoning about the correctness of algorithms
- Learn analysis techniques critical to determine the efficiency of algorithms
- Learn how to transform algorithms to programs
- Learn to implement, simulate, and visualize algorithms
- Apply algorithms to real world problems
This course consists of homework assignments (every 10-15 days), 3 in-class exams, quizzes, and a research project. The course closely follows the book Algorithm Design by Jon Kleinberg and Eva Tardos, and Python Algorithms: Mastering Basic Algorithms in the Python Language by Magnus Lie Hetland.
The topics are:
| TOPIC | SLIDES | READINGS | DEMOS |
|---|---|---|---|
| Introduction (What are algorithms?) | Syllabus | Preface · ToC | |
| Stable Matching (Gale-Shapley) | 1up · 4up | Chapter 1 | Gale-Shapley |
| Algorithm Analysis (big-Oh notation) | 1up · 4up | Chapter 2 | |
| Graphs (graph search) | 1up · 4up | Chapter 3 | |
| Greedy Algorithms I (basic techniques) | 1up · 4up | Chapter 4 | interval scheduling · interval partitioning |
| Greedy Algorithms II (shortest paths and MSTs) | 1up · 4up | Chapter 4 | Dijkstra · red-blue · Prim · Kruskal · Borůvka · Edmonds |
| Divide and Conquer I (sorting and selection) | 1up · 4up | Chapter 5 | merging · inversions · quickselect |
| Divide and Conquer II (integer and polynomial multiplication) | 1up · 4up | Chapter 5 | |
| Dynamic Programming I (basic techniques) | 1up · 4up | Chapter 6 | |
| Dynamic Programming II (sequence alignment, Bellman-Ford) | 1up · 4up | Chapter 6 | |
| Network Flow I (maximum flow theory) | 1up · 4up | Chapter 7 | Ford-Fulkerson · pathological |
| Network Flow II (maximum flow applications) | 1up · 4up | Chapter 7 | |
| Network Flow III (assignment problem) | 1up · 4up | Chapter 7 | |
| Intractability I (polynomial-time reductions) | 1up · 4up | Chapter 8 | |
| Intractability II (P, NP, and NP-complete) | 1up · 4up | Chapter 8 | |
| Intractability III (coping with intractability) | 1up · 4up | Section 10.2, 11.8 | |
| PSPACE (PSPACE complexity class) | 1up · 4up | Chapter 9 | |
| Limits of Tractability (extending limits of tractability) | 1up · 4up | Chapter 10 | |
| Approximation Algorithms (approximation algorithms) | 1up · 4up | Chapter 11 | |
| Local Search (Metropolis, Hopfield nets) | 1up · 4up | Chapter 12 | Supplemental Material - list scheduling |
| Randomized Algorithms (randomized algorithms) | 1up · 4up | Chapter 13 | |
| Data Structures I (amortized analysis) | 1up · 4up | Supplemental Material | |
| Data Structures II (binary and binomial heaps) | 1up · 4up | Supplemental Material | binary heap · heapify |
| Data Structures III (Fibonacci heaps) | 1up · 4up | Supplemental Material | |
| Data Structures IV (union-find) | 1up · 4up | Section 5.1.4 (Dasgupta et al.) | |
| Linear Programming I (simplex algorithm) | 1up · 4up | Supplemental Material | |
| Linear Programming II (linear programming duality) | 1up · 4up | Supplemental Material | |
| Linear Programming III (ellipsoid algorithm) | 1up · 4up | Supplemental Material |