CPS 100, Spring 2001, Syllabus

All readings should be done before the class in which they're scheduled to get the most from each class. There will be guided questions for each reading to help you do the reading in a productive way. You should answer the inclass questions before the class in which they are linked below.

In general you can't read books about programming and computer science the same way you read novels or non-fiction books on politicial science, for example. You have to study what you're reading and ask yourself questions about the reading to ensure you get some understanding. You probably won't understand everything when you first read it.

For readings Astrachan is A Computer Science Tapestry by Astrachan and Sedgwick is Algorithms in C++ by Sedgewick.

Monday	Wednesday	Friday
	1/10 Overview, review, classes, C++, vectors notes for viewing notes for printing inclass work Astrachan, pp 277-335 Astrachan, pp 339-380	1/12 Operators, function objects, algorithms inclass work Astrachan, pp 543-549 Astrachan, pp 745-756
1/15 Martin Luther King Day Introductions Due	1/17 C++, compiling inclass work Astrachan pp 571-581	1/19 Pointers inclass work Astrachan pp 582-595 Yahtzee Due
1/22 Pointers/Sharing linetracker.cpp Anagram Due	1/24 Drop/Add over Linked Lists notes for viewing notes for printing inclass work Astrachan, pp. 595-610 Sedgewick, pp. 91-110	1/26 Linked Lists, recursion inclass work Sedgewick, pp. 207-209 Quiz
1/29 Linked Lists Astrachan, pp 535-539 written link out multiset out	1/31 Linked Lists, toward big-Oh inclass work Astrachan, pp 556-559	2/2 Linked List Ketchup inclass work Quiz
2/5 Introduction to multiset, interfaces, towards inheritance notes for viewing notes for printing inclass work Written Link due *morning*	2/7 Inheritance Astrachan, pp 641-654 inheritance code inclass work	2/9 Algorithm Analysis, Big-Oh Sedgewick, pp 27-42 Astrachan, pp 556-559
2/12 Big-Oh, Search trees notes for viewing notes for printing basictree.cpp Sedgwick, pp 44-64 Multiset due	2/14 Trees continued, implementation and analysis inclass questions Sedgewick pp 230-251 Multiset part 2 out	2/16 More tree examples Sedgewick pp 515-524 Sedgewick pp 529-541 inclass #10 answers
2/19 Test 1	2/21 Trees and recurrences	2/23 Stacks/Queues notes for viewing notes for printing treelevel.cpp postfix.cpp inclass questions Sedgewick p 129-158 Multiset part 2 due *morning*
2/26 Queues, level order traversal treelevel.cpp	2/28 Maps: interface and implementation notes for viewing notes for printing tmapcounter.cpp anamap.cpp expressions	3/2 Maps: hashing, efficiency, inheritance Sedgewick pp 587-607 Quiz
3/5 Hashing: alternative implementations Quiz 3 solutions Sedgewick pp 608-622	3/7 Backtracking, Heuristics, Cryptograms Make-up Quiz notes for viewing notes for printing hanoi.cpp nqueens.cpp	3/9 Backtracking, Minimax, Gameplaying
3/12 Spring Break	3/14 Spring Break	3/16 Spring Break
3/19 Priority Queues, Heaps, Huffman Coding notes for viewing notes for printing pqdemo.cpp usepq.cpp Sedgewick pp 381-389 Written Tree out	3/21 Heaps, Huffman Coding Sedgewick pp 381-389 Recurrence Notes Huffman Coding RSG out	3/23 Tries, Monkeys, Typewriters, Catch up trie.cpp babble.cpp
3/26 Sorting: theory and practice in class questions Sedgewick pp 265--346 Tapestry pp 543-567 Sedgewick pp 347-368 Written Tree due	3/28 Sorting continued	3/30 Sorting finished Quiz RSG due
4/2 Balanced Trees (AVL/Red-Black) notes for viewing notes for printing balanced trees	4/4 Game Trees TicTacToe	4/6 Huff Coding/Design in class questions Huff out
4/9 Catch up in class questions Sorting Cheat Sheet	4/11 Test 2	4/13 Graphs: vocabulary and algorithms notes for viewing notes for printing in class questions Sedgewick pp 121-124, 255-262
4/16 Programming Graphs	4/18 Graph Algorithms graphstuff dijkstra.cpp inclass questions	4/20 Catch up Quiz
4/23 NP-Completeness and Computability notes for viewing notes for printing colorable.cpp inclass questions	4/25 Last Day of Class	4/27
4/30	5/2 Final Exam, 9-12 noon	5/4

Owen L. Astrachan

Last modified: Mon Apr 23 09:44:53 EDT 2001