Study Guides (380,000)
CA (150,000)
Ryerson (10,000)
CPS (40)
All (6)
Final

CPS 420 Final Exam Winter 2018Exam


Department
Computer Science
Course Code
CPS 420
Professor
All
Study Guide
Final

This preview shows pages 1-3. to view the full 14 pages of the document.
RYERSON UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE
CPS 420
FINAL EXAM
WINTER 2018
NAME:
STUDENT ID:
INSTRUCTIONS
This exam is 3 hours long.
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.

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

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

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

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 for n 1
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.
You're Reading a Preview

Unlock to view full version