CSC263H1 Y, Summer 2020
Problem Set 1
General instructions
CSC263H1 Y: Problem Set 1
Due Friday May 22 before 10pm
Please read the following instructions carefully before starting the problem set. They contain important information about general problem set expectations, problem set submission instructions, and reminders of course policies.
• Your problem sets are graded on both correctness and clarity of communication. Solutions that are technically correct but poorly written will not receive full marks. Please read over your solutions carefully before submitting them.
• Each problem set may be completed in groups of up to three. If you are working in a group for this problem set, please consult the articles on collaboration and plagiarism on posted on quercus.
• Solutions must be typeset electronically, and submitted as a PDF with the correct filename. Hand- written submissions will receive a grade of ZERO.
The required filename for this problem set is problem set1.pdf.
• Problem sets must be submitted online through MarkUs. If you haven’t used MarkUs before, give yourself plenty of time to figure it out, and ask for help if you need it! If you are working with a partner, you must form a group on MarkUs, and make one submission per group. “I didn’t know how to use MarkUs” is not a valid excuse for submitting late work.
• Your submitted file(s) should not be larger than 9MB. You might exceed this limit if you use a word processor like Microsoft Word to create a PDF; if it does, you should look into PDF compression tools to make your PDF smaller, although please make sure that your PDF is still legible before submitting!
• Submissions must be made before the due date on MarkUs.
• The work you submit must be that of your group; you may not use or copy from the work of other
groups, or external sources like websites or textbooks.
Additional instructions
• We will choose a random subset of the questions, including parts of questions, to mark.
Page 1/4
CSC263H1 Y, Summer 2020
Problem Set 1
1. [10 marks] Complexity
(a) Let i,n ∈ N and ∀i, ai ∈ R+. Prove or disprove:
n
aixi ∈Θxn
i=0
(b) Let a,b,c,d ∈ R+ and b,d > 1. Prove or disprove:
logb xa ∈ Θ logd xc
(c) Let f1, f2, g1, g2 : N → R+. Prove or disprove:
g1 ∈Θ(f1)∩g2 ∈Θ(f2)⇒g1 ·g2 ∈Θ(f1 ·f2)
Note: Typo fixed on May 14th.
Page 2/4
CSC263H1 Y, Summer 2020 Problem Set 1
2. [20 marks] List ADT. Consider the following abstract data type that we will call a “List.”
Objects: An ordered multiset L of integers. Note that a multiset allows for the repitition of elements, so [1] and [1, 1] are distinct lists. In this case, “ordered” means that distinct lists have distinct orders. I.e. [−1, 0, 1] and [1, 0, −1] are distinct lists; it does not mean that the contents must be in any particular order (e.g. non-decreasing).
Operations:
– Insert(L, x, i): Insert the integer x into L at position i.
– Pop(L, i): Remove and return the integer at position i in L.
– Remove(L, x): Delete the first occurence of the integer x from L.
– Size(L): Return the number of integers in L.
– Sort(L): Modify L so that the integers are in non-decreasing order.
(a) Give two different implementations of the list ADT; one using a linked data structure, and one using fixed length arrays. Here you should describe the ways in which you will represent data. You will describe how operations work in part (b).
(b) Describe in detail (pseudocode) how each operation above works for each of your implementations of the list ADT.
(c) Describe one situation (pseudocode) for each of your implementations where it would be preferable to the other, and justify your choice based on the running times of the different implementations.
Page 3/4
CSC263H1 Y, Summer 2020 Problem Set 1
3. [20 marks] Expected cost. Consider a min-priority queue Q implemented using a binary min-heap. Let k ∈ N be a given natural number. Suppose that Q contains n = 2k − 1 elements (or “nodes”), with indices 1 . . . n. Let aj be the value stored in the element with index 2j−1.
Let x ∈ Z be a given integer. Let m be a random variable corresponding to the number of swaps performed by Q.insert(x).
Letpbeagivenrealnumber,0