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

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 data structures
• 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 data structures
• graph.ml: kudos problem about the graph data type

In addition to these files, we have provided you with queueInterface.ml and dequeInterface.ml, 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 file thoroughly, you should not modify them (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.

Make sure to avoid changing 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.

• Either q.head 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 best implementations given the invariants. In particular, make sure you understand tail recursion!

Part 3

dequeInterface.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 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

• 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. 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 Caveat 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 pointers point to the very 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 two "None"s are equivalent, but this is NOT the case with "Some"s.
  More details on this can be found in imp.ml