CSC263H1 Y, Summer 2020 Problem Set 1 Sample Solutions
CSC263H1 Y: Problem Set 1 Sample Solutions
Due Friday May 22 before 10pm
Note: solutions may be incomplete, and meant to be used as guidelines only. We encourage you to ask follow-up questions on the course forum or during office hours.
1. [10 marks] Complexity
(a) Let i,n ∈ N and ∀i, ai ∈ R+. Prove or disprove:
n
aixi ∈Θ(xn)
i=0
Solution
n
Letx0 =1,c1 =an andc2 =ai. Notethat
and
n
Therefore aixi ∈ Θ(xn)
i=0
n
c1xn =anxn ≤aixi
i=0
nn
aixi ≤ aixn = c2xn
i=0 i=0
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.
Solution
Let x0 = 1 and c1 = a logd b. The rest of the proof is left as an excercise. c
Solution
Assume g1 ∈ Θ(f1), so we have the appropriate variables x1, c1, and c3. Also assume g2 ∈ Θ(f2) with variables x2, c2, and c4.
Letx0 =x1+x2,c=c1·c3,andc′ =c2·c4. Therestoftheproofisleftasanexcercise.
Page 1/9
CSC263H1 Y, Summer 2020 Problem Set 1 Sample Solutions
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) [10 marks] 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) [0 marks] Describe in detail (pseudocode) how each operation above works for each of your imple- mentations of the list ADT.
Solution
Linked list data: a node structure which includes a stored value and a pointer to another node or null; a pointer to the head of the linked list; and a size counter.
Array list data: a pointer to a fixed length array, a list size counter, and either an array size counter or sentinels (to indicate the end of the array).
Solution
class LList ():
def init ( self ):
self .head = None self.length = 0
def insert(self, x, i): if i > self.size():
print(”Index out of range”) return
s e l f . l e n g t h += 1 if i == 0:
n = node(x, self .head) self.head = n
return
prev = self.head
nxt = self .head.next
for in range(0, i−1):
prev = prev.next
Page 2/9
CSC263H1 Y, Summer 2020 Problem Set 1 Sample Solutions
nxt = nxt.next
n = node(x, nxt) prev.next = n
def pop(self, idx):
if self . size () == 0:
return (” Index out of
range ”)
if idx == 0:
val = self.head.value
self .head = self .head.next return val
prev = self.head
cur = self .head.next for i in range(idx−1):
prev = cur
cur = cur.next
val = cur.value prev.next = cur.next return val
def remove(self , x): i=0
cur = self.head
while cur != None and cur.value != x:
cur = cur.next
i += 1
if i < self.size():
s e l f . pop ( i )
def size(self): return self . length
def getval(self, i): if i >= self.size():
return (” Index out of cur = self.head
for idx in range(i):
cur = cur.next return cur . value
def set val(self, x, i): if i >= self.size():
return (” Index out of cur = self.head
for idx in range(i):
range ”)
range ”)
Page 3/9
CSC263H1 Y, Summer 2020 Problem Set 1 Sample Solutions
cur = cur.next cur.value = x
def sort(self):
if self.size() < 2:
return
for i in range(0, L.size()):
cur min = i
for j in range(i+1, self.size()):
if self.get val(j) < self.get val(cur min): cur min = j
temp = self.get val(cur min)
self.set val(self.get val(i), cur min) self.set val(temp, i)
def
return str(self.array)+str(self.size())+”, ”+str(self.array size)
def str ( self ): cur = self.head
s = ””
while cur != None:
s = s + str(cur.value)+ ”−>”
cur = cur.next return s
class node ():
def init (self, val, nxt=None):
self.value = val self .next = nxt
####################################################
class AList ():
def init ( self ):
self.length = 0
self . array = [None] # Size 1 array self . array size = 1
def insert(self, x, i): if i > self.size():
print(”Index out of range”)
return
for index in range(self.size()−1, i, −1):
self . array [ index+1] = self . array [ index ] self.array[i] = x
s e l f . l e n g t h += 1
if self.size()==self.arraysize:
self . double array ()
str ( self ):
Page 4/9
CSC263H1 Y, Summer 2020 Problem Set 1 Sample Solutions
ray [ i ]
. array si
(c) [10 marks] 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 5/9
def double array( self ):
new array = [None for i in range(2∗self.array size)] for i in range(0,L.size()):
new array[i] = self.array[i]
self . array = new array
self . array size += self . array size
def pop(self, i):
if i >= self.size():
print(”Index out of range”)
return
val = self.array[i] for index in range(i ,
self . array [ index ] = s e l f . l e n g t h −= 1 return val
self . size ()):
self . array [ index+1]
def remove(self , x):
for i in range(0, self.size()):
if self.array[i]==x: s e l f . pop ( i )
break
def size(self): return self . length
def sort(self):
if self.size() < 2:
return
for i in range(0, L.size()):
cur min = i
for j in range(i+1, self.size()):
if self.array[j] < self.array[cur min]: cur min = j
self.array[i], self.array[cur min] = self.array[cur min], self.ar
def
return str(self.array[:self.size()])+str(self.size())+”, ”+str(self
Note that for the linked list we defined two additional procedures: get val and set val to facilitate the implementation of sort. For the array list we have double array in order to increase the size of the fixed length array being used. Although this is a python implementation, we note that the use of built in python lists is restricted to operations that are well defined for fixed length arrays.
The reason we provide python3 code instead of pseudo code here is so that you may run it and test it yourself, however I make no promises that it is bug-free.
str ( self ):
CSC263H1 Y, Summer 2020 Problem Set 1 Sample Solutions
Solution
We prefer linked lists if we continuously add elements to the front of the list:
n = 10000
for i in range(n):
L.insert(i, 0)
We prepend elements to linked lists in constant time, so the above code run in Θ(n) with linked lists. With array lists, each prepend must shift all the elements forward by however many
elements are already in the list, so the total running time is
We prefer array lists for sorting:
L. sort ()
Since, although both sorting implementations are equivalent, get val and set val run in Θ(n), whereas the equivalent indexing operations in array lists runs in Θ(1). Thus selection sort for linked lists runs in Θ(n3) and for array lists runs in Θ(n2)
n n(n + 1) 2
i=0
i = 2 ∈ Θ(n ).
Page 6/9
CSC263H1 Y, Summer 2020 Problem Set 1 Sample Solutions
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