CS 3110 Spring 2009

CS 3110 Schedule Spring 2009 The notes linked below are required reading, but they are not a substitute for attending lecture and recitation. The lectures and recitation sections are tightly coupled: Lectures will assume knowledge from previous sections, and vice-versa. These notes should be read sequentially (Monday's section, Tuesday's lecture, Wednesday's section, Thursday's lecture, etc.). Note: due dates of unreleased assignments are tentative. Note: lecture and recitation topic schedule is tentative.
Meeting	Date	Topic
Introduction to Functional Programming
Lec. 1	Jan. 20	Course overview and background on ML (slides) (code)
Rec. 1	21	Introduction to OCaml syntax
Lec. 2	22	OCaml syntax and evaluation (code) (PS1 issued)
Thu Jan 22 and Sun Jan 25		Introduction to OCaml, 7:00PM, Upson B7 Lab (code)
Rec. 2	26	Tuples, records, and pattern matching (code for 2:30pm recitation)
Lec. 3	27	Scope, currying and lists (code)
Rec. 3	28	Higher-order Functions, Anonymous Functions, Currying, Side effects, Printing and Exceptions
Lec. 4	29	Variants, recursive types, and polymorphism (code) (PS1 due, PS2 issued)
Rec. 4	Feb. 2	Pattern-matching pitfalls, more parameterized types
Lec. 5	3	Map, fold and the map-reduce paradigm (code)
Rec. 5	4	Folding and tail recursion
Lec. 6	5	Substitution model of evaluation
Functional Data Structures
Rec. 6	9	More about the substitution model
Lec. 7	10	Modules and data abstractions (structures and signatures) (code)
Rec. 7	11	Functional stacks and queues, dictionaries, fractions
Lec. 8	12	Specifications and Abstraction Functions (code)(PS2 due, PS3 issued)
Rec. 8	16	PS3 review: LZW compression
Lec. 9	17	Representation and module invariants (code)
Rec. 9	18	More LZW compression for PS3
Lec. 10	19	Functors: Parameterized Modules (code)
Rec. 10	23	More about functors
Lec. 11	24	Functional Data Structures: Red-Black Trees (code)
Rec. 11	25	Mutability: refs and arrays
Lec. 12	26	Mutable data structures: disjoint set-forests (code) (PS3 due, PS4 issued)
Rec. 12	Mar. 2	Inductive correctness proofs
Lec. 13	3	Prelim 1 review (code)
Rec. 13	4	Logic for formal verification
Lec. 14	5	Verification
Mar. 5		Preliminary Exam, 7:30-9:00pm (Closed-book. Covers material through Recitation 12 and PS3.)
Rec. 14	9	Verification cont'd
Imperative Programming and Concurrency
Lec. 15	10	Testing and code review
Rec. 15	11	Prelim 1 wrap-up
Lec. 16	12	Concurrency: multi-threading and mutexes (code)(PS4 due, plus extension)
*Spring Break*
Rec. 16	23	Concurrency: Condition Variables and Message Passing
Lec. 17	24	Concurrency: Producer-Consumer and Thread Pools (code) (PS5 issued)
Rec. 17	25	PS5 overview
Data Structures and Analysis of Algorithms
Lec. 18	26	Concurrency: Thread pool cont'd (code)
Rec. 18	30	Asymptotic complexity and binary search trees
Lec. 19	31	Asymptotic complexity and recurrences
Rec. 19	Apr. 1	Solving recurrences
Lec. 20	2	Asymptotic complexity and recurrences, master method
Rec. 20	6	Using the substitution and master methods
Lec. 21	7	Amortized analysis and resizing hash tables
Rec. 21	8	Amortized analysis examples
Lec. 22	9	Representing and traversing directed graphs (code)
Rec. 22	13	Graph algorithms
Lec. 23	14	Memoization and dynamic programming (code) (PS5 due, PS6 issued)
Topics
Rec. 23	15	PS6 overview
Lec. 24	16	Locality
Rec. 24	20	Streams and lazy evaluation
Lec. 25	21	Prelim 2 review
Rec. 25	22	B-trees
Lec. 26	23	Garbage collection
Apr. 23		Preliminary Exam, 7:30-9:00pm (Closed-book. Covers material through Lecture 25 and PS5.)
Rec. 26	27	No recitation: extra office hours for PS6
Lec. 27	28	CS Research Topics: Mining Large-Scale Social Data
Rec. 27	29	No recitation: extra office hours for PS6
Lec. 28	30	CS Research Topics: The DARPA Urban Challenge
May 6		PS6 due
		The Tournament

CS 3110 Schedule Spring 2009