The final exam is comprehensive. You have 110 minutes for UNI finals. The questions you that can be certain will be on the exam are: 1. do the proof and list the reasons and step numbers for each step of the proof. mt modus tollens, mp modus ponens, DM DeMorgans, ds dysjunctive syllogism, imp implication, dn double negation, contra contrapositive are some of the rules you should review and rememorize. Distributive, commutative, associative are less often used, but you may notice in the Mercenary Motors calculator, they were used alot to get the number of gates (AND, OR and NOT) down from 27 gates to 5 gates. mt, mp, DM, ds, imp, dn, contra, hs, comm, assoc, dist, DM, mp, ds 2. hash tables and average successful search and average unsuccessful search performance value. terminology such as synonyms with respect to the hash function, collision and collision resolution strategy, home address, probes. 3. P(n, r) and C(n, r) and the counting things problems. Permutations and combinations. 4. Principle of inclusion/exclusion and Ghostbusters how many tools does Dr. Peter Venkman use, etc. Venn diagram needed for certain counts. Formula needed for missing count of 8. 5. Sets, cardinality of sets, binary relations on sets, cartesian products of sets, subsets, union, intersection, set difference, Venn diagrams, Powersets of a set. Cross products on sets. 6. Inductive proofs. Basis step and inductive step. The summation notation. Classical inductive proofs like 1 + 2 + 3 + ... + n = (n+1)(n) -------- and postage stamp inductive proofs that break down into 2 two cases.... VIP: LEARN THE PATTERN FOR INDUCTIVE PROOFS!!!!!!!!! ------- THERE ARE MANY EXAMPLES ON THE CLASS WEB PAGE..... ---- STUDY THEM and LEARN THE PATTERN. ----- ----------------- 7. Universal quantifiers and Existential quantifiers syntax. Upside down A for Universal. Backward E for existential. 8. Graphs, Weighted Graphs, Digraphs and non-directed graphs, matrix representation of graphs like we showed with Excel spreadsheets, similarity graphs, similarity levels and dissimilarity functions. Adjacency matrix for a graph, draw the graph from it. 9. Properties of binary relations. Reflexive, Symmetric, Transitive, Antisymmetric, Irreflexive. Composition of binary relations. 10. Binary trees. Preorder, inorder, postorder traversals. Average successful search performance for a given binary search tree. What is worst case average successful search performance for a binary search tree with 4 nodes? With 7 nodes? What is the best case average successful search performance for a tree with 4 nodes? With 7 nodes? How many different shaped trees are there that have 4 nodes? 5 nodes? 11. Composition of functions. f o g(x) and g o f(x). Range of a function, given a certain domain. f o f(x) and composition of a function on itself. 12. What is the partition of a set? How many partitions of the set S = {1, 2, 3} are there? How many of set T = {a, b, c, d} are there? 13. Kruskal's algorithm. List L. Partitions. Four steps of Kruskal's algorithm and the sorted list L of edges. Understand and memorize the actors and the steps for Kruskals, as given on the handout and the web site (not the textbook version). 14. Big Theta binary relation on functions and the time complexity of algorithms. Constant, logarithmic, linear, n log n, quadratic (squared), cubic, polynomial, exponential, and factorial. Growth rate of functions as a function of the size of the input or the problem, in terms of n. You won't need to find three numbers game Big Theta, but you should understand the general concept and your lecture notes. 15. The divides relation. 4 divides 16 but 4 does not divide 18. The mod function or remainder function. Floor and Ceiling functions. Log to the base 2 function. 16. Prove that the sum of any two odd numbers is an even number. Prove that the product of any two odd numbers is an odd integer. Prove that if x is odd and y is even, then x + y is odd. Prove that if x is an even integer and y is an odd integer, then xy (the product x times y) will be even. Prove that if x squared is odd, then x is odd. 17. Draw the Hasse diagram for this binary relation. 18. What is a POSET? What is an equivalence relation? rat, art or tar is which one? rst is which one? 19. When is a partially ordered set (POSET) called a total order or a total ordering of the sets elements? What has to be true? 20. How many comparisons would the selection sort make in sorting a list of 12 elements? Give the EXACT answer, please. How many passes would the selection sort make through a list of 10 numbers? What would the following array look like after the 1st and the 2nd pass of the selection sort algorithm were completed on the data. 21. What is the binary representation of 231 when converted into binary? What does 231 look like as a binary number? Show your work and way of arriving at the answer. What is the binary number 10101011 when converted into a base ten decimal number? 22. The cardinality of set A is m. The cardinality of set B is n. (Note: You will be given specific numbers for m and n, such as m = 3 and n = 4, for example). How many functions from set A to set B are there? How many functions from A to B are injective? How many functions from A to B are surjective? 23. Draw the initial HEAP that would be created by the first part of the HEAP SORT algoritm. Draw the picture of the binary tree as it would look after the two largest numbers are in their proper locations at the end of the tree (array) and the heap is formed again.