## 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. 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.

...

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

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

TEST THREE on the FRIDAY AFTER THANKSGIVING BREAK...

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.