PineWikiClick on each date for detailed notes (if available). As always, the future is uncertain, so you should take parts of the schedule that haven't happened yet with a grain of salt.
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Introduction. What the course is about. Getting started with C. Readings: KernighanRitchie Chapter 1.
More C: integer types and expressions; declarations and variables. Readings: KernighanRitchie Chapter 2, C/Variables, C/IntegerTypes.
C statements and control structures: assignment operators, relational operators, logical operators , if/then/else statements, while loops. Readings: KernighanRitchie Chapter 3, C/Statements.
C control structures continued: switch, for, and do..while statements; break, continue, and the infamous goto. Readings: C/Statements, KernighanRitchie Chapter 3. Side note: a question about what happens to the various control structures when they are compiled made me go look at assembler output for a bit. The page C/AssemblyLanguage, which you do not have to read, was the result.
C functions. Readings: C/Functions, KernighanRitchie Chapter 4.
Input and output. Readings: C/InputOutput, KernighanRitchie Appendix B Section 1 (you don't need to memorize this, but you should read it).
Pointers. Readings: C/Pointers, KernighanRitchie Chapter 5.
More pointers: null pointers, void *, dynamic storage allocation using malloc and free. Readings: C/Pointers, C/DynamicStorageAllocation (old notes, mostly superseded by the corresponding sections in C/Pointers.
String processing in C. Readings: C/Strings, KernighanRitchie Section B3.
More C/Strings: strlen; malloc and strings. C/Structs and typedef. Using struct pointers to hide information for AbstractDataTypes. Readings: KernighanRitchie Chapter 6.
More struct-like constructions: union, enum. Giving useful names to things with typedef and #define. Readings: C/Definitions, KernighanRitchie Section A12.
More ADTs. Efficiency issues and AsymptoticNotation. LinkedLists and applications. Readings: KernighanPike Sections 2.5 and 2.7.
More LinkedLists and related abstract data types: queues, iterating over linked lists.
Testing and debugging: use of assert and gdb. Debugging strategies. Readings: KernighanPike chapter 6, C/Debugging, TestingDuringDevelopment.
More linked list structures: circular and/or doubly-linked lists. Sanity checking. Readings: LinkedLists.
More circular doubly-linked lists: splicing and dicing, iterating around a circle, use as deques.
Dictionary data types and HashTables. Readings: KernighanPike Section 2.9.
More HashTables. Storing and retrieving values with open addressing.
Dynamic HashTables. Iterating over hash tables. Generic hash tables using void *.
Function pointers. Readings: KernighanRitchie Section 5.11, C/FunctionPointers.
Exam 1 was given Wednesday, March 2nd, 2005, in class. It was a closed-book, cumulative exam covering all material discussed in lecture up to that date. The sample solutions are available as exam1-solutions.pdf
More C/FunctionPointers: closures and objects.
Timing and profiling. Readings: KernighanPike Sections 7.1-7.2, C/PerformanceTuning
Basic algorithm design technique. Readings: KernighanPike Sections 2.1-2.2, AlgorithmDesignTechniques.
More algorithm design: DynamicProgramming.
Recursive data structures. Heaps. Readings: BinaryTrees, Heaps.
More Heaps: packed heaps, bottom-up heapification, heapsort.
C/BitExtraction, Basic idea of RadixSearch.
More RadixSearch: tries and Patricia trees.
More RadixSearch: ternary search trees.
Graphs and graph algorithms in C. Readings: C/Graphs; see also GraphTheory and GraphAlgorithms for relevant notes from other courses.
More graph algorithms and implementations: DepthFirstSearch and BreadthFirstSearch. Readings: C/Graphs.
Finding shortest paths in graphs. Readings: ShortestPath.
C/FloatingPoint. Structure, use, and pitfalls of floats and doubles.
Persistent data. Random-access binary files. Readings: C/Persistence.
What do learn next now that you know C. Readings: C/WhatNext.
Exam 2 was given Monday, April 25th, 2005, in class. The exams have now been graded and the grades have been entered into Grade-o-Matic. Graded exams are available outside AKW 401. Sample solutions are available in exam2-solutions.pdf.