Illustrate the result of each operation (clearly indicate the content of the stack after the operation and, in case of a POP, the returned value by the operation
Solution
Stack S is initially empty, or S=∅
The sequence of operations is as follows:
PUSH(S, 3): S={3}
POP(S): S=∅, returned value is 3
PUSH(S, 17): S={17}
PUSH(S, 5): S={17,5}
PUSH(S, 15): S={17,5,15}
POP(S): S={17,5}, returned value is 15
POP(S): S={17}, returned value is 5
POP(S): S=∅, returned value is 17
P1.2
Consider an initially-empty queue Q and the following sequence of operations:
Illustrate the result of each operation (clearly indicate the content of the queue after the operation and, in case of a DEQUEUE, the returned value by the operation
Solution
Queue Q is initially empty, or Q=∅
The sequence of operations is as follows:
ENQUEUE(Q, 3): Q={3}
DEQUEUE(Q): Q=∅, returned value is 3
ENQUEUE(Q, 17): Q={17}
ENQUEUE(Q, 5): Q={17,5}
ENQUEUE(Q, 15): Q={17,5,15}
DEQUEUE(Q): Q={5,15}, returned value is 17
DEQUEUE(Q): Q={15}, returned value is 5
DEQUEUE(Q): Q=∅, returned value is 15
P1.3
Assume we have a stack implementation MyDynArrayStack using dynamic arrays: the implementation supports N push operations with an amortized runtime complexity of Θ(1) per operation, and the implementation supports POP, EMPTY, and SIZE operations with runtime time complexity of Θ(1)
Provide a queue implementation that uses MyDynArrayStack and supports any valid sequence of NENQUEUE and DEQUEUE operations with an amortized runtime complexity of Θ(1) per operation. Explain why your implementation has the stated amortized runtime complexity for ENQUEUE and DEQUEUE operations.
Solution
Queue implementation MyDynArrayQueue using two MyDynArrayStack, sIn and sOut:
Algorithm 16 Queue
1:sIn:=MyDynArrayStack()
2:sOut:=MyDynArrayStack()
Algorithm 17 ENQUEUE(x)
1:sIn.PUSH(x)
Algorithm 18 DEQUEUE()
1:if sOut.EMPTY() then
2:while ¬sIn.EMPTY() do
3:sOut.PUSH(sIn.POP())
4:end while
5:end if
6:return sOut.POP()
where sIn is used to store elements, and sOut is used to store elements in reverse order.
Amortized runtime complexity explanation:
ENQUEUE
PUSH to sIn has an amortized runtime complexity of Θ(1) per operation, as stated in the problem.
DEQUEUE
When sOut is empty, the transfer of element from sIn to sOut has a runtime complexity of Θ(N) with worst case.
However, the item was moved once per enqueue-dequeue cycle, so the total time spent is proportional to N, thus making amortized runtime complexity of Θ(1) per operation.
Problem 2
Consider the relations courses(prog, code, name) (that models courses named name and identified by the program prog the course is part of, e.g., SFWRENG, and the course code code, e.g., 2C03) and enrolled(prog, code, sid) (that models students with identifier sid enrolling for a course identified by program prog and course code code).
We want to compute the list of all pairs (sid, name) in which sid is a student identifier s and name is the name of a course the student with identifier s is enrolled in. To compute this list, we developed the following two nested-loop algorithms:
Algorithm 19 CEJOIN(courses, enrolled)
1:output:=∅.
2:for (pc,cc,nc)∈courses do
3:for (pe,ce,se)∈enrolled do
4:if pc=pe and cc=ce then
5:add (se,nc) to output.
6:end if
7:end for
8:end for
9:return output
Algorithm 20 ECJOIN(courses, enrolled)
1:output:=∅.
2:for (pe,ce,se)∈enrolled do
3:for (pc,cc,nc)∈courses do
4:if pc=pe and cc=ce then
5:add (se,nc) to output.
6:end if
7:end for
8:end for
9:return output
Assume we have significantly more students enrolled for courses than courses (|enrolled| > |courses|).
P2.1
Assume we are running algorithm CEJOIN and ECJOIN on a computer C where every instruction takes exactly the same amount of time to execute. Argue why CEJOIN must be faster than ECJOIN when running on computer C?
Solution
Given ∣enrolled∣>∣courses∣, the difference between the two lies in the number of iterations of the inner loop.
The outer loop table will only be scanned once, and the inner loop will be scanned for each iteration of the outer loop in the nested-loop algorithm:
CEJOIN will iterate over enrolled once, and courses over each iteration. Since |enrolled| > |courses|, CEJOIN’s inner loop will result in fewer iteration.
ECJOIN will iterate over courses once, and enrolled over each iteration. Since |enrolled| > |courses|, ECJOIN’s inner loop will means more iterations, comparing to CEJOIN.
Thus, we can conclude that CEJOIN must be faster than ECJOIN when running on computer \mathbb{C.
P2.2
real-world-system
Implementation of CEJOIN and ECJOIN in impl_22.cpp shows that ECJOIN is actually faster than CEJOIN. Explain why this is the case in a real-world system.
Solution
Given the processor is using fast caches, the inner loop of ECJOIN will be faster than CEJOIN due to cache locality.
Since |enrolled| > |courses|, the inner loop of ECJOIN will have better cache locality, as it will be accessing the same memory locations more frequently. Additionally, ECJOIN’s outer loop will only run once, therefore we can expect ECJOIN to be faster comparing to CEJOIN, since CEJOIN will have to access enrolled each iteration, which would be slower comparing to accessing courses (since every item in enrolled might not be cached).
P2.3
The measurements in the above figure have a few sudden jumps, e.g., at 1 500 000, 2 500 000, 4 500 000, 8 500 000, and 17 000 000. Explain what causes these jumps.
Solution
These jumps are probably caused by the cache size and cache associativity.
As the data size increases, the number of elements might not fit into processor’s L1, L2, L3 cache, thus, causing more frequent cache misses. At these points, the dataset is so large such that the processor might have to access on slower main memory, which induces these bump we observed from the graph.
We can also expect context-switching overhead given the code might be running in multiple processes or threads. However, the implementation implies that this code is running in a single thread, so we can rule out context-switching overhead.
P2.4
Write an algorithm that efficiently computes the same result as CEJOIN and ECJOIN in all-case Θ(∣enrolled∣log2(∣courses∣)). In the design of your algorithm, you may require that either enrolled or courses is ordered. Argue why your algorithm is correct and why it has the runtime complexity we specified.
Solution
Assuming courses is sorted and ordered by (prog, code) pair, the following algorithm can be used:
Algorithm 21 EFFJOIN(courses, enrolled)
1:output:=∅.
2:course:=sort(course,by=(pc,cc))
3:for (pe,ce,ne)∈enrolled do
4:i:=binary-search(courses,(pe,ce))
5:if i=null then
6:add (se,nc) to output.
7:end if
8:end for
9:return output
With the following binary search algorithm:
Algorithm 22 binary-search(course, (p, c))
1:l:=0
2:r:=len(course)−1
3:while l≤r do
4:m:=l+(r−l)/2
5:if course[m].pc=p and course[m].cc=c then
6:return course[m]
7:else if course[m].pc<p or (course[m].pc=p and course[m].cc<c) then
8:l:=m+1
9:else
10:r:=m−1
11:end if
12:end while
13:return null
In all cases this would yield a runtime complexity of Θ(∣enrolled∣log2(∣courses∣))
Correctness
Sorting course, has time complexity of Θ(∣courses∣log2∣courses∣), which will be executed once.
The binary search has time complexity of Θ(log2∣courses∣), which will be executed for each iteration of enrolled.
The for loop iterate each element in enrolled once, which has time complexity of Θ(∣enrolled∣).
Thus, the total time complexity is Θ(∣enrolled∣log2(∣courses∣)).
