# CS 330 Algorithms

## Homework 4

Remember: "Argue"="Prove", "[Show/Explain] How"="Give pseudo-code" (remember: top-down approach allows grader to stop at any level of detail; pseudo-code for trivial subroutines can be left out), etc.

### Max, Min, Median, Select:

• pr. 9-1
(hint: if you need to you can use randomized algorithms)
you can use the algorithms discussed in the book as subroutines

### Heaps

• 6.1-3
• 6.1-4
• 6.1-5
• 6.2-6
• 6.4-3
• 6.4-4
• Make a min-heap from elements a, b, c, d, e, f, g, h, i (given as a list in that order). Use alphabetic order: a<b.
*make sure to use the efficient algorithm for this!* Show intermediate steps!*

### Leftist Heaps:

• Insert (in the given order and according to the algorithms on the web) the following elements

into leftist min-heap H1:           e, b,  j, k, d

and into leftist min-heap H2:    i, a, c, f

• RemoveMin from H1 above
• Merge the heaps H1 and H2 after first question above (i.e. before RemoveMin of the previous question).
• Make a leftist heap from elements a, b, c, d, e, f, g, h, i (given as a list in that order)
*make sure to use the efficient algorithm for this!*

In all the above, show intermediate steps, marking the rank of each node.

• 8.3-4
• 8.4-2
• 8-4

### Dictionary/Dynamic-set(review: lists, stacks, queues, trees) (most of the problems below are relatively simple and were covered to large extent in your cs111-112)

• 10.1-6
(that is write two simple procedures to implement Enqueue and Dequeue, using the Push and Pop)
• 10.1-7
• 10.2-5
• 10.2-6
• 10.2-7
• 10-1
• 10-2

Extra credit problems:

•  6.1-7
•  6.2-5
•  8.1-2
•  8.1-3
•  8.1-4 (hint - in addition to the hint in the book: use the same technique as in that section to obtain lower the bound)
This problem is highly recommended, though not assigned - it can really tell you whether you have mastered the lower bounds proof for sorting!
•  8.2-4
• 8.3-2
• 8.3-3
• 8-1
• 8-2
• 10.1-2