Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSC263H1

Problem Set #2

Winter 2023

General Instructions

• Worth: 2%. Please read the completion requirements carefully (see the last point below).

• Due: By 21:00 on Friday 3 February 2023, on MarkUs. Submissions will be accepted up to one week late with a penalty of −10% for each weekday late (penalties begin at 21:00 on Sunday following the due date). Submissions later than one week will receive no credit.

• Problem sets are to be submitted individually. You are free to discuss the problems and their solutions with others, but you must write and submit your own individual answers. See the section on the Syllabus about Academic Integrity for details of exactly what is allowed and what is not.

• Submissions may be typeset or handwritten legibly, but must be made in a single document in an accepted format — documents that cannot be displayed directly on MarkUs will not be marked, even if MarkUs allows you to submit them. We recommend (but do NOT require) the use of LATEX to produce high-quality documents.

• Each problem set will be marked for correctness, to provide you with valuable feedback about the level of understanding you have demonstrated. Because the purpose of the problems is primarily to help you self-assess your understanding of the relevant course material, your submission must meet specific conditions to receive credit. Please read the Syllabus (https://q .utoronto .ca/courses/293389#problem- sets) for full details

of how to benefit the most from this problem set, and how to submit your work.

Problems

Review

“Review” problems can be solved using only knowledge from prerequisite courses. This does not necessarily mean that they are easy, but they require no new knowledge.

1. For the set of keys {1, 4, 5, 10, 16, 17, 21}, draw binary search trees of heights 2, 3, 4, 5, and 6.

Practice

“Practice”problems are straightforward applications of the course material. No creativity or insight should be required to solve them.

2. Insert the keys 12, 8, 9, 20, 10, 15, 3, 11, 5 in this order into an initially empty AVL tree. Show your progress (at least one tree after each insertion) and final tree result. Indicate the height of each subtree next to every node in your final tree (you may find it useful to do this for every tree, not just the final one).

3. Find a key you could insert into the last tree for the previous problem, so that the result requires rebalancing. Explain which node(s) need rebalancing, and show the result of the rebalancing.

4. Delete the key 5 from the following AVL tree. What type of imbalance does it cause? Balance the tree and show your results. Describe your process.

Challenge

“Challenge”problems require some insight or creativity to apply the course material in a different way. Challenge- level problems are not necessarily difficult: for example, the first problem below is really more practice-level.

5. We want to come up with a data structure that stores a collection of elements C with the following operations.

• Insert(C, x): add x to C . Duplicate elements are allowed. Runs in worst-case time O(log n).

• Min(C) / Max(C): return a smallest / largest element in C . Runs in worst-case time O(1).

• ExtractMin(C) / ExtractMax(C): remove and return a smallest / largest element from C . Runs in worst-case time O(log n).

• Note: we want to implement both operations in each pair Min/Max and ExtractMin/ExtractMax.

Describe how to implement these operations by using TWO regular heaps, where one additional piece of information is stored along with each element. Your heaps can be the same type (two min-heaps or two max-heaps) or different types (one min-heap and one max-heap).  Describe precisely what additional information you store with each value, and how to perform each of the operations. Justify briefly that your implementation satisfies the runtime requirements. In your answer, you may call any of the standard heap operations from lectures or the textbook, and your runtime analysis can be based on known properties of these algorithms.

6. Describe how to implement the ADT from the previous question by using one AVL tree, together with some additional information. Describe precisely what additional information you store, how to perform each of the operations, and how the additional information is maintained up-to-date during operations that modify the collection. Justify briefly that your implementation satisfies the runtime requirements. In your answer, you may call any of the standard AVL operations from lectures or the textbook, and your runtime analysis can be based on known properties of these algorithms.

7. Write an algorithm Union(T1, T2 ) that, given pointers to the roots T1 and T2 of two AVL trees, creates an AVL tree containing the union of all the keys in T1 and T2, and returns a pointer to its root. (We want only the keys, none of the rest ot the information associated with each element.) Each of T1 and T2 may contain duplicate keys, and the union of the trees should contain all duplicates (for each key x, there should be as many copies of x in the union as there are in T1 and T2 together). Your algorithm should run in worst-case time Θ (n), where n is the total number of nodes in the two trees. Briefly justify that your algorithm is correct and runs within the required worst-case time.

Extra

“Extra”problems go beyond the learning objectives of the course, making connections to topics we will not cover, or giving you a glimpse of how the material can be taken further. You do NOT have to attempt “extra”problems for full credit. They are provided for your interest only.

8. A binary tree is k-balanced if, for every node u, the absolute value of the difference between the heights of u’s subtrees is at most k . (Thus, an AVL tree is a 1-balanced binary search tree.) Prove that the height of every 2-balanced binary tree with n nodes is Θ (log n).

Next, describe what modifications are necessary to the Insert and Delete methods to implement a 2-balanced BST. Does the new balance requirement simplify anything compared to AVL trees?