Date: Tue, 14 Jan 1997 20:33:03 GMT Server: Apache/1.0.5 Content-type: text/html Content-length: 4047 Last-modified: Mon, 13 Jan 1997 17:44:22 GMT
Week Lecture Topics Reading Week 1 (Jan 6 - 10) Intro, Abstraction, Data Models AU* Ch. 1 The Pascal Data Model AU Ch. 1 Pascal Storage Allocation N@ p383-414 Week 2 (Jan 13 - 17) Dynamic Allocation of Objects N p415-465 Iteration AU Sec 2.2 Inductive Proofs AU Sec 2.3 Complete Induction AU Sec 2.4 Week 3 (Jan 21 - 24) Proving Properties of Programs AU Sec 2.5 Recursive Definitions AU Sec 2.6 Recursive Methods AU Sec 2.7, N p466-474 Week 4 (Jan 27 - 31) Execution of Recursive Calls N p475-481 Merge Sort AU Sec 2.8 Proving Properties of Recursive Programs AU Sec 2.9 Quicksort N p489-496 EXAM 1 Feb 4 - 6, covering Ch. 1 & 2 and 142 lectures. Week 5 (Feb 3 - 7) Measuring Running Time AU Sec 3.1-3.3 Big-Oh AU Sec 3.4, 3.5 Analyzing Program Running Time AU Sec 3.6 Week 6 (Feb 10 - 14) Bounding Running Time AU Sec 3.7 Analyzing Programs with Procedure Calls AU Sec 3.8 Analyzing Recursive Procedures AU Sec 3.9 Analysis of Merge Sort AU Sec 3.10 Week 7 (Feb 18 - 21) Solving Recurrence Relations AU Sec 3.11 Trees, Basic Terminology AU Sec 5.1-5.2 Data Structures for Trees AU Sec 5.3 Week 8 (Feb 24 - 28) Recursions on Trees AU Sec 5.4 Structural Induction AU Sec 5.5 Binary Trees AU Sec 5.6 Binary Search Trees AU Sec 5.7-5.8 Week 9 (Mar 3 - 7) AVL Trees CS235 Binary_Tree Class Priority Queues and Partially Ordered Trees AU Sec 5.9 Heap Sort AU Sec 5.10 Week 10 (Mar 10 - 14) Lists AU Sec 6.1-6.5 Stacks AU Sec 6.6 Queues AU Sec 6.8 EXAM 2 Mar 18 - 20 covering Ch. 3, 5 & 6 through 6.8. Week 11 (Mar 17 - 21) Longest Common Subsequences AU Sec 6.9 Character Strings AU Sec 6.10 Sets - Basic Definitions, Operations AU Sec 7.1-7.2 Operations on Sets AU Sec 7.3 Week 12 (Mar 24 - 28) Implementation of Sets AU Sec 7.4-7.5 Probability AU Sec 4.9-4.10 Hashing AU Sec 7.6 Week 13 (Mar 31 - Apr 4) Relations and Functions AU Sec 7.7 Implementing Functions & relations AU Sec 7.8-7.9 Binary Relations AU Sec 7.10 Week 14 (Apr 7 - 11) Infinite Sets AU Sec 7.11 Counting AU Sec 4.1-4.2 Permutations AU Sec 4.3 Selections, Orderings, Assignments AU Sec 4.4-4.6 Week 15 (Apr 14 - 15) Distribution of Objects to Bins AU Sec 4.7 Review FINAL Section 1 Friday, April 18, 7AM-10AM (In Class) FINAL Section 2 Wednesday, April 23, 7AM-10AM (In Class) *Aho, Alfred V. & Ullman, Jeffrey D., "Foundations of Computer Science," (C Edition), 1995, Computer Science Press @Norman, Theodore A., "A First Course in Object-Oriented Programming", BYU Bookstore Packet