Discrete Mathematics for Computer Scientists -- Example Exam Questions | DIT980, HT 2015 | ||||||||||||||||||

Home | Schedule | Assignments | Exercises | Exam | About | Fire | 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). These mostly are about calculating:
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 Show that your answer is correct with a truth table.
Q. Simplify the following formula: p -> (p /\ q) Show that your answer is correct with a truth table.
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 8
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 < 2
Q. Take a look at the following recursive function definition for f : ℕ
f(x,0) = 1
Prove that f(x,n) = x
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)(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: And answer the following questions: (a) Is it reflexive? (b) Is it symmetric? (c) Is it transitive? (d) Is it an equivalence relation?
Q. Look at the following relation: (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 | p 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 | a
Q. Prove or disprove: If we have a natural number n such that n | a
Q. For what numbers m do we have that m
Hint: m
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 xsHint: 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 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 a 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: 0
The step case assumes that k
(k+1)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 is divisable by p for all 0 < k < p. (You do not have to prove this.)
Q. Prove: ...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? |