Review Problems

1. Convert 11001100 to
   • Decimal
   • Hexadecimal
   • Decimal using 2's complement
2. For the proposition (p^q^r^s)v(~p^q^r^s)v(p^~q^r^s)v(~p^~q^r^s)v(p^~q^r^~s)v(~p^~q^r^~s)v(~p^q^~r^~s)
   • Create a truth table
   • Create a karnuagh map and find the reduced minterm expression
   • Find the truth table of the reduced minterm expression and show that the two truth tables are equivalent
3. Prove A union B = union of the symmetric difference of A and B and the intersection of A and B.
4. For the relation R = {(1,2),(1,3),(3,4)} generate
   • reflexive closure
   • symmetric closure
   • transistive closure
5. Section 4.4: Problems 2, 4, 8, 16, and 44.
6. Prove by induction 1/(1*3) + 1/(3*5) + 1/(5*7) + . . . + 1/((2n-1)(2n+1)) = n/(2n+1)
7. Prove by induction if at least one Pi is true, P0 v P1 v . . . v Pk is true
8. Prove by induction if all Pi are true, P0 ^ P1 ^ . . . ^ Pk is true.
9. Write a recursive algorithm to find a^(2^n)) (Section 4.4, problem 24)
10. Section 4.4, problem 30
11. Given a matrix A and B compute
    • A+B
    • Product (AB and BA)
    • Row echelon form
    • Determinant of each
    • Inverse of each
12. Section 3.2, all of the big-O, big-theta and big-omega problems.
13. Section 3.5, problems 1-5.
14. Section 3.7, problems 46-50
15. Show the preorder, inorder and postorder traversals of a tree
16. Prove by induction that if a tree has v vertices and e edges, then v = e + 1
17. Consider the weighted adjacency matrix below, where an entry of - means there is no link between the nodes. Using Dijkstra's algorithm, find the shortest path from all nodes to all nodes.

    	A	B	C	D
    A	0	5	10	15
    B	-	0	4	8
    C	-	-	0	3
    E	2	-	-	0

18. Be able to construct an adjacency matrix from a graph.
19. Understand the terminology of graphs and trees
20. Prove that a tree with more than 1 vertex is a bipartite graph.
21. Prove that every connected graph with n vertices has at least n-1 edges
22. Prove that in a simple graph with at least two vertices, there must be two vertices that have the same degree (hint: Use the prigeonhole principle).
23. Prove that a simple graph is a tree if and only if it is connected, but the deletion of any of its edges produces a graph that is not connected.
24. Chapter 10, Section 5, problems 2-4 and 6-8.
25. Chapter 10, Section 3, problems 7-15
26. Game Trees and min-max
27. Hamilton and Euler paths and cycles
28. Chapter 9, Section 4, problems 1-25, except 16.
29. Chapter 9, Section 3, problems 34-44