CSCI2100D 2020-21: Assignment 2∗

This assignment is due at 17:00 (5pm), 23rd April 2021.

■ Q1. [18 marks] Answer the following questions related to queue.
– (i) [4 marks] Given the following queue (size is 6), what will it look like after
dequeue(),
– (ii) [4 marks] Given a queue with size 5, what will be the output of the following
operations. Assume that initially the queue is empty.
enqueue(2), enqueue(4), enqueue(6), dequeue(), enqueue(5), dequeue(), enqueue(7),
dequeue(), enqueue(9), dequeue()
– (iii) [10 marks] Suppose you have three queues q1, q2, q3 (size = 4) with starting
configuration shown on the left, and finishing condition shown on the right. Give a
sequence of dequeue and enqueue operations that take you from start to finish. For
example, to dequeue an element of q1 and enqueue it into q2, you may write down
“dequeue q1 and enqueue to q2” as your answer.
start
front front front
∗Departmental Guideline for Plagiarism (Department of Systems Engineering and Engineering Management): If
a student is found plagiarizing, his/her case will be reported to the Department Examination Panel. If the case is
proven after deliberation, the student will automatically fail the course in which he/she committed plagiarism.
The definition of plagiarism includes copying of the whole or parts of written assignments, programming
exercises, reports, quiz papers, mid-term examinations and final examinations. The penalty will apply to both
the one who copies the work and the one whose work is being copied, unless the latter can prove his/her
work has been copied unwittingly. Furthermore, inclusion of others’works or results without citation in
assignments and reports is also regarded as plagiarism with similar penalty to the offender. A student caught
plagiarizing during tests or examinations will be reported to the Faculty office and appropriate disciplinary
authorities for further action, in addition to failing the course.
2
■ Q2. [8 marks]
– (i) [4 marks] Consider the queue introduced on the slide 4-5 of Chapter 4. Queues.
What is the time complexity of int dequeue(queue *q).
– (ii) [4 marks] Consider the circular queue introduced on the slide 16-18 of Chapter

4. Queues, what are the advantage of circular queue, compared with the queue in (i).
   ■ Q3. [34 marks] Answer the following questions related to sorting.
   – (i) [8 marks] Consider an array 𝐴1 [1..6] = (15, 10, 5, 2, 20, 25). Following the pseudocode
   in slide 42 of Chapter 6. Sorting, sort 𝐴1 in ascending order using heap
   sort. You need to show the contents of 𝐴1 after each step as in slide 43.
   – (ii) [8 marks] Given an array 𝐴2 [0..7] = (2, 1, 4, 9, 6, 5, 8, 3), illustrate how to sort
   this array by merge sort in ascending order as in slide 33 of Chapter 6. Sorting.
   – (iii) [10 marks] Given an array 𝐴3 [0..8] = (7, 10, 9, 1, 11, 6, 4, 8, 2), illustrate how
   to sort this array by quick sort as in slide 16 of Chapter 6. Sorting with the
   following strategies:
   ∗ (a) [5 marks] Pick the median-of-three as the pivot. Use partition method
   at slide 19 chapter 6. (When the (sub)array contains even number of elements,
   there are two “middle” elements. Please pick the first middle
   element (the one with smaller array index) as the middle element), e.g.,
   among [1 3 2 4], middle elements are 3 and 2 and we pick 3 as the middle
   element.
   ∗ (b) [5 marks] Pick the first element as the pivot. Use In-Place partition method
   at slide 20 chapter 6.
   – (iv) [8 marks] Given an array 𝐴4 [0..𝑛 − 1] which contains 𝑛 integers, design an
   algorithm, denoted by kthLargest(𝐴4, 𝑘), in pseudocode to find the 𝑘-th largest
   integer 𝑠𝑘 in 𝐴4, where 1 ≤ 𝑘 ≤ 𝑛. For example, consider 𝑛 = 5 and 𝐴4 [0..4] =
   (3, 3, 0, 1, 4). Then 𝑙1 =kthLargest(𝐴4, 2) = 3 and 𝑙2 =kthLargest(𝐴4, 3) = 3. Note
   we do not accept trivial solutions such as returning 𝐴4 [𝑛 − 𝑘] after sorting 𝐴4.
   (Hint: In quicksort, an element is randomly selected as the pivot value 𝑣 and the array
   is reorganized (Fig. 1). Let the # of elements larger than 𝑣 be 𝑛𝑟
   . By comparing 𝑛𝑟 with
   𝑘, we will know whether 𝑙𝑘 = 𝑣, 𝑙𝑘 < 𝑣 or 𝑙𝑘 > 𝑣. Then, we can proceed the search
   in one of the subarrays recursively, until the target is found. For convenience, in
   your algorithm, you can call partition to represent the in-place partition method
   described in slide 20 of Chapter 6. Sorting, and with adequate explanation,
   reasonable helper functions may also be used, e.g. declaring randomInt(𝑚𝑖𝑛,𝑚𝑎𝑥)
   that returns an integer randomly between [𝑚𝑖𝑛,𝑚𝑎𝑥].)
   elements smaller than 𝑣
   𝑛𝑙
   𝑣 elements larger than 𝑣
   𝑛𝑟
   Fig. 1. Partitioning
   CSCI2100D 2020-21: Assignment 2 3
   ■ Q4. [18 marks] Consider the binary search tree 𝑇0 shown in Fig. 2.
   – (i) [4 marks] Insert 5 and 9 sequentially into 𝑇0. Show the resulting trees after each
   insertion.
   – (ii) [4 marks] Delete 8 and 2 sequentially from (the original) 𝑇0, using the approach
   as described in the lecture. Show the resulting trees after each deletion.
   – (iii) [6 marks] Generally, given a binary search tree of height ℎ, what are the time
   complexities (in Big-Oh) of the following operations? Explain briefly.
   ∗ (a) [2 marks] Searching
   ∗ (b) [2 marks] Deletion
   ∗ (c) [2 marks] Insertion
   – (iv) [4 marks] Show the nodes visited in order when searching for 6 and 13 in 𝑇0
   respectively.
   ■ Q5. [22 marks]
   – (i) [6 marks] Consider the binary search tree 𝑇0 shown in Fig. 2, write down the
   Inorder, Preorder and Postorder traversal of the given tree.
   – (ii) [6 marks] From the following traversals of a complete binary tree, reconstruct
   and draw the complete binary tree. Some nodes are hidden as #.
   ∗ Inorder: ##𝑄𝐴𝑊 ###
   ∗ Preorder: #𝑄#𝐷#𝑌##
   ∗ Postorder: #𝑍##𝑃𝑇 ##
   – (iii) [8 marks] Determine if the following statement is true. If true, justify your
   answer by giving a brief proof; if false, give a counter-example.
   ∗ (a) [4 marks] The structure of a binary tree can be determined given only the
   sequences of preorder and postorder traversals of it.
   ∗ (b) [4 marks] There must be more non-internal nodes than internal nodes in
   a complete binary tree. (In a binary tree, an internal node is any node that is
   neither the root nor a leaf. A non-internal node, thus, refers to either the root
   4
   or a leaf. For instance, 2, 4, 10 and 12 are the internal nodes, and 8, 1, 3, 11 and
5. are the non-internal nodes of 𝑇0.)