NAME:
STUDENT ID:
This exam is 3 hours long.
INSTRUCTIONS
RYERSON UNIVERSITY DEPARTMENT OF COMPUTER SCIENCE
CPS 420 FINAL EXAM WINTER 2018
This exam is out of 75 and is worth 40% of the course mark.
This is a closed book exam. However, one double-sided letter-sized crib sheet is allowed. No other aids are allowed.
This exam is single-sided and has 7 pages including this front page.
Please answer all questions directly on this exam.
The exam is divided into 4 parts ordered chronologically as the material was covered in the course. You might find it helpful to read the whole exam and start with the sections you find easiest.
For Grading Purposes
A1-2
/10
A3
/10
B
/10
C
/20
D1-3
/15
D4
/10
CPS 420 W2018 FINAL 2
PART A – INDUCTION AND RECURSION – 20 MARKS
Given the sequence an defined recursively as follows: a0 = 1
an =2n-an-1 forn1
A1 Terms of a Sequence (5 marks)
Calculate a1, a2, a3, a4, a5
Keep your intermediate answers as you may need them in the next question.
A2 Iteration (5 marks)
Based on the results of question A1, solve the recurrence relation when n0 (i.e. find an analytic formula for an). Simplify your answer as much as possible, showing your work and quoting any formula or rule that you use. Your final answer should not contain sums and products.
CPS 420 W2018 FINAL 3
A3 Induction (10 marks)
Prove by mathematical (weak) induction that for every integer n1,
∑𝑛 𝑖.2𝑖=(𝑛−1)2𝑛+1+2 𝑖=1
No other method is acceptable.
Be sure to lay out your proof clearly and correctly and to justify every step.
CPS 420 W2018 FINAL 4 PART B – GRAPH THEORY – 10 MARKS
B1. Matrices in Graph Theory (6 marks)
a)
On the diagram on the right, draw the directed graph G described by the adjacency matrix on the left (i.e. add the edges in G)
0 1 2 3
0123
0100
1001
0100
0
31
0010 2
a)
Fill out the following matrix A which is defined as follows:
A(i,j) = number of walks of length 2 from vertex i to vertex j in the graph G.
0123
0 1 2 3
Minimum Spanning Tree (4 marks)
B2.
On the diagram on the right, draw a minimum spanning tree of the weighted graph on the left (i.e. draw the edges you are keeping with their weights),
A5B AB
F 3 C F C
E D E D The edge numbers are weights
2
CPS 420 W2018 FINAL 5
PART C – REGULAR EXPRESSIONS AND FINITE STATE AUTOMATA – 20 MARKS
Given the alphabet ∑={0,1,2,3,4,5,6,7,8,9}, define the following two languages over ∑*: L1 = {xN, 5|x} and L2 = N- L1
Elements of L1 and L2 are represented in base ten without leading 0s, except for zero which is simply the single digit 0.
Please note that all the questions in this part of the exam are related. They have been ordered in an order that facilitates answering them but it is possible to answer them independently. Therefore you can answer these questions in the order that makes the most sense to you.
C1
a)
b)
C2
a)
Regular Expressions (6 marks)
Write a regular expression denoting L1.
Write a regular expression denoting L2.
Finite State Automata (14 marks)
Draw a state diagram (= deterministic finite state automaton) with as few states as possible which recognizes L1. This state diagram should be complete: it should handle all strings of digits.
b)
Draw a state diagram (= deterministic finite state automaton) with as few states as possible which recognizes L2. This state diagram should be complete: it should handle all strings of digits.
CPS 420 W2018 FINAL 6 PART D – COUNTING AND PROBABILITIES – 25 MARKS
In this entire section, you should simplify your calculations as much as possible. Fractions should also be simplified as much as possible but can remain fractions.
D1 Final Exam Grades (6 marks)
There are 179 students currently registered in CPS420. This final exam is graded out of 75. For the purposes of this question you can assume that all the grades are integers.
If you know that at most 10 students will get a grade strictly below 20, what is the least number of final exams that will need to be graded to guarantee that at least 2 students in this class have the same grade in this final exam? Explain your answer.
D2 Lottery tickets (4 marks)
A lottery sells 20,000 tickets at $2 each. There are:
1 prize of $10,000
10 prizes of $50
100 prizes of $2
What is the expected value of this lottery? Explain your answer.
D3 Bingo (5marks)
A bingo ball contains 75 tokens numbered from 1 to 75. The game host draws a token randomly from the ball but simply says that the number has no repeating digits. What is the probability that the number drawn was even? Explain your answer.
CPS 420 W2018 FINAL 7
D4 Lake Couchiching (10 marks)
Lake Couchiching is a medium sized lake just to the North of Lake Simcoe. We will look at anagrams of COUCHICHING. An anagram of a word is a new word that is formed by rearranging the letters of the original word. For example MITE is an anagram of TIME. Anagrams do not have to be real words.
a) How many different anagrams of the word COUCHICHING are there? (including COUCHICHING)
Explain your answer.
b) How many of these begin with C or I? Explain your answer.
c) What is the probability that a random anagram of COUCHICHING (including COUCHICHING itself) will start with C or I? Explain your answer.