UNIVERSITY OF TORONTO Faculty of Arts and Science
AUGUST 2020 EXAMINATIONS
CSC 263 H1F
Duration: 3 hours
Copyright By PowCoder代写 加微信 powcoder
Aids Allowed: Course notes, textbook, and assignments.
• This final examination consists of 3 questions on 4 pages.
• You may submit your solutions in a plain text file, pdf file, or as a photograph of handwritten solutions. In any case, your solutions should
be neatly organized and legible.
• As a student, you help create a fair and inclusive writing environment.
If you possess an unauthorized aid during an exam, you may be charged
with an academic offence.
• State any assumptions you make.
Marking Guide
No 1: /10 No 2: /10 No 3: /20
TOTAL: /40
page 1 of 4 Good Luck!
CSC 263 H1F Final Assessment August 2020
Question 1. Abstract data types. [10 marks]
What ADTs from class, if any, did you employ when implementing the ADT in your project? How could you have done so without them, and why did you pick those ADTs?
If you did not employ any ADTs from class when implementing the ADT in your project, how could you have improved your implementation with ADTs from class, and why would it have helped?
page 2 of 4 cont’d. . .
August 2020 Final Assessment CSC 263 H1F
Question 2. Implementation. [10 marks]
Of the three questions below, pick the most appropriate for your project and answer it:
• What data structures from class did you employ when implementing your project, and how did you augment them to add functionality or improve the running time of your ADT’s methods?
• What data structures from class did you employ when implementing your project, and how could you have augmented them to add functionality or improve the running time of your ADT’s methods? • What data structures from class could you have employed when implementing your project, and how would you augment them to add functionality or improve the running time of your ADT’s methods?
page 3 of 4 over…
CSC 263 H1F Final Assessment August 2020
Question 3. Analysis. [20 marks]
Part(a) [10marks]
In class, we analyzed the worst-case running times for the dictionary operations on BST trees. Now we will consider one possible notion of average case. Assume we have an empty tree T and we do the following operations
INSERT(T,1),INSERT(T,2),···,INSERT(T,n)
in some order. Assume all orders are equally likely. Since all operations on BST trees depend on the height
of the tree, we are interested in Havg(n) – the expected height of T after the n inserts.
(a) Define the probability space that we are dealing with.
(b) Let Ai be the event that we insert i first. Write an expression for t(Ai), the expected height of the
final tree given that we insert i first, in terms of Havg.
(c) Write a recurrence relation for Havg (n).
(d) Solve the recurrence relation from part (c). Hint: it should be Θ(logn).
Part(b) [10marks]
Consider the function you analyzed using amortization. Of the three questions below, pick the most appropriate for your project and answer it:
• The best-case running time is asymptotically bounded above by the amortized cost. Identify a way in which, by restricting the ADT’s functionality, the amortized cost would be bounded above by the best-case running time.
• The amortized cost is asymptotically bounded above by the worst-case running time. Express an appropriate credit invariant for your data structure, and explain how it is maintained when performing a worst-case operation.
• The best-case running time and the worst-case running time are all asymptotically equivalent. Explain what improvement in the cost of an operation you might incure by considering the amortized cost.
page 4 of 4 Total Marks = 40 end of assessment
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com