Discrete Mathematics for Computer Scientists -- Example Exam QuestionsDIT980, HT 2015
Home | Schedule | Assignments | Exercises | Exam | AboutFire | Forum | TimeEdit | Links | 2014
The exam will consist of 7 questions. For each question, you can get 0, 1, or 2 points: 2 points if your answer is good enough (small mistakes allowed); 1 point if there were some good parts, but also some parts missing; 0 points if your answer is not good enough.

A total of 7-10 points will get you a G. 11-14 points will get you a VG.

Here are some example questions you may encounter.

Any of the base exercises, from any of the weeks (mostly taken from the book).

• calculating sets,

• calculating truth tables,

• calculating gcd, Bezout, Chinese Remainder,

• calculating Euclidian cycles, topological sorts,

• calculating number of possibilities, probabilities.

• For example questions on predicate logic, see the exercises on predicate logic (pdf).

For some more example questions, see the mini-exam (pdf).

The following are adapted from our exercises. The answers can be found in the answers to those exercises.

Q. Give an example of a function f : ℕ -> ℕ that is injective but not surjective. Explain why it is injective and why it is not surjective.

Q. Give an example of a function g : ℕ -> ℕ that is surjective but not injective. Explain why it is surjective and why it is not injective.

Q. Which of the following set operations: union, intersection ("snitt"), difference are associative and/or commutative? Explain.

Q. Give an example of an operator f : ℕ x ℕ -> ℕ that is associative but not commutative. Explain.

Q. Give an example of an operator f : ℕ x ℕ -> ℕ that is commutative but not associative. Explain.

Q. We are going to look at formulas that have the shape:

∀ x : (A(x) -> B(x))

(a.) Find an example of such a formula that is false. Show that it is false.

(b.) Find an example of such a formula that is true. Show that it is true.

(Don't forget to think about the universe.)

Q. We are going to look at formulas that have the shape:

∃ x : (A(x) /\ B(x))

(a.) Find an example of such a formula that is false. Show that it is false.

(b.) Find an example of such a formula that is true. Show that it is true.

(Don't forget to think about the universe.)

Q. Simplify the following formula:

(p /\ q) -> q

Q. Simplify the following formula:

p -> (p /\ q)

Q. (a.) Is logical implication (->) commutative and/or associative?

(b.) Is logical equivalence (<->) commutative and/or associative?

Explain.

Q. Show by induction over n that 8n - 3n is divisible by 5, for all n ≥ 1.

Q. Show by induction over n that 1⋅2 + 2⋅3 + 3⋅4 + ... + n⋅(n+1) = n(n+1)(n+2)/3, for all n ≥ 1.

Q. Show by induction over that 4n < 2n, for all n ≥ 5.

Q. Take a look at the following recursive function definition for f : ℕ+ x ℕ -> ℕ:

f(x,0) = 1
f(x,n) = f(x,n/2)2   ,   if n > 0 and n is even
f(x,n) = x⋅f(x,n-1)   ,   if n is odd

Prove that f(x,n) = xn for all x>0 and all n≥0, by induction over n.

Q.> Consider the following two diophantine equations. For each one, explain whether or not it has a solution. If there are any solutions, give three different solutions.

(a) 17x + 22y = 6

(b) 22x - 55y = 13

Q. Consider the following three congruences:

x ≡ 1 (mod 3)

x ≡ 2 (mod 5)

x ≡ 3 (mod 7)

(a) Find an integer x that satisfies all three congruences simultaneously. Use the Chinese Remainder Theorem, and explain how you reached your solution, step by step.

(b) What solutions are there such that 0 ≤ x ≤ 200?

Q. Look at the following relation:

• R1(x,y) = x | y     (divisability)

(a) Is it reflexive?

(b) Is it symmetric?

(c) Is it transitive?

(d) Is it an equivalence relation?

Q. Look at the following relation:

• R2(x,y) = gcd(x,y)=1     (having no divisors in common)

(a) Is it reflexive?

(b) Is it symmetric?

(c) Is it transitive?

(d) Is it an equivalence relation?

Q. Show that if p is a prime number > 3, then 24 | p2-1.

Hint: Use a case split on what the remainder (rest) of p can be when dividing it by 6.

Q. Show the following: If we have a prime number p such that p | a2, then we also have p2 | a2.

Q. Prove or disprove: If we have a natural number n such that n | a2, then we also have n2 | a2.

Q. For what numbers m do we have that m2-1 is a prime number?

Hint: m2-1 = (m+1)(m-1)

Q. We have a natural number n > 1 that is not a prime number. Show that there must be a natural number b, such that 1 < b ≤ √n and b | n.

Q. Show that if we have a ≡ b (mod mn) then we also have a ≡ b (mod n).

Some code:

```  elem :: Eq a => a -> [a] -> Bool
x `elem` []     = False
x `elem` (y:ys) = x==y || (x `elem` ys)

(++) :: [a] -> [a] -> [a]
[]     ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

rev :: [a] -> [a]
rev []     = []
rev (x:xs) = rev xs ++ [x]

length :: [a] -> Integer
length []     = 0
length (x:xs) = 1 + length xs

take :: Integer -> [a] -> [a]
take n _  | n <= 0 = []
take n []          = []
take n (x:xs)      = x : take (n-1) xs
```

Q. Prove that, for all x and all lists xs, ys:

```  x `elem` (xs ++ ys) = (x `elem` xs) || (x `elem` ys)
```

Q. Prove that, for all lists xs:

```  length (rev xs) = length xs
```
Hint: You need a property about length and ++ as a lemma. Please state this property clearly. You do not need to prove it!

Some more code. Here, we define a datatype for trees. The flatten function takes a tree and produces a list of all the elements in the tree. The swap function works the same as in the lecture. The size function computes the number of nodes in a tree.

```  data Tree a = Empty | Node a (Tree a) (Tree a)

flatten :: Tree a -> [a]
flatten Empty        = []
flatten (Node x p q) = flatten p ++ [x] ++ flatten q

swap :: Tree a -> Tree a
swap Empty        = Empty
swap (Node x p q) = Node x (swap q) (swap p)

size :: Tree a -> Integer
size Empty        = 0
size (Node _ p q) = 1 + size p + size q
```

Q. Prove that, for all trees p:

```  size p = length (flatten p)
```

Q. Take a look at Figure 7.3 in the book (page 192), where you can see 5 examples of graphs. Which of these graphs have an Eulercycle and which ones don't?

For the ones that have an Eulercycle, construct the cycle.

Q. Given a simple graph G. Define the relation R(u,v) between nodes u and v of G as follows:

R(u,v) = "there is a path from u to v in G"

Show that R is an equivalence relation.

Q. Prove that a tree with n nodes has exactly n-1 edges.

Hint: Use strong induction on the number of nodes n. In the induction step, remove one edge from the graph, and see what happens. How many components do you get?

Q. Take a look at Fig. 7.8 and 7.9 from the book (page 200-201), where you can see two examples of directed graphs. Which of these has a topological ordering and which doesn't?

For the graph that has a topological ordering, construct one. Q. Take a look at the graph in the above figure. How many topological orderings are there for this graph? Explain how you arrived at tour answer.

Q. Given a directed graph G.

Define the relation R(u,v) between nodes u and v of G as follows:

R(u,v) = "there is a directed path from u to v in G"

What properties does or doesn't R have: reflexivity, symmetry, transitivity? Explain.

Q. You roll 3 dice. What is the probability that the three values that turn up are all different? What is the probability that there are at least two dice with the same value?

Q. You roll n dice. What is the probability that there are at least two dice with the same value?

Q. Given a prime number p. Show that

 ( p ) k
is divisable by p for all 0 < k < p.

Does this also hold when p is not prime?

Q. Given the set A = {1,2,3,4,5}. How many strictly sorted lists are there of length 3 where all the elements come from the set A? A list is strictly sorted if the list is sorted, and no two elements are the same.

How many strictly sorted lists are there if A={1,2,3,...,n}, and the list length is k?

Q. Prove Fermat's little theorem, namely that

ap ≡ a (mod p)

for any prime number p, and any natural number a.

We have actually already proved this in the lecture. This time, do it by induction on a.

Let me help you: The base case (a=0) is easy: 0p ≡ 0 (mod p) for any p > 0.

The step case assumes that kp ≡ k (mod p) (this is the induction hypothesis), and has to show that

(k+1)p ≡ (k+1) (mod p)
Luckily, we have now learned how to expand the expression (k+1)p, which should help you finish the proof.

Hint: Make use of the following: If p is a prime number, then

 ( p ) k
is divisable by p for all 0 < k < p. (You do not have to prove this.)

Q. Prove:

 ( n ) + ( n ) = ( n+1 ) k k+1 k+1
...by using the definition of the choose function ("över") and manipulating the factorials.

Q. You are taking a course with 54 students (including you). For the exercise sessions, you are randomly divided into 9 groups of size 6. You are secretly in love with one of your classmates (not yourself). What is the probability that the two of you end up in the same group?

Q. How many undirected graphs exist that have n distinct nodes?

Q. Given a directed graph that is a bijection. This means that every node has exactly one outgoing arrow, and exactly one ingoing arrow. What is the probability that there is a cycle in the graph?