CS223/Schedule

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

As always, the future is uncertain, so you should take parts of the schedule that haven't happened yet with a grain of salt.

2012-01-10: Introduction. What the course is about. Getting started with C: running the compiler, the main function, declaring variables, simple input and output, start of control structures (if/else, while and for loops). Readings: WhyYouShouldLearnC, HowToCompileAndRunPrograms, HowToUseTheComputingFacilities, C/Variables, C/IntegerTypes, C/InputOutput, C/Statements; KernighanRitchie §§1.1–1.5, plus 3.1–3.3 for more details on if statements and §3.5 for more details on while and for loops.
2012-01-12: Arithmetic. Floating-point types. Relational, logical, bitwise, and assignment expressions. Operator precedence. Readings: C/IntegerTypes, C/FloatingPoint, C/Precedence; KernighanRitchie Chapter 2.
2012-01-17: More control structures (do..while loops, break and continue, switch and goto, nested loops). Basics of functions. Readings: C/Statements, C/Functions; KernighanRitchie rest of Chapter 3, §§1.7–1.8.
2012-01-19: Pointers and pointer arithmetic. A little bit about arrays, malloc and free, and C99 variable-length arrays. Readings: C/Pointers; KernighanRitchie §§1.6, 5.1, 5.3, and 5.4; HorowitzEtAl §1.2. All lectures will be in DL 220 starting from this date.
2012-01-24: Pointers as function parameters and return values. Pointers to pointers and multidimensional arrays. A tiny bit about strings and the true meaning of argv. Readings: KernighanRitchie §§5.2, 5.6, 5.7, 5.9, and 5.10; HorowitzEtAl §2.1–2.2.
2012-01-26: Strings, character arrays, passing arrays in and out of functions, const and restrict. Readings: C/Strings; KernighanRitchie §§1.9, 5.5, 2.4.
2012-01-31: structs, unions, and enums. Basics of abstract data types and use of opaque struct pointers for information hiding. Readings: C/Structs, C/Definitions, AbstractDataTypes; KernighanRitchie §§6.1, 6.2, 6.4, 6.8, and 2.3; HorowitzEtAl §2.3.
2012-02-02: More about abstract data types. Use of typedef. Compiling programs across multiple files; use of make. Readings: AbstractDataTypes, HowToUseTheComputingFacilities section on Makefiles; HorowitzEtAl §1.4; KernighanRitchie §6.7.
2012-02-07: Guest lecture by Debayan Gupta: Debugging C programs. Readings: C/Debugging.
2012-02-09: Guest lecture by Xueyuan Su: Asymptotic notation and program efficiency. Linked lists. Readings: LinkedLists; HorowitzEtAl §§1.5, 4.1–4.3.
2012-02-14: Dictionary types and hash tables. Readings: C/HashTables; HorowitzEtAl §8.2.
2012-02-16: Recursion vs iteration. Readings: C/Recursion.
2012-02-21: Recursive data structures: binary trees. Readings: BinaryTrees, BinarySearchTrees, BalancedTrees, C/AvlTree; HorowitzEtAl §§5.1–5.3, 5.7.
2012-02-23: Heaps. Also a very brief discussion of function pointers. Readings: Heaps; HorowitzEtAl §5.6, KernighanRitchie §5.11.
2012-02-28: Function pointers and applications. Readings: C/FunctionPointers, C/Iterators.
2012-03-01: Exam 1 was given Thursday, 2012-03-01, in class. It was a closed-book, cumulative exam covering all material discussed in lecture up to that date. Sample solutions: exam1-2012-solutions.pdf, exam1-2012.pdf. Sample exam from 2005: exam1-2005.pdf, exam1-2005-solutions.pdf
2012-03-20: Randomization in C. Readings: C/Randomization.
2012-03-22: Randomized data structures: skip lists, universal hash families. Readings: rest of C/Randomization.
2012-03-27: Radix sorting and radix search. Readings: RadixSort, RadixSearch; HorowitzEtAl §§12.3.1–12.3.8.
2012-03-29: Dynamic programming. Readings: DynamicProgramming.
2012-04-03: Graphs: representing a graph; depth-first search and applications. Readings: C/Graphs; HorowitzEtAl §§6.1, 6.2.1, and 6.2.3.
2012-04-05: More graph searching: breadth-first search, Dijkstra's algorithm for shortest paths, extension to A*. Readings: ShortestPath; HorowitzEtAl §§6.2.2 and 6.4.1.
2012-04-10: Effect on data structures of the memory hierarchy. B-trees. Readings: BTrees; HorowitzEtAl §11.2.
2012-04-12: String searching and suffix arrays. Readings: SuffixArrays.
2012-04-17: A bit of C++. Readings: C++.
2012-04-19: Exam 2 was given Thursday, 2012-04-19, in class. It was a closed-book, cumulative exam covering all material discussed in lecture up to that date. Sample exam from 2005: exam2-2005.pdf, exam2-2005-solutions.pdf. Exam and sample solutions: exam2-2012.pdf, exam2-2012-solutions.pdf.