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 CS235 Calendar

CS235 Calendar

Winter 1997

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