Study Guide for First Mid-term

CS 336 - Werth

I. Coverage: Chapter 1; Chapter 2: Sections 2.1-2.4, Euclidean Algorithm from Section 2.5; Chapter 3: Sections 3.2-3.4

II. Mechanics: Test is October 3 during class time. Test will be closed book, closed notes. I will give you as part of the test: tables of logical equivalences (p 24), rules of inference (p 58), and set identities (p 89). I expect you to know other definitions and principles from list below.

III. Things to Study: Class notes, Homework Problems, "Problems to study for Pop Quizzes", Worked examples in the book.

IV. Definitions/Principles to know:

1. Contrapositive and converse of p->q

2. Tautology, logical equivalence

3. Bound and free variables, scope of a quantifier

4. Equivalents statements for negation of existential and universals quantifiers (p35)

5. Negating nested quantifiers

6. Table 1 p 50.

7. Proof methods: direct, indirect, contradiction

8. Proof methods: constructive, non-constructive

9. Power set of a set

10. Function, codomain, domain, range

11. 1-1 and onto functions

12. Definition of big-O and big-Theta,

13. Sum, product and polynomial theorems for big-O (p 136, 139) and polynomial

theorem for big-Theta (p 142)

14. Worst-case, average case complexity

15. Tractable, intractable and unsolvable problems

16. Classes P, NP

17. Satisfiability and Traveling Salesman Problems

18. Greatest common divisor, relatively prime integers

19. Euclidean Algorithm ( p177)

20. Countable and uncountable sets. Examples of each

21. Same cardinality of sets

22. Principle of induction, basis step, inductive step, inductive hypothesis

23. Strong Induction

24. Well ordering property

25. Recursive definition

26. Structural induction

V. There will be at least the following on the test:

1. Some definitions/theorems/principles to state from the definition list above

2. Some easy problems like the pop quizzes

3. English statements to translate into logical statements.

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

OR

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

a subset of the other.

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

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

7. An induction proof.

8. A recursive definition to give

9. A structural induction proof to do

AND MAYBE

1. Do a worst case analysis of an algorithm

2. Another induction proof

3. A more complex problem (no more than 10% of the test).

4. Show f is NOT O(g) for some f and g