math vic
RiverFlowsInYou
PracticeQuestionssolutions.pdf
Practice Exam Solutions
1.1/1.3 (1.1/1.2) Prove p q q p semantically (using a truth table) and syntactically (using the accepted table of equivalences)
p q p q q p
T T F F
T F F F
F T T T
F F F F
1. p q 1. Given
2. p q 2. DeMorgan
3. p q 3. Double Negation
4. q p 4. Commutative Property
12.1-12.4 (11.1-11.4) Consider the Boolean function given by the table below.
x y z F(x,y,z)
1 1 1 0
1 1 0 1
1 0 1 0
1 0 0 1
0 1 1 0
0 1 0 0
0 0 1 1
0 0 0 1
a) Find the sum-of-products expansion for F. x yz x y z x y z x y z
b) Simplify your answer to a) using a Karnaugh map.
xz x y
c) Simplify your answer to a) using the Quine-McCluskey Method
1. 110
2. 100
3. 001
4. 000
x y z
x y z
x y z
x y z
1_ 0 {1, 2}
_ 00 2, 4
00 _ 3, 4
1 _ 0 and 00 _ cover all minterms. xz x y
d) Design a circuit that represents this Boolean function.
13.2 (12.2) Design a finite-state machine that meets the following specifications
The keypad only has the digits 0 and 1, and an “enter” key.
The user types in his password, then hits “enter”
For each digit the user types, display a The user’s password is 01
If the user enters the password correctly, display “In!”
If the user enters the password incorrectly, display “Out!” and accept no more input.
13.3/13.4 (12.3/12.4) For each of the descriptions below, construct an FSA and a regular expression. Assume
the alphabet is {0,1}
a) All strings that start with 0 and end with 1. *
0 0 1 1
b) All strings that have an odd length. *
0 1 0 1 0 1
c) All strings that contain exactly one 1. * *
0 10
d) All strings that do not contain exactly one 1. ** * *
0 0 10 1 0 1
1.5 (1.4) Determine the truth value of each of the following. Give a brief explanation justifying each answer.
Assume the domain of x and y is the nonnegative integers.
a) 2x y x y True. You can always find an integer bigger than any given integer.
b) 2y x x y False. There is no biggest number.
c) ( 1)y x x y x x True. Let 0y and note that x y is always false.
d) 0 1 ( 1)y x y y x y x x False. For any 1y , pick 1x
1.5. (1.4) Translate the following into first order logic. Let )( xP : x is prime, )(xE : x is even
a) All primes are odd. ( ) ( )x P x E x
b) All primes greater than 2 are odd. ( ) 2 ( )x P x x E x
c) Some primes greater than 2 are even. 2 ( ) ( )x x P x E x
d) There is a biggest prime. ( ) ( )x P x y P y y x
e) There are infinitely many primes. ( ) ( )x P x y P y y x OR ( )x y P y y x
f) There is exactly one prime number. ( ) ( )x P x y P y x y
g) There are exactly two prime numbers. ( ) ( ) ( )x y P x P y x y z P z x z y z
1.6. (1.5) One of the arguments below is valid and one is invalid. Identify the valid one and prove its validity
using the accepted rules of inference. Each line of your proof should only invoke one rule. Do not skip any
steps.
p r
q r
q r
p
p r
q r
r
p q
The first one is invalid. Let , ,p T q T r T . The premises are true
and the conclusion is false.
1. p r 1. Given
2. q r 2. Given
3. r 3. Given 4. p 4. Modus Tollens 3,1
5. p 5. Double Negation 4
6. q 6. Modus Tollens 3,2
7. p q 7. Conjunction 5, 6
1.7 (1.6). a) Prove The sum of two odd numbers is even (or more formally, if m is
odd and n is odd, then m + n is even)
Assume m is odd and n is odd.
By definition 2 1m k and 2 1n k for some k and k
2 1 2 1 2 2 2 2 1 2m n k k k k k k k where 1k k k
b) Give a proof by contraposition of the theorem: If n is odd, then n-2 is odd.
Assume n-2 is not odd. Then n-2 is even, so 2 2n k for some k.
So, 2 2 2 1 2n k k k where 1k k . Hence, n is even, so n is not odd.
5.1/5.2 (4.1/4.2)
a) Prove by mathematical induction that 2 4 6 ... 2 1n n n
Note 2 1 1 1 1
Assume 2 4 6 ... 2 1 1 1 1n n n .
Then 22 4 6 ... 2 1 1n n n n n
So, 22 4 6 ... 2 1 2 1 2n n n n n n n
Hence, 22 4 6 ... 2 1 1n n n n n n n QED
b) Prove by strong induction that every amount of postage of 8 cents or more can by formed using just 3-cent
and 5-cent stamps.
Note
8 1 3 1 5
9 3 3 0 5
10 0 3 2 5
Assume that for all k with 8k and k n ,there exist a and b such that
3 5k a b
For 3k n , let a and b be such that 3 3 5n a b
Then 3 3 5 1 3 5 3 5n a b a b a b where 1a a QED
c) Let 1 2 1 21, 2, 2n n na a a a a .
i) Compute 3 4 ,a a and
5 a
3
3a , 4
4a and 5
5a
ii) Use strong induction to prove that 1 n
n a n
Note: 1
1 1 1 1a ,
2
2 2 2 1a
Assume for all k with 2k and k n that 1 k
k a k
In particular, for 1k n , 1
1 1 1
n
n a n
and for 2k n ,
2
1 2 1
n
n a n
1 2 2 2
1 2
2 1 1
2 2 1 ( 1) 2 ( 1) 1 2 1 ( 1) 1 2 ( 1)
1 1 2 1 1 2 1 2 2 2 1 ( ) 1
n n n n
n n n
n n n n
a a a n n n n
n n n n n n
A3/3.1 Describe a non-recursive algorithm that takes a list of distinct integers 1 2 , ,...,
n a a a and finds the number
of primes in the list. Write your answer in pseudo-code or any well known procedural language like Python,
Java, C++, ….
You may assume that a function "prime?" has been defined, where
"prime?" applied to an prime number returns TRUE and "prime?" applied to a composite number returns
FALSE.
procedure Number_of_primes ( 1 2 , ,..., :
n a a a integers)
count = 0
for i = 1 to n
if ( i
a is prime) count = count + 1
return count
5.4 (4.4) Describe a recursive algorithm that takes a list L of distinct integers and finds the number of primes in
the list. Write your answer in pseudo-code or any well known procedural language like Python, Java, C++, ….
Assume that you have the following three functions that operate on lists.
i) "empty?" which returns TRUE if a given list is empty, FALSE otherwise
ii) "first" which returns the first element of a given nonempty list.
iii) "rest" which returns a list containing all but the first element of a given nonempty list.
Note that if the list has only one element, "rest" will return the empty list.
procedure Number_of_primes (L :list of integers)
if (L is empty) return 0
else if (first(L) is prime) return 1 + Number_of_primes(rest(L))
else return Number_of_primes(rest(L))
5.4 (4.4) Describe a recursive algorithm to generate the nth term of the sequence
1 2 1 21, 2, 2n n na a a a a procedure nth-term(n: positive integer)
if (n=1) return -1
else if (n=2) return 2
else return –(2nth-term(n-1) + nth-term(n-2))
3.2 a) Find C and k that shows 123 23
xxx is 3xO
3 3
3 3x x always
2 3
2x x when 2x
3
x x when 1x
3
1 x when 1x
3 2 3 3 3 3 3
3 2 1 3 6x x x x x x x x when 2x . 6, 2C k
OR
3 3
3 3x x always
2 3
2 2x x when 1x
3
x x when 1x
3
1 x when 1x
3 2 3 3 3 3 3
3 2 1 3 2 7x x x x x x x x when 1x . 7, 1C k
b) Find C and k that shows that 222
...21 n is 3nO
2 2 2 2 2 2 2 3
1 2 ... ...n n n n n n n when 1n . 1, 1C k
c) Rearrange the following functions so that each function is big-Oh of the next function:
2
, 1000 log( ), log( ), 2 !, 2 , , 3 n n
n n n n n n
2
1000 log( ) log( ) 2 3 2 ! n n
n n n n n n
3.3 Give big-Theta estimates for the number of comparisons in the following algorithms
procedure matrix-max (A: an n n matrix with integer entries)
max = 0
for row = 1 to n
for col = 1 to n
if A(row,col) > max then max = A(row,col) // A(row,col) gives entry in matrix with given row and column
return max
n loop inside of an n loop. 2n
procedure some-procedure_1(some inputs)
for i = 0 to 1n
for j = n to 1i step 1
some comparison
return something
n loop inside of an n loop. 2n
procedure some-procedure_2(some inputs)
for i = 0 to 1n
for j = 1 to 100
some comparison
return something
Constant loop inside of an n loop. n
8.3 (7.3) a) Problem: Find whether an interesting number is in a list
Algorithm: If the list is size 1, do a comparison to determine if the number in the list is interesting
For bigger lists, split into three roughly equally sized pieces, do 4 comparison to find the two best
candidates, then run this algorithm on those two lists.
Give a big-Theta estimate for the number of comparisons used for the algorithm.
3( ) 2 5nT n T
2, 3, 5, 0a b c d .
Since 0
2 5 , 3log 2n by the Master Theorem.
For the following three algorithms, give a big-Theta estimate for the number of multiplications used.
b) procedure naïve-pow (a: integer, n :non-negative integer)
if n = 0, return 1 else return a naïve-pow(a, )1n
Note that the Master Theorem does not apply here. It will take one
multiplication for each n. n
c) procedure better-pow((a: integer, n :non-negative integer, power of 2)
if n = 0, return 1
else return (better-pow (a, )2/n )2
2( ) 1nT n T 1, 2, 1, 0a b c d
Since 0
1 2 , 0 log logn n n by the Master Theorem.
d) procedure better-pow2((a: integer, n :non-negative integer, power of 2)
if n = 0, return 1
else if n is even return better-pow (a, )2/n better-pow (a, )2/n
2( ) 2 1nT n T 2, 2, 1, 0a b c d
Since 0
2 1 , 2log 2n n by the Master Theorem. Note the similarities between this algorithm and the previous one, yet
they have significantly different complexities.
6.1 (5.1) Consider all bit strings of length 12.
a) How many begin with 110?
9 choices to make, 2 options per choice: 9
2
b) How many being with 11 and end with 10?
8 choices to make, 2 options per choice: 8
2
c) How many begin with 11 or end with 10?
Subtract off the bit strings that were double counted: 10 10 8
2 2 2
6.2 (5.2) A company stores products in a warehouse. Bins are specified by aisle, location in aisle and shelf.
There are 2 aisles, 3 shelves per aisle and 4 locations per shelf.
a) Objects come into the warehouse and are thrown randomly into a location. What is the least number of
products needed to guarantee that at least 3 products are stored in the same location?
There are 4 3 2 24 different locations in the warehouse. It is possible to distribute 48 products so that each location has two products. Once we
add the 49th object, one bin will have at least 3 products.
b) Given that the company has 1,000 products find the smallest value of n such that every location has either n
or 1n items.
1000
24 41
If the items are distributed as evenly as possible, each location
will have at least 41 or 42 items.
6.3 (5.3) You have 15 novels, 10 history books and 5 math books. Assume that all 30 books are different.
a) How many ways can you loan three history books and seven novels to a friend?
10 15
3 7
b) How many ways can you put the 30 books in a row on a shelf if the novels are on the left, the math books are
in the middle and the history books are on the right?
15! 5! 10!
6.4 (5.4)
a) Use the binomial theorem to prove that
100 100 100 100 100 100 100 100 100 100 100 100
... ... 0 2 4 6 98 100 1 3 5 7 97 99
The statement is equivalent to
100 100 100 100 100 100 100 100 ... 0
0 1 2 3 97 98 99 100
, or
100
0
100 1
i
i i
.
Plugging in to the Binomial Theorem with 100, 1, 1n x y
gives 100
100 100
0
100 1 1 1 0 0
i
i i
b) Prove that 2
2 2
2 2
n n n
Using the definition.
2
2 2 ! 2 2 1 2 2 ! 2 2 1 2 1 2
2 2! 2 2 ! 2! 2 2 ! 2
n n n n n n n n n n n
n n
2 2 2 2 2
1 2 !! 2 2 2 1 2
2 2! 2 ! 2! 2 !
n n n nn n n n n n n n n
n n
Story proof:
You have n girls and n boys and you want to pick 2 of them.
You can either
i) choose 2 of the 2n children (left hand side) OR
ii) choose 2 girls or 2 boys or one of each
2
2 2 2 2
n n n n n n
6.5 (5.5) You have a bowl containing candies: 50 cherry, 40 orange and 30 pineapple.
a) How many ways to pick 15 candies?
15 *’s, 2 |’s. 17
2
or 17
15
b) How many ways to pick 15 candies with at least two of each flavor?
First pick 2 of each, then count how many ways to pick the remaining 9.
9 *’s, 2 |’s. 11
2
or 11
9
c) How many different strings can be made from the letters ABBCCCDDDD?
10!
1! 2! 3! 4!
8.5 (7.5) Among 18 students in a room, 7 study mathematics, 10 study science, and 10 study computer
programming. Also, 3 study mathematics and science, 4 study mathematics and computer programming, and 5
study science and computer programming. We know that 1 student studies all three subjects. How many of
these students study none of the three subjects?
18 7 10 10 3 4 5 1 2x x
8.6 (7.6)
a) How many solutions in integers? 1 2
30x x , 1 2
5 15, 7 17x x
This is the same as having to pick 30 donuts of two types, with
restrictions on how many of each type are allowed. Say the two types of
donuts are glazed and old-fashioned.
First, pick the 5 glazed and 7 old-fashioned donuts. This leaves 18
(=30 5 7) donuts left with at most 10 glazed and at most 10 old-fashioned,
or 1 2
18x x , 1 2
10, 10x x
Let 1
P be the property 1
10x and let 2
P be the property 2
10x
1 2 1 2 1 2, ,N P P N N P N P N P P
N the number of ways to pick 18 donuts from two types with no restrictions.
18 *’s, 1 |: 19
1 N
1N P the number ways to pick at least 11 glazed donuts. Pick the 11 glazed first, then pick anything for the remaining 7.
7 *’s, 1 |: 1 8
1 N P
Similarly, 2 8
1 N P
1 2,N P P the number of ways to pick 18 donuts with at least 11 glazed and
11 old-fashioned. This is impossible, so 1 2, 0N P P
1 2 19 8 8
, 0 3 1 7 7
N P P
b) How many onto functions from a set with 7 elements to a set with 3 elements?
Call the three elements a, b, and c.
Let 1
P be the property that a is in the range,
2 P be the property that b is in the range, and
3 P be the property that c is in the range.
1 2 3 1 2 3 1 2 1 3 2 3 1 2 3, , , , , , ,N P P P N N P N P N P N P P N P P N P P N P P P
N the number of functions from a 7 element set to a 3 element set with
no restrictions. 7
3N
1N P the number of ways to build a function no input having a as its output.
This means there are 2 choices for each input, or 7
2 .
Similarly, 72 2N P and 7
3 2N P
1 2,N P P the number of ways to build a function so that no input has a or
b as its output. That means that every input goes to c and 1 2, 1N P P
Similarly, 1 3, 1N P P and 2 3, 1N P P .
1 2 3, ,N P P P the number of ways to build a function so that no input has a, b or c as its output. This is impossible since the only possible outputs
are a, b, and c. 1 2 3, , 0N P P P
7 7 7 71 2 3, , 3 2 2 2 1 1 1 0 1,806N P P P
7.1 (6.1) a) A fair coin is flipped 6 times. What is the probability
i) Heads will come up all 6 times? 6
1
2
ii) Heads will come up exactly 4 times? 6
6
4
2
10.2 Are the two graphs below isomorphic?
No. In the graph on the left, vertex 7 has degree 2 and is connected
to two vertices of degree 4. The graph on the right has no vertices
with this property.
10.1 – 10.6, 11.4 (9.1 – 9.6, 10.4) Consider the graph with the following adjacency list
Vertex Adjacent Vertices
a b,c
b a, c, d, e
c a, b, d, e
d b,c,e
e b,c,d
a) Draw the graph. (10.3/9.3)
b) Represent the graph as an adjacency matrix. (10.3/9.3)
c) Represent the graph as an incidence matrix. (10.3/9.3)
d) Is an Eulerian circuit possible? If so, give one. If not, remove a minimal number of edges to make one
possible, then give one in your new graph. (10.5/9.5)
Not possible. Vertices d and e each have odd degree. Remove edge [d,e] and a circuit is possible.
E.g. a, b, c, d, b, e, c, a
e) Is an Eulerian path possible? If so, give one. If not, remove a minimal number of edges to make one
possible, then give one in your new graph. (10.5/9.5)
Since vertices d and e are the only ones with odd degree, an
Eularian path is possible. Note that these have to be the starting
and ending vertices.
E.g. d, b, a, c, b, e, c, d, e
For the next two problems, keep only edges [a,b], [a,c], [c,d], [c,e] and [d,e].
f) Use a breadth-first search to find a spanning tree for this graph. Resolve all ties alphabetically. Represent
your answer as a rooted tree. (11.4/10.4)
g) Use a depth-first search to find a spanning tree for this graph. Resolve all ties alphabetically. Represent your
answer as a rooted tree. (11.4/10.4)
11.2 (10.2) A document consists entirely of words that can be made from the letters e, t, a, and n. The frequency
of those letters are 40%, 35%, 20% and 5% respectively.
a) Devise a Huffman code for this document.
:1, : 01, : 000, : 001e t a n
b) Encode the word eaten using your answer from a)
1000011001
c) On average, how many bits are needed to encode a character.
0.40 1 0.35 2 0.20 3 0.05 3 1.85 bits/character
11.3 (10.3) a) Give the prefix, infix and postfix expressions corresponding to the following tree
Prefix: -**ab+cde, or in LISP (- (* (* a b) (+ c d)) e)
Infix: a*b*c+d-e or parenthesized [(a*b)*(c+d)] – e
Postfix: ab*cd+*e-
b) For the prefix expression 2 2 2 2 2 2
i) Evaluate 2 2 2 2 2 2 40
ii) Draw the parse-tree
iii) Write in infix: 2 2 2 2 2 2
9.2 (8.2) Using the database passed out in class,
a) construct a SQL query that lists all of the addresses of orders fulfilled by Al Einstein
SELECT Address
FROM Vendors, Orders, Products, Customers
WHERE Vendor_Name = Al Einstein
b) describe in English what the following SQL query returns
SELECT Customer_Names
FROM Orders, Products, Customers
WHERE Price > $50.00
A list of names of all customers who purchased an item costing more
than $50.00
10.6/11.5 (9.6/10.5) Consider the graph below
(https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/04GreedyAlgorithmsII.pdf)
Resolve all ties numerically.
a) Use Djikstra’s algorithm to find the shortest distance from vertex 0 to all of the other vertices. (10.6/9.6) Vertices added in order.
Shortest path from 0 to
1: [0,1]
7: [0,7]
4: [0,4]
5: [0,4,5]
2: [0,4,5,2]
3: [0,4,5,2,3]
6: [0,4,5,2,6]
For the problems below, ignore the arrows and assume that the graph is undirected.
b) Use Prim’s algorithm to find a minimum spanning tree. (11.5/10.5) [2,5],[2,3],[4,5],[4,7],[1,7],[0,1],[3,6]
c) Use Kruskal’s algorithm to find a minimum spanning tree. (11.5/10.5)
[2,5],[2,3],[1,7],[4,5],[4,7],[0,1],[3,6]
9.4/9.5 (8.4/8.5) Consider the following relation: ),(),,(),,(,,,, deadecebcbR , and find the matrix representation of the following. (Make sure you can also find the ordered pair representation and the digraph
representation).
a) Reflexive closure of R.
, , , , ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , )b c b e c e d a e d a a b b c c d d e e
b) Symmetric closure of R.
, , , , ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , )b c b e c e d a e d c b e b e c a d d e
c) Transitive closure of R (use Warshall’s algorithm)
, , , , ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , )( , )b c b e c e d a e d b a b d c d c a e a Note that the first row and second column only have 0’s, so
we just need to run Warshall’s algorithm for
3rd row, 3rd column, 4th row, 4th column and 5th row, 5th column.
3rd row, 3rd column (nothing changes)
4th row, 4th column (added edge [e,a])
5th row, 5th column (added edges [b,a], [c,a], [b,d], [c,d])
d) The smallest equivalence relation that contains R.
( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , )
( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , )}
a a a b a c a d a e b a b b b c b d b e c a c b c c c d c e
d a d b d c d d d e e a e b e c e d e e
4.3/3.7 a) Find gcd 212121,121212 3030303
21212121 1 12121212 9090909
12121212 1 9090909 3030303
9090909 3 3030303
b) Find integers a and b such that 212121 121212 gcd 212121,121212a b
9090909 21212121 1 12121212
12121212 1 9090909 3030303
4.3/3.7 a) You have an 8-gallon jug and a 37-gallon jug, and an unlimited supply of water. How would you use
the jugs to make exactly 1 gallon of water?
37 4 8 5
8 1 5 3
5 1 3 2
3 1 2 1
3 1 2 1 3 1 2 1 3 1 5 1 3 1 2 3 1 5 1
5 1 3 2 2 5 1 3
8 1 5 3 3 8 1 5 2 8 1 5 1 5 1 2 8 3 5 1
2 3 1 5 1
37 4 8 5 5 37 4 8 14 8 3 37 1
2 8 3 5 1
Keep filling the 8-gallon jug and pour it into the 37-gallon jug.
Whenever the 37-gallon jug is full, empty it.
Repeat this process until you have filled the 8-gallon jug 14 times and
emptied the 37-gallon jug 3 times. You will have 1 gallon of water left.
b) Use your answer from part a) to solve the equation 8 3 0 mod 37x . Express your answer in the form
mod 37x a where 0 37a .
8 3 0 mod 37
8 3 mod 37
14 8 14 3 mod 37
1 42 mod 37
32 mod 37
x
x
x
x
x
c) Find the two largest negative solutions and the two smallest positive solutions to the congruences
2 mod 3x , 3mod 4x and 4 mod 5x
2 mod 3 3 2x x k
3 2
3 2 3 mod 4 3 mod 4 4 3 3 mod 4
x k k k k l
x
3 2
3 4 3 2 12 11 4 3
x k x l x l
k l
4 mod 5
12 11 4 mod 5 2 1 1mod 5 4 mod 5 5 4 12 11
x l l l l m
x l
12 11
12 5 4 11 60 59 5 4
x l x m x m
l m
The two largest negative solutions occur when 1m and 2m , i.e. when
1x and 61x .
The two smallest positive solutions occur when 0m and 1m , i.e, when
59x and 119x .
