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.