[FrontPage] [TitleIndex] [WordIndex] 

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.

Click 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 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

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.

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

2014-06-17 11:58