PineWikiAs 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 pointes 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.
