Homework 3

The goal of this assignment is to develop further experience with the heap data structures in Chapter 3 of the Okasaki textbook. Download the skeleton files LHeaps.elm, BHeaps.elm, and ExplicitMin.elm, and use them as a starting point for the following problems. Look for all occurrences of TODO in comments, which point out where you should implement your solutions. Once you are done, follow the submission instructions below.

Problem 1: Leftist Heaps

3.1.1 --- Okasaki, Exercise 3.3 (30 points)

Define

fromList : List Int -> Heap

such that fromList xs turns an unordered list xs into a Heap by making O(log n) passes over the list xs, pairwise merging adjacent elements. In comments, explain why your solution runs in O(n) time, where n is the length of xs.

Hint: one strategy is to factor the solution into two helper functions

mergePairs : List Heap -> List Heap
makePass   : List Heap -> List Heap

where mergePairs calls merge on adjacent pairs of elements, and makePass makes another pass over the list to merge pairs if necessary and otherwise returns the final result.

To analyze the worst-case running time for such an implementation, define two recurrence relations such that

  • S(n,m) is the time that mergePairs hs takes, where n is the length of hs and m is the size of the largest heap in hs, and
  • T(n,m) is the time that makePass hs takes, where n is the length of hs and m is the size of the largest heap in hs.

Problem 2: Binomial Heaps

3.2.1 --- Okasaki, Exercise 3.6 (30 points)

This problem proposes an alternative representation of binomial heaps that eliminates redundant rank information. Reimplement binomial heaps with this new representation in BHeaps.elm, so that the operations have the same running times as in the original implementation.

3.2.2 --- Okasaki, Exercise 3.7 (30 points)

The implementation of binomial heaps we have seen provides O(log n) access to the minimum element rather than O(1) time as for leftist heaps. In this problem, you will implement a "wrapper" module ExplicitMin that imports an implementation of the heap abstraction and exports an implementation of the heap abstraction that provides O(1) time access to the minimum element.

The problem in the textbook uses ML functors to abstract this pattern in order to work with any implementation of heaps (not just binomial heaps). Because Elm does not support ML-style modules or Haskell-style type clases, we will hard-code our solution to work with binomial heaps.

Implement the heap abstraction in ExplicitMin.elm so that findMin runs in O(1) time and the remaining operations have the same O(log n) running times as those in BinomialHeaps.elm from class.

While you are developing and testing your code, you will need to place BinomialHeaps.elm in the same directory as your solution (but you will not submit it).


Grading and Submission Instructions

Submit the three files LHeaps.elm, BHeaps.elm, and ExplicitMin.elm updated with your changes. You are free to modify these files as you wish, as long as you do not change any type signatures that are provided.

Your solution will be graded using a combination of automated grading scripts and manual review. It is a good idea for you to design some test cases of your own to exercise more sample behaviors than just the ones provided in the writeup. We also reserve the right to take into account the organization and style of your code when assigning grades.

If you are not able to finish all parts of the assignment, make sure that all of your submitted files compile successfully. If not, you risk getting zero points for the assignment. In particular, for each file Foo.elm, make sure that it can be loaded into the Elm REPL

% elm-repl
> import Foo
>

and that it can be compiled to a standalone HTML file:

% elm-make Foo.elm --output=Foo.html
Successfully generated Foo.html

Submitting Your Code

Start by navigating to the folder where you checked out your repo. Next, create a subfolder for this assignment and populate it with the skeleton code:

% svn mkdir hw3
% cd hw3
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw3/LHeaps.elm
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw3/BHeaps.elm
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw3/ExplicitMin.elm

If wget or a similar tool (such as curl) is not available on your machine, download and save the skeleton files provided above in some other way. Then add only these files to your repo:

% svn add LHeaps.elm
% svn add BHeaps.elm
% svn add ExplicitMin.elm

Make sure you choose the same exact names for directories and files that you create. Once you are ready to submit:

% svn commit -m "hw3 submission"

You can resubmit as many times as you wish, and we will grade the most recent versions submitted. Late days, if any, will be computed based on your submission times.

As a sanity check, you can visit the Web-based frontend for your repository to make sure that you have submitted your files as intended:

https://phoenixforge.cs.uchicago.edu/projects/USER-cs223-win-16/repository