NAME:
STUDENT ID:
This exam is 3 hours long.
INSTRUCTIONS
RYERSON UNIVERSITY DEPARTMENT OF COMPUTER SCIENCE
CPS 420 FINAL EXAM WINTER 2017
This exam is out of 80 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 8 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-2
/12
D3
/11
D4
/7
CPS 420 W2017 FINAL 2
PART A – INDUCTION AND RECURSION – 20 MARKS
Given the sequence an defined recursively as follows: a0 = 1
an =3an-1+2forn1
A1 Terms of a Sequence (5 marks)
Calculate a1, a2, a3, a4, a5
Keep your intermediate answers as you will need them in the next question.
A2 Iteration (5 marks)
Using iteration, solve the recurrence relation when n1 (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. In particular, your final answer should not contain sums and products.
You can use this formula without proving it: for any positive integers b and n with b1, ∑𝑛 𝑏𝑖=𝑏𝑛+1−1
𝑖=0 𝑏−1
CPS 420 W2017 FINAL 3
A3 Induction (10 marks)
Given the sequence bn defined recursively as follows: b0 = 1
bn= 𝑏𝑛−1 forn1 1+2𝑏𝑛−1
Prove by weak induction that for every n0, bn = 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 W2017 FINAL 4 PART B – GRAPH THEORY – 10 MARKS
B1 Drawing Graphs (10 marks)
In each of the following questions, either draw a graph with the given specifications or explain why no such graph exists.
a) Build a graph which is not connected and had 6 vertices and 12 edges
b) Build a graph which is connected, has 6 vertices, 5 edges, and a circuit.
c) Build a tree with 6 vertices and 6 edges:
d) Build a forest with 8 vertices and 5 edges
e) Build a graph with 6 vertices and 5 edges which is not a tree.
CPS 420 W2017 FINAL 5
PART C – REGULAR EXPRESSIONS AND FINITE STATE AUTOMATA – 20 MARKS
Let L1 be the language of the binary representations of all positive integers divisible by 4. Let L2 be the language of the binary representations of all positive integers not divisible by 4.
None of the elements of these languages have leading zeroes.
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 0’s and 1’s.
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 0’s and 1’s.
CPS 420 W2017 FINAL 6
PART D – COUNTING AND PROBABILITIES – 30 MARKS
In this entire section, you should simplify your calculations as much as possible
D1 Final Exam Grades (6 marks)
There are 168 students currently registered in CPS420. This final exam is graded out of 80. For the purposes of this question you can assume that all the marks are integers.
D2
Smart Hat (6 marks)
a)
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.
You want to make a bet that there will be a group of at least x CPS420 students who will all have the same grade on this exam. How large can you make x and still be guaranteed to win your bet? Explain your answer.
b)
A hat contains 25 tokens of identical size, shape and weight. The tokens are numbered from 1 to 25. Your friend draws a token randomly from the hat and tells you that its number has two digits. What is the probability that your friend drew a token with a prime number? Explain your answer.
Note that the set of all prime numbers between 1 and 25 is {2, 3, 5, 7, 11, 13, 17, 19, 23}
CPS 420 W2017 FINAL 7
D3 Anagrams (11 marks)
An anagram of a word is a new word that is formed by rearranging the letters of the original word. For example EVIL is an anagram of VILE.
a) How many different anagrams of the word KEEPER are there? (including KEEPER) Explain your answer.
b) How many of these begin with E or P? Explain your answer.
c) What is the probability that a random anagram of KEEPER (including KEEPER) will start with E or P? Explain your answer.
CPS 420 W2017 FINAL 8
D4
a)
Binomial Theorem (7 marks)
Finish drawing the first 5 lines of Pascal’s triangle by filling in the circles below with the missing values:
1
11 11 11 11
b) Use the drawing in part a) to show a full expansion of (2x+5)4. Show your intermediate steps.