Study Guide for Final

Study Guide for Final

CS 336, Werth

Fall 2003

1. Coverage. The final is cumulative. The previous two study guides for the first and second mid-terms describe the old material to study for the final. They are on the web. This study guide describes the new material to be covered. This new material will be Sections 8.7-8.8, 9.1, 9.4-9.5 and 3.6 from the book. Also, this new material will be drawn from the class notes, especially those on program correctness.

The new material will be about 50% of the final and the old material will be about 25% of the final for each of the two old study guides.

II. Mechanics

Exam Date and Time:

THURSDAY, DECEMBER 11, 2-5 PM

Exam Room:	RAS	213

III. Things to study: Class notes, homework, "Problems to study for Pop Quizzes", book.

IV. Definitions/Principles to know

1. planar graphs

2. Euler's formula

3. K _3,3 and K₅ are not planar

4. homeomorhic graphs, Kuratowski's theorem

5. dual graph of a map

6. coloring of a graph, chromatic number of a graph

7. The four color theorem

8. Applications of graph coloring: scheduling, register optimization

9. An algorithm for finding a graph coloring

10. Definition of a tree, Theorem 1 page 633

11. m-ary tree, full m-ary tree

12. Theorems 2-4 page 639

13. level of a vertex, height of a (rooted) tree, balanced tree

14. spanning tree

15. breadth first, depth first search

16. minimum spanning tree,

17. Prim's and Kruskal's algorithms

18. Partial correctness of a program segment wrt initial assertion p and final assertion q

19.Rules of inference for: conditionals, compositions, and assignments

20. Total correctness

21. loop invariants

22. weakest precondition, weakest precondition computations conditionals, compositions, and assignments

23.Pre and post conditions

24. Bound functions

V. The final will contain at least the following:

1. program(s) to show totally correct using loop invariants and weakest preconditions

2. program segments to show partially correct

3. some code for which you will optimize register assignments using graph coloring

4. Some things on trees - minimum spanning tree, breadth first or depth first search

5. A structural induction proof

6. A logical equivalence to prove using equivalences as in Example 6 page 25.

A set equality to show either using the table of set identities or by showing each side is

a subset of the other.

(I will give you a table of equivalences as I did on the first exam)

7. An f and g where you show f is O(g) from the definition (i.e. find the witnesses C and k)

8. A complicated expression for which you must find a "good" big O expression using the theorems

9. An induction proof (done using the good style we described).

10. A recursive definition to give

11. Permutations and combinations problems of all the standard types

12. Some English statements to write in logical notation.