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.

Point Distribution

The breakdown of points in this assignment is as follows:

• Finger Exercises (imp.ml): 15 points
• Queues (q.ml): 25 points
• Deques (deque.ml): 45 points
• Graphs (graph.ml): 0 points, many kudos
• Use of invariants, style, and test case points (manually assigned by TAs): 15 points

You have three "free" attempts, each additional on-time submission will cost you 5 points.

A Note on Equality

OCaml has a nifty thing about equality that you will see in your homework. What's that, you ask?

• = 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.

• 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.
  Without going into the details, Some n == Some n will return true or false haphazardly, even if "n"s in question are the SAME EXACT THING.
  If you want to find out why, feel free to ask one of us.