CSE 347 Analysis of Algorithms - bsiever/WUSTL-CSE-Curriculum GitHub Wiki

This page is a place to collect info to guide our discussion of 347's curriculum.

WUSTL course

  • CSE 347 Fall 2018 website
  • Topics covered: Divide and conquer, greedy, DP, max flow, reductions, intractability, NP-completeness, approximation algs, amortized analysis, randomized algs, online algs.
  • Pedagogy/delivery: weekly: 2 hrs lecture, 1 hr recitation
  • Learning objectives: (taken from the course webpage)
    • understand and rigorously analyze a wide variety of algorithms encountered in practice
    • articulate what it means for a problem to be intractable, to recognize intractability in some cases, and to propose approaches to make progress on intractable problems
    • be an "informed user" of algorithms

Proposed learning objectives

  • understand and rigorously analyze a wide variety of algorithms encountered in practice
  • articulate what it means for a problem to be intractable, to recognize intractability in some cases, and to propose approaches to make progress on intractable problems
  • be an "informed user" of algorithms
  • (new) classify problems encountered in practice according to their structure as being likely solvable by the appropriate technique learned in the class
  • (new) design algorithms to solve a variety of problems encountered in practice
  • (new) construct convincing formal arguments to support correctness of algorithms
  • (new) formally articulate intuitions about algorithms and translate them into formal proofs

Proposed topic coverage

  • Essential: DP, greedy, NP completeness and reductions, divide-and-conquer, flow, linearity of expectation (e.g. quicksort)
  • Recommended (cover subset at instructor's discretion): amortized analysis, randomized algs, online algs, approximation algs

Other issues raised, no definite recommendation:

  1. Testing methodology: Target student scores / target exam difficulty
  • motivating question: is it a problem if average student exam score is very low (e.g. 50%)?
  • principle: exams should be hard enough to test whether learning objectives are being met, but not impossible
  1. Exam time: in-class vs. take-home
  • preference: take-home (no a priori reason to force time limit)
  • obstacle: academic integrity issues
  • tradeoff question: do we sacrifice AI integrity for the sake of giving honest students more time on exams?

  1. Course title: should it be "Design and Analysis of Algorithms"?

  2. Course logistics: need to make sure we give students guaranteed support: reliable, well-equipped TAs, prompt grading, etc.

Peer-institution courses

Stanford (Ron)

They require only one algorithms course and it looks more like our 247 than our 347. Their Design and Analysis of Algorithms course is an elective, available on their theory and other tracks. They cover NP completeness in a required, earlier course on mathematical foundations of CS, which looks like our 240 + finite state automata and turing machines. They are on the quarter system so I'm not sure how they cover so much in a quarter.

Rice (Ron)

Rice has many more required courses than we do, and their major program requires 16 (to our 14) courses in computer science. For algorithms, they require Algorithmic Thinking, which combines some of our 240 and 247 material. They require also Reasoning about Algorithms, which is a slower and easier version of our 347.

Harvey Mudd (Steve)

  • CS140: Algorithms / course description
  • Topics covered: divide-and-conquer, DP, amortized analysis, recurrences, invariants, inductive proofs, sorting, searching, shortest-path, network flow; selections from circuits, parallel algs, comp. geometry; NP-completeness, complexity, approximation algs.
  • Pedagogy/delivery: 3.0 credits. Some implementation assignments.
  • Learning objectives: This seems to be a combo of our 247 and 347; looks like a lot to cover in one semester.

Purdue (Steve)

  • CS 31800: Intro to the Analysis of Algorithms / course description
  • Topics covered: sorting, searching, pattern-matching, graph probs, intro to NP.
  • Pedagogy/delivery: 3.0 hrs
  • Learning objectives: Not required (only 247-equivalent is required); required for Algorithms "track" only.

UIUC (Jeremy)

  • CS 374: Intro to algorithms and models of computation
  • Topics covered: string, languages, and regular expressions

DFAs, NFAs, proving nonregularity

CFLs

Turing machine

recursive algorithms

divide-and-conquer (multiplication, selection)

backtracking search

DP (text segmentation, edit distance, optimal BSTs)

graph algorithms (DFS, topological sort, strongly-connected components)

shortest paths (Dijkstra, Bellman-Ford, Floyd-Warshall)

MST

P and NP, Cook's Theorem

hardness via reductions

undecidability + Rice's theorem

  • Pedagogy/delivery:
  • Learning objectives: mixes algorithms and automata theory, and probably doesn't go as deep on either as we do in 347 + 547. Seems to be a "terminal" theory course; the advanced course that is prereq for graduate theory courses, CSE 473, looks more like our 347.

MIT (Jeremy)

  • 6.046J Design and Analysis of Algorithms
  • Topics covered: Interval schedling as intro (just like 347)

Divide-and-conquer algorithms (medians, convex hull, more interval scheduling, Strassen, FFT)

B-trees

van Emde Boas trees

Union-find + amortized analysis

randomized algorithms (matrix multiply, quicksort + quickmedian, skip lists, universal hashing)

dynamic programming (range trees, all-pairs shortest paths)

greedy algorithms (MST and others)

"incremental improvement" (max flow/min cut, maximum matching, etc)

linear programming and the idea of reduction

complexity (P, NP, NP-completness, reductions)

approximation algorithms

distributed algorithms (synchronous and asynchronous)

cryptography (hash functions, ciphers)

cache-oblivious algorithms

  • Pedagogy/delivery:
  • Learning objectives: seems like 347++ in terms of topics. Follow-on course is 6.854, which is like our 541 but has more stuff in it and is taught by a famous algorithms guy