CPS 100, Fall 2000, 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.

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
8/28 Overview, review, classes, vectors, C++, objects notes for viewing notes for printing inclass work Astrachan, pp 277-335 Astrachan, pp 339-380	8/30 Templates, operators, function objects inclass work Astrachan, pp 535-539, 543-549 Astrachan, pp 745-756	9/1 Pointers and vectors inclass work wordcount.cpp Astrachan pp 571-594 Assignment 0 due
9/4 Catch up sharetoy.cpp frogwalk3.cpp quiz 1 out Assignment 1.1 due	9/6 Linked-lists notes for viewing notes for printing inclass work linkcount.cpp Astrachan, pp. 595-610 Sedgewick, pp. 91-110	9/8 Linked lists, recursion Drop/Add over Quiz Sedgewick, pp. 207-209
9/11 Linked lists, toward big-Oh inclass work	9/13 Algorithm Analysis, Big-Oh class questions dirsort.cpp Sedgewick, pp 27-42 Astrachan, pp 556-559 Assignment 1.2 due	9/15 Sets, Linked sets, efficiency notes for viewing notes for printing useset.cpp Astrachan, pp 610-620 Quiz Homework 1 out.
9/18 Trees, big-Oh, recurrences notes for viewing notes for printing Sedgwick, pp 44-64	9/20 Linked List review inclass work answers to in class different answers	9/22 Review/Catch Up Homework 1 due (no quiz)
9/25 Inheritance Astrachan, pp 641-654 inheritance code Assignment 2.0 due	9/27 Trees, search trees in class questions in class answers quiz 2 questions out Sedgewick pp 230-251	9/29 trees, C++ and inheritance Sedgewick pp 515-524 Sedgewick pp 529-541
10/2 Catch up/Review of MSIntersect notes for viewing notes for printing copyprob.cpp	10/4 Catch up, review tree problems	10/6 Catch up, review Assignment 2.1 due Quiz
10/9 Review linked list answers out tree answers out	10/11 Test 1	10/13 Secrets of life
10/16 Fall Break	10/18 Stacks/Queues, applications Sedgewick p 129-158 notes for viewing notes for printing treelevel.cpp postfix.cpp Assignment 3 out inclass work	10/20 stacks/queues, OO/hooks modified treelevel mapcount.cpp sdmap.h
10/23 Hashing, Maps, Efficiency Sedgewick pp 587-607 notes for viewing notes for printing tmapcounter.cpp expression parsing mapcount2.cpp from class	10/25 Hashing continued filemap.cpp filetmap.cpp written trees out Quiz 3 out Sedgewick pp 608-622 Assignment 3 due	10/27 Maps, Inheritance, RSG/Animal
10/30 Catch up/maps	11/1 Priority Queues/Heaps/Huffman Coding Sedgewick pp 381-389 notes for viewing notes for printing usepq.cpp pqdemo.cpp Assignment 4 out inclass tree balance O(n)	11/3 Huffman Tries, Monkeys, Typewriters Written 2/trees due inclass work Quiz 3
11/6 RSG data structures notes	11/8 Sorting and Searching notes for viewing notes for printing inclass work libsort.cpp Sedgewick pp 265--346 Tapestry pp 543-567 Sedgewick pp 347-368	11/10 Sorting continued test practice timequadsorts2.cpp sortall.h sortall.cpp
11/13 Review/Catch Up Assignment 4 due	11/15 Test 2	11/17 Huffman Coding Written Assignment 3 out
11/20 Backtracking, Heuristics notes for viewing notes for printing in class backtracking	11/22 Backtracking, Minimax, Game-playing, Cryptograms qbushy.cpp discussed cryptograms Written 3 due	11/24 Thanksgiving
11/27 Balanced Trees (AVL/B-tree/Red-black) Tries notes for viewing notes for printing inclass tries/avl trees/code huff questions	11/29 Graphs introduction/Algorithms inclass graphs Sedgewick pp 121--124,255-262	12/1 Graph Algorithms continued notes for viewing notes for printing wordladder ladder questions
12/4 Graphs continued graph questions crawlgraph.cpp graph.h graphalg.h	12/6 NP-Completeness, Computability Last Class notes for viewing notes for printing Assignment 5 due	12/8

12/11 M

12/12 T

12/13 W

12/14 Th
Final Exam
9:00 AM -- noon
Open Book

12/15 F

Owen L. Astrachan

Last modified: Tue Dec 5 22:51:24 EST 2000