Discrete Structures Fall 2006

Textbook web site.

Review: Weeks 1 through 5 web page resources.

Review: Weeks 6 through 10 web page resources.

Week Dates Topics Homework or Quizzes
11 10/30-11/03 Halloween Treat: Dinosaur treats handed out...

HOMEWORK: ATM and other Inductive proofs and poker hands HW. For Monday, and Wednesday.

ATM problem: k + 10 instead of k + 1 is okay to use for the ATM with 20 and 50 dollar bills proof.

Read section 4.4 on Functions. Know Domain, Codomain, Range, preimage, image, f maps x to y, floor, ceiling, mod, and log2 functions.

    The HW that will be due on Monday, November 6th is:

    Page 248 #52    Page 249 #54
    Page 355 #6     Page 356 #7      Page 358 #32.a.

Hash Tables.

Prime numbers

Hash Tables.

Big Theta binary relation on functions.

12 11/06-11/10 Binary Search Trees and minimum spanning trees, etc.
Draw the binary search tree (bst) that
produced the following PREORDER output:
(preorder output for the keys)
   78, 21, 12, 5, 10, 7, 101, 88, 222
13 11/13-11/17

Hashing HW due Wednesday, 11/15.


Hash Tables.

Binary Search Trees and binary trees traversals: Preorder, Inorder, Postorder.

14 11/20-11/20 Thanksgiving week Test Three email note.


Binary TREES: Binary Search Trees with their root, RST and LST, if they are not empty.

Calculating the performance for a binary search tree (BST).

15 11/27-12/01 ...

TEST 3 - Friday 12/01

TEST THREE REVIEW of Monday class.
16 12/04-12/08 TEST SCORES; EXAM #3 had 106 points possible, but is adjusted to be worth 100 points.

All Three Test scores, with the average.

  1. Know Kruskal's Algorithm for finding a MST (Minimum Spanning Tree) from a connected, weighted graph.

  2. Know Similarity Graphs and dissimilarity function concepts. You received a handout on the 2nd to last day of class. We will cover this further on the last day of class.

STUDY GUIDE: Final Exam Outline and review topics.

Final Exam is 1-2:50 p.m. on Tuesday, December 12th.

Discrete Structures Curriculum 2001 discussion by ACM/IEEE Ironman Draft.