In this quiz, we review some content from COMP2521/9024, and establish the standards for de- scribing and reasoning about algorithms.

You can discuss these problems with anyone, and you can use any resources to solve the problems, as long as you write in your own words.  You have to submit your first attempt to complete the quiz by Friday of Week 4; you have to submit your final version which incorporates your changes following the feedback from your tutor by Friday of Week 7.

You’ll submit your attempts by making a post on the Ed forum:

.  click ‘New Thread’ in the top left corner

.  select ‘Post’

. title your post ‘Quiz z1234567’, using your zID

.  select the category ‘Tutorials’

.  select the subcategory corresponding to your tutorial code

. enter the text of your responses

.  select ‘Private’

.  click ‘Post’

You can insert images and equations into the text box. We ask that the text of your response be typed into the text box rather than attached in an uploaded file.

Please only  make  one  post  to  answer  all  questions.   Do  not  make  a separate  post  for  each question.

After posting, you can always edit the post or add comments if you’d like to amend it before receiving feedback.

Once you make a first attempt, your tutor will make a comment below it, using a ‘traffic light’ system.

.  Green means you’ve completed the task.

. Yellow means minor revisions are required.

.  Red means major revisions are required.

If the task isn’t complete, your tutor will leave additional comments specifying what you have to change. You should then edit your original post or add further comments to address this feedback, and your tutor will re-assess the work. Do not make a new post for a second attempt.

You must eventually receive ‘green’ feedback to complete the task.  This will earn all five course marks, regardless of the number of attempts.  If you do not receive green for all parts, you will not receive marks for the quiz.

We suggest that you make a first attempt before your second tutorial, but this isn’ta hard deadline. If you don’t know how to do a problem, write that in your post and your tutor will give you some help in their first round of feedback.

The quiz must be completed by the end of week 7, but we anticipate that most students will achieve this in the first two or three weeks of term.  However, you should not leave this to the last minute, as you will risk missing out on feedback before the due date.

Aside from this assessment,  you can  (and  should!)   also  post  to  the Ed forum  about tutorial discussion points and problems, as well as practice problems. Those posts should be public rather than private, so that other students can see and interact with them.

Question 1

Suppose you have a binary search tree in which each node stores a distinct integer.  If a node contains the value x, we will say that the node with least value greater than x is its successor.  For example, if a binary search tree includes the values 1, 3, 4, 6 and 7, then the successor of 4 is 6. Here are some possible layouts of this tree:

Explain why if x has a right child, then the successor of x does not have a left child.

Question 2

Suppose you have a max heap in which each node stores a distinct integer. Consider the following algorithm which claims to implement the Pop operation, i.e.  remove the node of largest value from the heap.

Maintain a pointer to the node of largest value, initially at the top of the heap, and recurse downwards. At each stage:

.  if the node has two children, swap it with the child of larger value;

.  if the node has only one child, swap it with that child;

.  if the node has no children, delete it.

2.1   Demonstrate the execution of the  algorithm on  a nontrivial example in which it correctly removes the node of largest value from the heap.

2.2   Explain why this algorithm does not correctly implement the Pop operation.

2.3   Describe how to correctly implement the Pop operation.

Question 3

A conveyor belt contains n packages that need to be delivered to AlgoTown within K days.  Package i has an associated integer weight wi , where no package has weight exceeding a maximum M.  Each day, the packages are loaded onto a truck in the order of their position on the belt.  We may not load more than the capacity of the truck, which is also an integer.

3.1   To get a better understanding of the description above, consider the following example. There are n = 10 items with the following weights: w = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and K = 5.

.  Determine if it is possible to load all packages within 5 days if the truck’s capacity is 12. .  Determine if it is possible to load all packages within 5 days if the truck’s capacity is 17.

3.2   Given the capacity C of the truck, the weights of the packages and the number of days K, design an O(n) algorithm that checks whether it is possible to deliver all packages within K days.

3.3   Suppose now that you get to choose the capacity of the truck.  To save money, you would like to choose the smallest possible truck that allows you to deliver all packages within K days. Design an O(nlog(nM)) algorithm that solves this problem.