Skip to content

Overview

Instructor: Alex Steiger (asteiger@cs.duke.edu)
Class:
M/Tu/W/Th 1:00-2:30 in LSRC D106
Recitation
: Tu/Th 2:45-4:00 in LSRC D106
Office Hours: M/W 2:45-4:00 (starting 7/8), F: 2:30-4:00 in D215, others by appt.

Course 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:

  1. Design correct and efficient algorithms for computational problems using recursion, iteration, randomization, and approximation.
  2. Analyze the correctness and efficiency of algorithms using recurrences, asymptotic analysis, and mathematical proofs.

Textbook: Algorithms by Jeff Erickson, which is freely available as an e-book at algorithms.wtf. You do not need to purchase a hardcopy. We will also reference Jeff’s notes on other topics not included in the textbook, found lower on that same webpage. Sections of other textbooks may be included as readings for the course, in which case we will provide them on Canvas.

Prerequisites (or equivalent):

  • CS 201: Data Structures and Algorithms
  • CS 230: Discrete Mathematics

CS 201 covers asymptotic runtime analysis and fundamental data structures, algorithms, and problems (e.g., binary search trees, preorder traversal, and sorting, respectively) that we will assume familiarity with. CS 230 covers the formal mathematics that we will employ to justify the correctness of algorithms and data structures at hand in the course. For a more complete list of topics that we expect familiarity with, the prerequisites on pages i-ii in the preface of our textbook closely align with our course (direct link to preface). We recommend the list of freely available resources that cover the prerequisite material at the end of that section. We also recommend Charles A. Cusack’s lecture notes, An Active Introduction to Discrete Mathematics and Algorithms (direct link).

Getting Help:

We are using Ed Discussion (use your first.last@duke.edu to login) for this course as our Q&A platform. It can be also be accessed through Canvas on the sidebar. Please ask all course-related questions should be asked on Ed. You should feel free to not only ask questions on Ed but answer your peers’ questions! Try to engage with each other here to discuss, answer, or follow-up on each others’ posts. Alex will be monitoring Ed (in)frequently throughout the semester. You are welcome to post anonymously or to make private posts if you have specific questions about your own work.

When posting on Ed, we ask that you follow the following guidelines (borrowed from Brandon Fain):

  • You should never post your own solutions publicly for other students
  • Be respectful of all other members of the course at all times
  • Try things on your own and search for other similar questions before posting your own questions.
  • Be specific in your question. For example, we need more information than “how do I solve problem 2” (remember to try things on your own first, so you should have more details to provide than this).

For personal concerns/comments/questions, please email Alex directly.

Grade Breakdown:

  • Homework: 40%
    • Lowest scored HW is dropped
  • Exams: Midterm 15%, Late-Term 15%, Comprehensive Final 20% (50% total)
  • Engagement: 10% (Lecture and discussion participation and surveys)

Tentative Schedule:

  • Week 1: Introduction (incl. Asymptotic Analysis, Induction, Recursion and Recurrence Relations)
  • Week 2: Backtracking & Dynamic Programming
  • Week 3: Graph Algorithms, Modeling, and Applications
  • Week 4: Greedy Algorithms & Flow Networks (Midterm Exam Wed 7/24)
  • Week 5: Linear Programming & NP-Hardness
  • Week 6: Randomized and/or Approximation Algorithms (Late-Term Exam Wed 8/7)
  • Final Exam: Sunday 8/11 @ 9:00am-12:00pm

Accommodations

Duke University is committed to providing equal access to students with documented disabilities. Students with disabilities may contact the Student Disability Access Office (SDAO) to ensure your access to this course and to the program. There you can engage in a confidential conversation about the process for requesting reasonable accommodations both in the classroom and in clinical settings. Students are encouraged to register with the SDAO as soon as they begin the program. Please note that accommodations are not provided retroactively. More information can be found online at access.duke.edu or by contacting SDAO at 919-668-1267, SDAO@duke.edu.