CSC263H1, Fall 2019 Problem Set 1 Sample Solutions
CSC263H1: Problem Set 1 Sample Solutions
Due Tuesday September 17 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. [20 marks] Complexity Consider these procedures:
1 2 3 4 5
6
7
8
9
10
11
12
13
14
Sum(input array A) returns Integer total = 0
for i = 1 to A.size total ← total + A[i]
return total
CheckArray(input array A) returns Boolean if A.size < 3 then
return true if A[1] = 0 then
return false
for i = 1 to A.size − 2
if Sum(A[i:i+2])̸=0then
return false return true
Assume that each assignment, comparison and arithmetic operation takes one unit of computational cost. (a) [3 marks] Let tSum(A) be the cost of executing Sum on an input A. Express tSum(A) in terms of
the size of A. Justify your analysis of the computational cost.
(b) [12 marks] Let T(n) be the worst-case cost of executing CheckArray on an array A of size n.
Express T (n) in terms of n. Fully justify your analysis of the computational cost.
(c) [5 marks] Give a function f (n) such that T (n) ∈ Θ(f (n)). Justify your answer by explaining why
T(n) ∈ O(f(n)) and T(n) ∈ Ω(f(n)). A sound and clear justification is required to receive credit.
the code above, the left arrow denotes the assignment operation, i.e. x ← x + 1 increments x; return
In
exits a function immediately. The array A is an input to the function and its scope is local to the function. The indices of array A start at 1. The colon denotes the subarray operation, i.e., A[j : k] is a constant-time operation on A that returns the subarray consisting of the elements A[j], A[j + 1], . . . A[k], when j ≤ k, and the empty array when j > k.
Solution
First, let us determine the cost tSum(A) of Sum on an input A. The procedure always executes A.size iterations of the loop (line 3), and each iteration performs one arithmetic operation (line 4). Therefore, tSum(A) = A.size.
Next, let us determine the cost t(A) of CheckArray on an input A. Let the input size be n = A.size. We now divide the input into cases:
(a) When n < 3, CheckArray executes one comparison and exits (lines 7, 8).
Page 1/7
CSC263H1, Fall 2019 Problem Set 1 Sample Solutions
(b) When A[0] = 0, CheckArray executes two comparisons and exits (lines 7–10).
(c) Otherwise, 3 ≤ n and A[0] ̸= 0. In this case, the loop (line 11) iterates up to n − 2 times,
provided it does not terminate early (line 13). Let us examine this case in more detail.
If any running sum of three consecutive elements is zero, the loop terminates early (lines 12–13), and in this case, the number of iterations of the loop is not dependent on n. The worst case cost occurs when the loop completes all n − 2 iterations. To show that this is possible, we provide on example of a worst-case input.
Consider A = (1,−2,1,1,−2,1,1,−2,1,1,−2,...) for any array size n. In this pattern, any three consecutive elements will include exactly two 1’s and a single -2, i.e., the sum of three consecutive elements is always 0. From line 12, we see that the loop will not terminate early for this representative worst-case input.
To calculate the cost of this worst-case input, first consider line 12. Sum is invoked with an input array of size 3. Therefore each invocation of Sum in line 12 has complexity 3. There is also a comparison to zero, so the total complexity of line 12 is 4.
If the loop runs to completion, then the cost will be T(n) = 2+4(n−2), where the first term accounts for the comparisons before the loop, the first factor accounts for the cost of line 12, and the second factor accounts for the number of times line 12 is executed. Therefore, T (n) = 4n − 6.
WenowshowthatT(n)∈O(n). LetB=1andc=5. Weshouldthatforalln>B,T(n)= 4n − 6 ≤ 5n. Subtracting 4n from both sides gives −6 ≤ n, which is true for n > B = 1. Therefore, T (n) ∈ O(n).
WenowshowthatT(n)∈Ω(n). LetB=6andc=3. Weshouldthatforalln>B,T(n)= 4n−6 ≥ 3n. Subtracting 3n−6 from both sides gives n ≥ 6, which is true for n > B = 6. Therefore, T (n) ∈ Ω(n).
Since T (n) ∈ Ø(n) and T (n) ∈ Ω(n), therefore T (n) ∈ Θ(n).
Page 2/7
CSC263H1, Fall 2019 Problem Set 1 Sample Solutions
2. [20 marks] List ADT. Consider the following abstract data type that we will call a “List.”
Objects: A 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 may 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) [6 marks] Give two different implementations of the list ADT; one using a linked data structure, and one using fixed length arrays.
Clarification (September 12): Here you should describe the ways in which you will represent data. You will describe how operations work in part (b).
(b) [10 marks] Describe in detail (pseudocode) how each operation above works for each of your implementations 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
Page 3/7
CSC263H1, Fall 2019 Problem Set 1 Sample Solutions
for in range(0, i−1): prev = prev.next
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
range ”)
range ”)
Page 4/7
CSC263H1, Fall 2019 Problem Set 1 Sample Solutions
cur = self.head
for idx in range(i):
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)
str ( self ):
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
def
Page 5/7
CSC263H1, Fall 2019 Problem Set 1 Sample Solutions
ray [ i ]
. array si
(c) [4 marks] Describe one situation (pseudocode) for each of your implementations where it would Page 6/7
if self.size()==self.arraysize: self . double array ()
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
str ( self ):
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.
def
CSC263H1, Fall 2019 Problem Set 1 Sample Solutions
be preferable to the other, and justify your choice based on the running times of the different implementations.
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 7/7