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. Make sure that you read up to Chapter 16 of the lecture notes before beginning this assignment. There is also an FAQ document for this homework available.

Assignment Overview

Once again, for this homework you will be working in multiple files, all of which will be automatically zipped into a hw04-submit(DATE).zip within Codio.

• imp.ml: practice with options, aliases, and equality
• queueTest.ml: a reusable module that we'll use for testing different queue implementations
• simpleQueue.ml: contains SimpleQueue, an implementation of the queue abstract data type using a list
• linkedQueue.ml: contains LinkedQueue, an implementation of the queue abstract data type using mutable, linked datastructures
• dequeTest.ml: a separate file in which you will write tests for deque.ml
• deque.ml: an implementation of the deque data type using mutable, linked datastructures
• graph.ml: kudos problem about the graph data type

You must submit the zip file containint just these seven files to run the online testers.

In addition to these files, we have provided you with queueInterface.ml, which defines the 'a queue abstract data type and the operations which can be performed on it. Although you should read this file thoroughly, you should not modify it (doing so might cause your homework not to compile on our submission server, and you will receive no credit)!

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.

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 deem necessary to ensure the correctness of your functions.

Part 2

queueInterface.ml

There's no code to write for this part, but you should read through this file in its entirety. This 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 datastructures can be used to represent queues.

queueTest.ml

This file introduces a reuseable 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 many tests for the provided functions, and you are responsible for completing the test suite. Specifically, you must add all tests for truncate and delete. Your TAs will be manually grading the completeness of your test coverage in Problem 4. Finish writing your 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.

• Either q.heal and q.tail are both None
• or q.head and q.tail are both Some nodes, and
  • q.tail is reachable by following 'next' pointers from q.head
  • q.tail's next pointer is None

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 most optimal implementations given your invariants. In particular, make sure you understand tail recursion!

Part 3

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, and you are responsible for completing the test suite. Specifically, you must 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 datastructure. 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

• The deque is empty, and the head and tail are both None, or
• the deque is non-empty, and for head = Some n1 and tail = Some n2
  1. n2 is reachable from n1 by following next pointers
  2. n2.next = None (there is no element after the tail)
  
  
  3. n1 is reachable from n2 by following prev pointers
  4. n1.prev = None (there is no element before the head
  
  
  5. for every node n in the deque:
     • if n.next = Some m then
       m.prev = Some mp and n == mp
     • if n.prev = Some m then
       m.next = Some mn and n == mn

graph.ml

This file is a challenging kudos problem.

Grading

There are 100 total points, broken down as follows:

• Problem 1 (Options): 5
• Problem 2 (Mutability): 7
• Problem 3 (Equality): 8
• Problems 4 and 7 (Testing): 5 (manually graded)
• Problem 5 (Simple Queues): 5
• Problem 6 (Linked Queues): 25
• Problem 8 (Deques): 35
• Kudos Problem (Graph): n/a
• Design: 5 (manually graded)
• Coding Style: 5 (manually graded)

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. 5 points will go to following the style conventions found in the OCaml Style Guide, and attending your recitation's Code Review. The final 5 points will go to testing. You will receive a maximum of 85 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 Note on Equality

• = and == are NOT the same
  = denotes STRUCTURAL equality while == denotes REFERENTIAL equality.
  Structural v. Referential?
  Structural means that two things have the same contents and the same shape.
  Referential means that two variables (i.e. a and b) both point to the same memory location. To understand this, you may want to draw an ASM heap diagram.

• You should NOT check for referential equality between options
  OCaml's compiler will be kind and will say that "None"s are equivalent, but this is NOT the case with Some.
  More details on this in imp.ml!