- Lecture. M/W 1:25-2:40 pm in Biological Sciences 111
- Recitation. Fridays, time and locations vary (see Dukehub)
- Primary References.
- Algorithms 1st Edition by Jeff Erickson (available online for free)
- Algorithms by Dasgupta, Papadimitriou, and Vazirani (DPV)
- Optional References. Introduction to Algorithms by Cormen and all
Bulletin Description
Design and analysis of efficient algorithms at an undergraduate level. Topics include greedy algorithms, divide and conquer, dynamic programming, graph algorithms, linear programming, randomized algorithms, and NP-completeness.
Learning Objectives
- Design correct and efficient algorithms for computational problems using techniques including (a) recursion, (b) divide and conquer, (c) parallelization, (d) dynamic programming, (e) graph search, (f) greedy, (g) flows and matching, (h) randomization, (i) and approximation.
- Analyze the correctness and efficiency of algorithms using (a) recurrences, (b) asymptotic analysis, (c) empirical benchmarks, (d) and mathematical proofs.
Prerequisites
The enforced course prerequisites are Computer Science 201 and Computer Science 230 (or approved substitutions). This course requires undergraduate background in data structures as well as a certain amount of mathematical sophistication. Ideally this background is obtained in the prerequisite courses, but you should review the detailed prerequisites and getting started guide to determine if there gaps in your background. Free online references are provided to all of the background topics.
