Homework 4: Working with Linked Queues and Deques

This homework provides plenty of practice working with mutable data structures. All of the necessary instructions are found in the homework files. The assignment uses material up to Chapter 16 of the lecture notes. There is also an FAQ document for this homework available.

Assignment Overview

In this homework assignment you will be working in multiple files, all of which will be automatically zipped into a hw04-submit(DATE).zip file within Codio. You can zip your project by selecting the dropdown where you can Run or Build your project and selecting “Zip (for submission).”

In addition to these files, we have provided you with queueInterface.ml and deque.mli, which define the 'a queue and 'a deque abstract data types and the operations which can be performed on them. Although you should read these files thoroughly, you should not modify them. Doing so might cause your homework not to compile on our submission server, in which case you will receive no credit!

Here are the recommended homework checkpoints:

Do not complete the problems out of order. You should do the work in the order specified below.

Running Your Code

You have “Run” menu options for each of these files.

Notice that while queueTest.ml contains generic tests for all the queue interfaces, if there are specific test cases you’ve written within either the LinkedQueue or SimpleQueue modules, you will need to run the appropriate executable to run those tests.

Make sure to avoid changing the method headers provided to you.

Instructions

The goal of this homework is to get practice with mutable data structures and to continue the ideas of abstraction and modularity. The homework consists of eight problems, divided into three parts.

Part 1

imp.ml

In problem 1, you will get some practice with functions that use option types, both as arguments and as return types. Problem 2 introduces mutability, aliasing, and refs. Finally, problem 3 covers equality and aliasing in great detail. You should write as many tests as you feel are necessary to ensure the correctness of your functions.

Part 2

queueInterface.ml

There’s no code to write for this file, but you should read through it in its entirety. The file defines a module signature, also known as an interface, for the 'a queue abstract data type. The word “abstract” means that we can define a queue in terms of its behavior and properties, rather than its concrete implementation: as we’ll see later on, lists and mutable linked data structures can be used to represent queues.

queueTest.ml

This file introduces a reusable module that can be used to test other modules which conform to the QUEUE interface defined in queueInterface.ml. Because we will be implementing QUEUE in two different ways, we can save some work by writing test cases against the interface (since the two implementations have that in common). Problem 4 is to write these tests.

You should make sure to thoroughly test all of the values defined in queueInterface.ml. We have provided some tests for most of the provided functions; you are responsible for completing the test suite. Specifically, you must add all tests for truncate and delete, plus whatever additional tests seem useful for the other functions. Your TAs will be manually grading the completeness of your test coverage just for truncate and delete. (The tests you write for other functions will not be graded, though of course they will help you write correct solutions to the rest of the problems.) It’s a good idea to write these tests before moving on to the next file!

simpleQueue.ml

Problem 5 develops a very simple implementation of the QUEUE interface, using lists as the backing data structure.

linkedQueue.ml

Problem 6 develops a more interesting implementation of the QUEUE interface based on mutable linked lists.

Representation Invariants

While implementing the required functions, you will be responsible for maintaining the following representation invariant about queues.

Part of your grade for this part will be based on how well you maintain and leverage the invariants in your implementation. We will be manually grading this aspect. Note that some ways of implementing the required functions, while technically correct, are not the best implementations given the invariants. In particular, make sure you understand tail recursion!

Part 3

deque.mli

There’s no code to write for this file, but you should read through it in its entirety. The file defines a module signature, also known as an interface, for the 'a deque abstract data type. The word “abstract” means that we can define a deque in terms of its behavior and properties, rather than its concrete implementation.

dequeTest.ml This file allows you to write tests for the functions in deque.ml.

You should make sure to thoroughly test all of the functions you must implement in deque.ml. We have provided many tests for the provided functions; you are responsible for completing the test suite. Specifically, you should add tests for remove_head, remove_tail, delete_last, delete_first, and reverse. Your TAs will be manually grading the completeness of your test coverage in Problem 7. Finish writing your tests before moving on to the next file!

deque.ml Problem 8 introduces the deque (pronounced ‘deck’) data type, which is another linked data structure. Deques are similar to queues, but with the ability to insert and delete at both ends; that is, they are “double-ended queues”.

Representation Invariants

graph.ml This file is a challenging kudos problem.

Grading

There are 100 total points, broken down as follows:

As with Homework 3, we will be manually grading a portion of your homework. 5 points will go to Design - this includes utilizing tail recursion and leveraging invariants in your implementation. Another 5 points will go to testing. You will receive a maximum of 90 points when you submit.

For this assignment, you may submit without penalty up to 3 times. Each additional (on time) submission costs you 5 points.

A Caveat on Equality