CMPSC 465, Spring 2013

Syllabus

DATE

 

M 01-07
Ch. 1

STL Containers classes: vector, list, set, multiset
p. 8: Do Exercises 4, 6, 8, and 9. You should code and test Ex. 4!

Assignment 1

W 01-09
Sec. 2.1

pp. 50-52: Do Exercises 1acdf, 2, 4, 7, 8, 9, 10 (in centuries)

F 01-11
Sec. 2.2
  • pp. 59-61: 2 (use formal defs.), 3 (use formal defs. for abde), 4 (use defs or limits), 5 (use defs or limits), 9, 10
  • (To Think About) p. 61, #12 This is one of the best problems in the book.
M 01-14
W 01-16
Sec. 2.3, 61-66
  • pp. 67-69: 1a-f, 2a-c (HINT: See appendix A), 3, 4, 5, 6, 9, 12, 13
F 01-18
M 01-21
Martin Luther King Day - No Classes
W 01-23
Sec. 2.4, 69-76
F 01-25
M 01-28
Sec. 3.1, 98-101
  • pp. 102, 103: 2, 3, 4, 5, 8, 9, 10, 11, 13, 14
W 01-30
Sec. 3.2, 104-105
  • pp. 106, 107: 2, 4, 5, 6
F 02-01

         * * * EXAM I * * * (on material through Sec. 2.4)

M 02-04
         Discuss Exam 1
W 02-06
Sec. 3.4 115-120
F 02-08
  * * * * Unavoidable instructor absence ... * * * *
M 02-11
Sec. 3.5, 122-128
  • pp. 128-130: 1, 2, 4, 6, 7, 8
W 02-13
Sec. 3.5, 122-128
  • C++ Code for DFS: See P:\Public\CmpSc 465 Spring 2013\dfsTree
F 02-15
Sec. 3.5, 122-128
  • C++ Code for BFS: See P:\Public\CmpSc 465 Spring 2013\bfsTree
M 02-18
Sec. 4.2, 138-141
  • pp. 142,143: 1, 3, 5, 9
W 02-20
Sec. 4.1, 131-136
Sec. 4.4, 150-152
F 02-22
Sec. 4.4, 153-4
Russian Peasant Mult
M 02-25
Sec. 5.1, 169-174
W 02-27
  • p. 181: 1, 3, 5, 6, 8
F 03-01
Sec. 5.2, 176-181
 
S P R I N G     B R E A K
M 03-11
Sec. 6.4, 226-232
  • p. 223: 1. 2, 3a, 4, 5, 7, 8
  • Code for heaps is in P:\Public\CmpSc 465 Spring 2013\heaps
W 03-13
F 03-15
Complete 6.4
M 03-18
 no class . . .
W 03-20
       * * * EXAM 2 * * * (on material through Sec. 5.2)
F 03-22
 
M 03-25
Section 9.4: Huffman Trees and Codes
  • (This section is out of order, but uses priority queues, so is a good follow-up to Sec. 6.4)
  • Source code for generating the Huffman trees and code is in P:\Public\CmpSc 465 Spring 2013\huffman.
  • pp. 342, 343: 1, 3, 4, 5. Also, experiment with some letter/frequency pairs using the above source code.
W 03-27
F 03-29
Section 6.3: Balanced BSTs and 2-3 Trees
  • There is code demonstarting STL set and map classes in P:\Public\CmpSc 465 Spring 2013\SetsAndMaps
  • There are images and .pdf files demonstrating AVL and Re-Black tree insertion in P:\Public\CmpSc 465 Spring 2013\Balanced BST Demos.
  • Use the applet at http://people.ksp.sk/~kuko/bak/big/ to do assist you in constructing AVL, Red-Black, and 2-3 trees for "GRAPENUTS", "DISGRACEFUL", "UNCOPYRIGHTABLE", and "DERMATOGLYPHICS".
M 04-01
W 04-03
Section 7.3: Hashing
  • pp. 274, 275: 1, 2, 3, 4, 7, 8
F 04-05

Chapter 8 Intro.

 

  • Code for dynamic programming versions of binomial coeffiecients is in the folder P:\Public\CmpSc 465 Spring 2013\binCoeffs.
M 04-08
Section 7.3: Hashing
  • pp. 274, 275: 1, 2, 3, 4, 7, 8
W 04-10
Section 8.2:
0-1 Knapsack
  • pp. 296, 297: 1, 2, 3, 4
  • See P:\Public\CmpSc 465 Spring 2013 for versions of Knapsack code.
F 04-12
Section 8.2 (finish)

Section 8.4 Warshall/Floyd
  • pp. 296, 297: 1, 2, 3, 4

  • pp 311, 312: 1, 2a, 3, 7, 8
M 04-15

EXAM 3 review questions

W 04-17

      * * * EXAM 3 * * * ( material )

F 04-19
 
M 04-22
 
W 04-24
 
F 04-26