CIS 1200

Homework 4: Working with Linked Queues and Deques

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 a FAQ document for this homework.

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).”

  • imp.ml (Problems 1-3): practice with options, aliasing, and equality
  • queueTest.ml (Problem 4): a reusable module that we’ll use for testing different queue implementations
  • simpleQueue.ml (Problem 5): contains SimpleQueue, an implementation of the queue abstract data type using simple lists
  • linkedQueue.ml (Problem 6): contains LinkedQueue, an implementation of the queue abstract data type using mutable, linked data structures
  • dequeTest.ml (Problem 7): a separate file in which you will write tests for deque.ml
  • deque.ml (Problem 8): 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 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!

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 function headers provided to you.

  • Checkpoint 1: After Lecture 13, you can give problem 1-2 in imp.ml a try!
  • Checkpoint 2: After Lecture 14, you can complete problem 3 in imp.ml and get started (working ahead) on 4-8.
  • Checkpoint 3: After learning the Lecture 15 material, you can complete problems 4-8.
  • Checkpoint 4: After learning the Lecture 16 material, you double-check that your solutions use tail recursion (the natural way to write the code is tail recursive).

Tail recursion is a programming style that avoids using space on the computer’s stack by passing extra arguments to recursive functions. It is covered in Lecture 16.

Note: we encourage you to read ahead in the notes! Feel free to try problems sooner than these checkpoints recommend, using the textbook, deep dives, or other resources to get you started!

In particular, if you want to get started on the last part of the homework before Lecture 16, one reasonable approach is to just go ahead and implement the required functionality without worrying about the tail recursion requirement in the first instance. Once we’ve covered the material in lecture, you should go back and revisit these problems to (a) check whether your solution may already be tail recursive (natural solutions to most of the problems will be tail recursive without any extra effort) and (b) tidy up those that are not.

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 and aliasing. Finally, problem 3 covers equality and aliasing in 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 both be used to represent queues.

queueTest.ml

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

You should make sure to thoroughly test all of the functions 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 the problems!). It’s a good idea to write these tests before moving on to the next problem!

simpleQueue.ml

Problem 5 develops a very simple implementation of the QUEUE interface, using lists as the internal 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 (1) q.head and q.tail are both None
  • or else (2) q.head and q.tail are both Some values, and
    • (2a) q.tail is reachable by following ’next’ pointers from q.head and
    • (2b) 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. 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!

Reminder: don’t forget to put parens around the then- and else-branches of any conditional expressions that perform commands in their branches.

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 are implementing in deque.ml. We have provided many tests for the provided functions; you are responsible for completing the test suite for yours. 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, 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.

OCaml StyleChecker

Before submitting to Gradescope, you should run the stylechecker in Codio to make sure you have no style violations.

  1. In your project, select “Style Check Project” from the dropdown menu at the top of the screen where “Build Project” lives.
  2. Each style violation will appear with its corresponding file, line number, and a suggestion on how to fix it. If you have no violations, “No style violations” will be printed.
  3. An assignment with “No style violations” in Codio will receive 5.0/5.0 pts for Autograded Style Score in Gradescope.

If you are ever unsure about OCaml style, check out the CIS 1200 OCaml Programming Style Guide.

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): 28
  • Problem 8 (Deques): 37
  • Kudos Problem (Graph): n/a
  • Coding Style: 5

As with Homework 3, we will be manually grading a portion of your homework. 5 points will go to testing. You will receive a maximum of 95 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.

Caveats on Equality

= and == are NOT the same: = denotes STRUCTURAL equality while == denotes REFERENCE equality.

Structural v. Reference?

Structural equality means that two things have the same contents and the same shape.

Reference equality means that two pointers point to the very same memory location. To understand this, you may want to draw ASM heap diagrams.

You should NOT check for reference equality between options

OCaml’s compiler may be kind and say that two Nones are equivalent, but this is NOT the case with Somes.

More details on this can be found in imp.ml