CS计算机代考程序代写 Finite State Automaton  This exam is 3 hours long.

 This exam is 3 hours long.
RYERSON UNIVERSITY DEPARTMENT OF COMPUTER SCIENCE
CPS 420 FINAL EXAM WINTER 2019
INSTRUCTIONS
 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 double-sided and has 12 pages including this front page. The last four pages are blank. Therefore there are 7 pages of questions: pages 2 to 8 inclusive.
 Please answer all questions directly on this exam. If you need extra space to finish answering questions, please do so on pages 9 to 12 and indicate very clearly on the original page of each question on which page the rest of your answer can be found.
 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.

PART A – INDUCTION AND RECURSION – 20 MARKS
Given the sequence an defined recursively as follows: a1 = 3
an= 𝑎𝑛−1 forn>1 1+𝑎𝑛−1
A1 Terms of a Sequence (5 marks)
Calculate a2, a3, a4, a5, a6
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 n1 (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.
CPS420 W2019 FINAL EXAM
2

A3 Induction (10 marks)
Given the sequence bn defined recursively as follows: b0 = 2
bn = bn-1+2×3n for n  1
You will prove by induction that for every n  0, bn = 2 ∑𝑛 3𝑖
Before you start you will need to translate this theorem into symbolic form: nD, P(n)
a) Set D (1 mark)
What is the set D in the symbolic form nD, P(n) of the theorem you will prove?
b) P(n) (1 marks)
What is the predicate function P(n) in the symbolic form nD, P(n) of the theorem you will prove?
You will now prove the theorem by mathematical (weak) induction. No other method is acceptable. Be sure to lay out your proof clearly and correctly and to justify every step.
c) Basic Step of the Proof (2 marks) Write the basic step of your proof below:
d) Inductive Step of the Proof (6 marks) Write the inductive step of your proof below:
𝑖=0
CPS420 W2019 FINAL EXAM
3

PART B – GRAPH THEORY – 10 MARKS
B1 Equivalent Graphs (3 marks)
Label the vertices from A to H of the graph on the right to show that it is equivalent to the graph on the left.
ABC
H DEF
G
B2 Circuits (7 marks)
This question is based on the following graph G (the edge numbers are edge names):
A1B2C3D 6
E5FG9
H 15 I J 16 K
a) Starting at vertex A, give an Euler circuit for G (listing the edges as they are
traversed) or explain why this cannot be done
b) Starting at vertex A, give a Hamiltonian circuit for G (listing the edges as they are traversed) or explain why this cannot be done.
CPS420 W2019 FINAL EXAM
4

PART C – REGULAR EXPRESSIONS AND FINITE STATE AUTOMATA – 20 MARKS
C1
C2
C3
Write a regular expression denoting L. Note that you may find it helpful to work on questions C2 and C3 at the same time, as they will inform each other.
Finite State Automata (10 marks)
Draw a state diagram (= deterministic finite state automaton) with as few states as possible which recognizes L. This state diagram does not need to handle non leap years.
Given the alphabet ∑={0,1,2,3,4,5,6,7,8,9}, the following language L over ∑* is defined as: L = {leap years between the dates 1900 and 2999 inclusive}.
The rules for leap years are as follows:
 
Leap years must be divisible by 4
Centuries (i.e. years that end in 00) are not leap years unless they are divisible by 400
Examples (3 marks)
List the first 20 elements of L in chronological order in the table underneath
Regular Expression (7 marks)
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
CPS420 W2019 FINAL EXAM
5

PART D – COUNTING AND PROBABILITIES – 30 MARKS
In this entire section, you should simplify your calculations as much as possible. Final answers can be fractions but they should also be simplified as much as possible.
D1 Cards (5marks)
What is the minimum number of cards that you must pick out of a shuffled standard 52-card deck to guarantee that you will get at least one face card (King, Queen, or Jack)? Explain your answer. A standard 52 card deck contains 4 suits of 13 cards.
D2 Chocolate Truffles (5 marks)
You are buying a box of 16 truffles as a birthday gift for a friend of yours. You will select which truffles to put in the box. The chocolate store has 20 different varieties of truffles who are all the same size and all cost the same. They have a large supply of all 20 varieties, so your choice will not be restricted by the store’s inventory.
How many different combinations of truffles can you put in the box of 16? Explain your answer.
CPS420 W2019 FINAL EXAM
6

D3 Consciousness (10 marks)
We will look at anagrams of CONSCIOUSNESS. An anagram of a word is a new word that is formed by rearranging the letters of the original word. All the letters have to be used. For example MITE is an anagram of TIME. Anagrams do not have to be real words.
a) How many different anagrams of the word CONSCIOUSNESS are there? (including CONSCIOUSNESS). Explain your answer.
b) How many of these end with O or S? Explain your answer
c) What is the probability that a random anagram of CONSCIOUSNESS (including CONSCIOUSNESS itself) will end with O or S? Explain your answer.
CPS420 W2019 FINAL EXAM
7

D4 Spam Filters (10 marks)
A conservative estimate is that 10% of all email you receive is spam. You are using a spam filter which has a false positive rate of 0.5% and a false negative rate of 1%, You want to calculate how reliable your filter is, in particular how carefully you should review the emails that end up in your spam folder.
a)
Based on the explanation above, fill out the non-shaded empty entries of the table below.
Probability
that … (English description)
is (% value)
P(S)
an email is spam
P(Sc)
an email is not spam
P(F+)
an email has been flagged as spam
P(F-)
an email has not been flagged as spam
P(F+|S)
P(F+|Sc)
P(F-|S)
P(F-|Sc)
CPS420
W2019 FINAL EXAM
b)
What is the probability that an email which has been flagged as spam is actually spam?
8

THIS PAGE IS INTENTIONALLY LEFT BLANK AND CAN BE USED FOR ROUGH WORK OR TO CONTINUE ANSWERING AN EARLIER QUESTION.
WORK ON THIS PAGE WILL ONLY BE GRADED IF SPECIFICALLY REQUESTED ON ONE OF PAGES 2 TO 8.
CPS420 W2019 FINAL EXAM
9

Related Posts