--- date: '2024-02-04' description: assignment on stacks, queues, amortized complexity, cache locality effects, nested-loop joins, and binary search optimization. id: A2 modified: 2026-06-05 15:08:41 GMT-04:00 tags: - sfwr2c03 title: Collections and data structure types. created: '2024-02-04' published: '2024-02-04' pageLayout: default slug: thoughts/university/twenty-three-twenty-four/sfwr-2c03/a2/A2 permalink: https://aarnphm.xyz/thoughts/university/twenty-three-twenty-four/sfwr-2c03/a2/A2.md generator: quartz: v4.6.0 hostedProvider: Cloudflare baseUrl: aarnphm.xyz full: https://aarnphm.xyz/llms-full.txt --- ## Problem 1 > \[!question\] P1.1 > > Consider an initially-empty stack $S$ and the following sequence of operations: > > ```plaintext > PUSH(S, 3), POP(S), PUSH(S, 17), PUSH(S, 5), PUSH(S, 15), POP(S), POP(S), POP(S) > ``` > > 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 = \emptyset$ The sequence of operations is as follows: 1. `PUSH(S, 3)`: $S = \lbrace 3 \rbrace$ 2. `POP(S)`: $S = \emptyset$, returned value is $3$ 3. `PUSH(S, 17)`: $S = \lbrace 17 \rbrace$ 4. `PUSH(S, 5)`: $S = \lbrace 17, 5 \rbrace$ 5. `PUSH(S, 15)`: $S = \lbrace 17, 5, 15 \rbrace$ 6. `POP(S)`: $S = \lbrace 17, 5 \rbrace$, returned value is $15$ 7. `POP(S)`: $S = \lbrace 17 \rbrace$, returned value is $5$ 8. `POP(S)`: $S = \emptyset$, returned value is $17$ > \[!question\] P1.2 > > Consider an initially-empty queue $Q$ and the following sequence of operations: > > ```plaintext > ENQUEUE(Q, 3), DEQUEUE(Q), ENQUEUE(Q, 17), ENQUEUE(Q, 5), ENQUEUE(Q, 15), DEQUEUE(Q), DEQUEUE(Q), DEQUEUE(Q) > ``` > > 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 = \emptyset$ The sequence of operations is as follows: 1. `ENQUEUE(Q, 3)`: $Q = \lbrace 3 \rbrace$ 2. `DEQUEUE(Q)`: $Q = \emptyset$, returned value is $3$ 3. `ENQUEUE(Q, 17)`: $Q = \lbrace 17 \rbrace$ 4. `ENQUEUE(Q, 5)`: $Q = \lbrace 17, 5 \rbrace$ 5. `ENQUEUE(Q, 15)`: $Q = \lbrace 17, 5, 15 \rbrace$ 6. `DEQUEUE(Q)`: $Q = \lbrace 5, 15 \rbrace$, returned value is $17$ 7. `DEQUEUE(Q)`: $Q = \lbrace 15 \rbrace$, returned value is $5$ 8. `DEQUEUE(Q)`: $Q = \emptyset$, returned value is $15$ > \[!question\] P1.3 > > Assume we have a stack implementation `MyDynArrayStack` using dynamic arrays: the implementation supports `N` push operations with an amortized runtime complexity of $\Theta(1)$ per operation, and the implementation supports `POP`, `EMPTY`, and `SIZE` operations with runtime time complexity of $\Theta(1)$ > > Provide a _queue_ implementation that uses `MyDynArrayStack` and supports any valid sequence of `N` `ENQUEUE` and `DEQUEUE` operations with an amortized runtime complexity of $\Theta(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`:

"\\begin{algorithm}\n\\caption{Queue}\n\\begin{algorithmic}\n\\STATE $sIn := \\text{MyDynArrayStack()}$\n\\STATE $sOut := \\text{MyDynArrayStack()}$\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 11 Queue

1: $sIn := \text{MyDynArrayStack()}$

2: $sOut := \text{MyDynArrayStack()}$

"\\begin{algorithm}\n\\caption{ENQUEUE(x)}\n\\begin{algorithmic}\n\\STATE $sIn.\\text{PUSH}(x)$\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 12 ENQUEUE(x)

1: $sIn.\text{PUSH}(x)$

"\\begin{algorithm}\n\\caption{DEQUEUE()}\n\\begin{algorithmic}\n\\IF{$sOut.\\text{EMPTY}()$}\n \\WHILE{$\\neg sIn.\\text{EMPTY}()$}\n \\STATE $sOut.\\text{PUSH}(sIn.\\text{POP}())$\n \\ENDWHILE\n\\ENDIF\n\\RETURN $sOut.\\text{POP}()$\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 13 DEQUEUE()

1:if $sOut.\text{EMPTY}()$ then

2:while $\neg sIn.\text{EMPTY}()$ do

3: $sOut.\text{PUSH}(sIn.\text{POP}())$

4:end while

5:end if

6:return $sOut.\text{POP}()$

where `sIn` is used to store elements, and `sOut` is used to store elements in reverse order. Amortized runtime complexity explanation: 1. `ENQUEUE` > - `PUSH` to `sIn` has an amortized runtime complexity of $\Theta(1)$ per operation, as stated in the problem. 2. `DEQUEUE` > - When `sOut` is empty, the transfer of element from `sIn` to `sOut` has a runtime complexity of $\Theta(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 $\Theta(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:

"\\begin{algorithm}\n\\caption{CEJOIN(courses, enrolled)}\n\\begin{algorithmic}\n\\STATE $output := \\emptyset$.\n\\FOR{$(p_c, c_c, n_c) \\in \\text{courses}$}\n \\FOR{$(p_e, c_e, s_e) \\in \\text{enrolled}$}\n \\IF{$p_c = p_e \\textbf{ and } c_c = c_e$}\n \\STATE add $(s_e, n_c)$ to $output$.\n \\ENDIF\n \\ENDFOR\n\\ENDFOR\n\\RETURN $output$\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 14 CEJOIN(courses, enrolled)

1: $output := \emptyset$ .

2:for $(p_c, c_c, n_c) \in \text{courses}$ do

3:for $(p_e, c_e, s_e) \in \text{enrolled}$ do

4:if $p_c = p_e \textbf{ and } c_c = c_e$ then

5:add $(s_e, n_c)$ to $output$ .

6:end if

7:end for

8:end for

9:return $output$

"\\begin{algorithm}\n\\caption{ECJOIN(courses, enrolled)}\n\\begin{algorithmic}\n\\STATE $output := \\emptyset$.\n\\FOR{$(p_e, c_e, s_e) \\in \\text{enrolled}$}\n \\FOR{$(p_c, c_c, n_c) \\in \\text{courses}$}\n \\IF{$p_c = p_e \\textbf{ and } c_c = c_e$}\n \\STATE add $(s_e, n_c)$ to $output$.\n \\ENDIF\n \\ENDFOR\n\\ENDFOR\n\\RETURN $output$\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 15 ECJOIN(courses, enrolled)

1: $output := \emptyset$ .

2:for $(p_e, c_e, s_e) \in \text{enrolled}$ do

3:for $(p_c, c_c, n_c) \in \text{courses}$ do

4:if $p_c = p_e \textbf{ and } c_c = c_e$ then

5:add $(s_e, n_c)$ 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|`). > \[!question\] P2.1 > > Assume we are running algorithm `CEJOIN` and `ECJOIN` on a computer $\mathbb{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 $\mathbb{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}$. > \[!question\] P2.2 > > ![[thoughts/university/twenty-three-twenty-four/sfwr-2c03/a2/real-world-comparison.webp|real-world-system]] > Implementation of `CEJOIN` and `ECJOIN` in [[thoughts/university/twenty-three-twenty-four/sfwr-2c03/a2/impl_22.cpp|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). > \[!question\] 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. > \[!question\] P2.4 > > Write an algorithm that efficiently computes the same result as `CEJOIN` and `ECJOIN` in all-case $\Theta(|enrolled| \log_2{(|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:

"\\begin{algorithm}\n\\caption{EFFJOIN(courses, enrolled)}\n\\begin{algorithmic}\n\\STATE $output := \\emptyset$.\n\\STATE $course := \\text{sort}(course, \\text{by}=(p_c, c_c))$\n\\FOR{$(p_e, c_e, n_e) \\in \\text{enrolled}$}\n \\STATE $i := \\text{binary-search}(courses, (p_e, c_e))$\n \\IF{$i \\neq \\text{null}$}\n \\STATE add $(s_e, n_c)$ to $output$.\n \\ENDIF\n\\ENDFOR\n\\RETURN $output$\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 16 EFFJOIN(courses, enrolled)

1: $output := \emptyset$ .

2: $course := \text{sort}(course, \text{by}=(p_c, c_c))$

3:for $(p_e, c_e, n_e) \in \text{enrolled}$ do

4: $i := \text{binary-search}(courses, (p_e, c_e))$

5:if $i \neq \text{null}$ then

6:add $(s_e, n_c)$ to $output$ .

7:end if

8:end for

9:return $output$

With the following binary search algorithm:

"\\begin{algorithm}\n\\caption{binary-search(course, (p, c))}\n\\begin{algorithmic}\n\\STATE $l := 0$\n\\STATE $r := \\text{len}(course) - 1$\n\\WHILE{$l \\leq r$}\n \\STATE $m := l + (r-l)/2$\n \\IF{$course[m].p_c = p \\textbf{ and } course[m].c_c = c$}\n \\RETURN $course[m]$\n \\ELSIF{$course[m].p_c < p \\textbf{ or } (course[m].p_c = p \\textbf{ and } course[m].c_c < c)$}\n \\STATE $l := m + 1$\n \\ELSE\n \\STATE $r := m - 1$\n \\ENDIF\n\\ENDWHILE\n\\RETURN $\\text{null}$\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 17 binary-search(course, (p, c))

1: $l := 0$

2: $r := \text{len}(course) - 1$

3:while $l \leq r$ do

4: $m := l + (r-l)/2$

5:if $course[m].p_c = p \textbf{ and } course[m].c_c = c$ then

6:return $course[m]$

7:else if $course[m].p_c < p \textbf{ or } (course[m].p_c = p \textbf{ and } course[m].c_c < c)$ then

8: $l := m + 1$

9:else

10: $r := m - 1$

11:end if

12:end while

13:return $\text{null}$

In all cases this would yield a runtime complexity of $\Theta(|enrolled| \log_2{(|courses|)})$ **Correctness** 1. Sorting `course`, has time complexity of $\Theta(|courses| \log_2{|courses|})$, which will be executed once. 2. The binary search has time complexity of $\Theta(\log_2{|courses|})$, which will be executed for each iteration of `enrolled`. 3. The for loop iterate each element in `enrolled` once, which has time complexity of $\Theta(|enrolled|)$. Thus, the total time complexity is $\Theta(|enrolled| \log_2{(|courses|)})$.