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

WUSTL course

• CSE 247/502N Spring 2019 website
• Topics covered: asymptotic complexity (2 lectures), stacks, queues, priority queues, recurrences (2 lectures: trees/summations and the master theorem), sorting (merge, selection, radix, comparison-sort lower bd), hashing/hash tables (2 lectures, light analysis), BSTs, AVL trees, graph search (BFS & DFS), Dijkstra's, Kruskal's, Prim's, general greedy strategy / exchange arguments.
• Pedagogy/delivery: weekly: one 1.5 hr lecture, one 1.5 hr studio
• Learning objectives: per-module learning objectives currently on each module's page (and listed here)

Proposed learning objectives

No change from current per-module objectives on course website.

Course material

Material is stable as-is and comparable with similar courses at peer institutions. No changes recommended.

• Essential topics: asymptotic complexity, priority queues, solving recurrences, sorting, hashing, balanced binary search trees, graph search and single-source shortest-path algorithms, minimum spanning trees, greedy algorithms and exchange arguments.
• Flexible topics: examples of data structs/algorithms in "essential" categories, e.g. red-black trees vs. AVL trees for balanced BSTs.

Suggestions / recommendations

1. Give short list of prereq skills in course listing: summations, proofs by induction. Revisit prereqs page on course website.
2. Create a new assignment: HW0 to test prereq skills / turnin workflow.

Issues discussed

1. Programming maturity: what role does 247 play in developing it?

• Should we provide less skeleton code to students? Less would help them gain autonomy and debug faster; more allows for more assignments in less time.

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)

• CS 70: Data Structures and Program Development / course description
• Topics covered: priority queues, dynamic dictionaries, disjoint sets, heaps, hash tables, balanced BSTs. Analysis including worst-case, avg-case, amortized. Storage alloc/reclamation. Lots of implementation practice.
• Pedagogy/delivery: 3.0 credits
• Learning objectives: None specified. Looks very similar to our 247.

Purdue (Steve)

• CS 25100: Data Structures and Algorithms / course description
• Topics covered: running-time analysis, 1D data structs, trees, heaps, sorting, BSTs, hash tables, graphs.
• Pedagogy/delivery: 3.0 credits
• Learning objectives: Looks very similar to 247.

UIUC (Jeremy)

• CS 255 Data structures
• Topics covered: 3 weeks of OO design concepts lists

stacks and queues

iterators

trees BSTs

AVL trees

k-d trees

B-trees

hashing (3 lectures)

heaps

disjoint sets

graphs

BFS

DFS

MST

shortest paths (single-source and all-pairs)

• Pedagogy/delivery:
• Learning objectives: shoves in OO design; otherwise, lots of commonality with 247

MIT (Jeremy)

• 6.006: Introduction to Algorithms
• Topics covered: "Algorithmic thinking" "Models of Computation" (compuational cost)

sorting (insertion, merge)

binary heaps

BSTs

AVL trees

counting and radix sort, information-theoretic lower bounds

hashing (chained)

hashing (open-addressing)

other hashing (Karp-Rabin, crypto hashing)

bignum arithmetic

floating-point math (square-root finding, Newton's method)

BFS

DFS + topological sort

Shortest paths (Dijkstra, Bellman-Ford)

Dynamic programming (numerous variants)

"advanced topics" - complexity, "research topics"

• Pedagogy/delivery:
• Learning objectives: looks more ambitious than 247