A0: Warmup
Welcome to the first assignment in CS 3110!
This assignment is a warmup: it’s some gentle practice that’s meant to prepare you for the rest of the assignments, which will be more intense. It will also give you the opportunity to verify that your OCaml environment is set up correctly, and to experience the 3110 assignment workflow. Because we want everyone to have that experience, this assignment is to be done as individuals, not with partners nor with teams. The assignment will be worth only about 1% of your final grade to ensure that any initial stumbles won’t have a seriously negative effect.
What you’ll do: Implement three short, unrelated functions; document them; and test them with assertions.
Objectives:
 Use OCaml operators,
if
expressions, functions, recursion, lists, and assertions.  Write specification comments in OCaml.
 Begin to appreciate good vs. poor style in OCaml.
Lectures covered: This assignment relies on material from lectures 1–4.
Before Beginning
Make sure that you have read these documents:
 Assignment FAQ
 Core Assignment Values
 Coding Standards
 Logistical Responsibilities
 This entire assignment writeup
Also make sure you read:
And take the CMS quiz on it. Completion of that quiz is a prerequisite to submitting A0. Because of how important it is for you to understand that AI policy, we will drop from CMS anyone who does not complete the quiz before its deadline.
Getting Started
Download the release code from CMS. Run make check
from the folder
containing the release code. You should get output that includes the
following (other lines might be interspersed):
===========================================================
Your OCaml environment looks good to me. Congratulations!
===========================================================
Your function names and types look good to me.
Congratulations!
===========================================================
If instead you get warnings about your OCaml environment, seek help
immediately from a consultant. Assuming your environment is good, you
should not get warnings about about your function names and types.
After completing each function, you should rerun make check
to ensure
that you haven’t changed any required names or types.
There are a few other targets provided in the release code:
 Running
make
will open the toplevel and automatically#use
your code. That should be useful for any interactive testing you want to do.  Running
make test
will build and noninteractively run your solution. There won’t be any output to the screen, unless an assertion fails or you’ve added a print statement.  Running
make doc
will extract your documentation comments to HTML and put it in thedoc/
directory. Opendoc/Warmup.html
to browse it.  Running
make clean
will delete files generated from your source code.  Running
make finalcheck
will do the same asmake check
as well as two other things, which are described under the submission instructions at the end of this handout.
Now you’re ready to implement each of the following three functions
in the file warmup.ml
. In doing so, consider: how elegant can you
make your implementation?
Function 1: Valid Date
Define a function
valid_date : int > string > int > bool
that takes an an integer y
,
a string m
, and an integer d
as input. The function returns true
if y
and m
and d
form a valid date, and returns false
otherwise.
For this problem, we define a valid date as having

a year that is strictly positive (i.e., greater than or equal to 1);

a month that is one of the following 3letter capitalized abbreviations: Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec;

a day that is between 1 and the number of days in that month, inclusive, taking leap years into account. Use the usual leap year rule for the Gregorian calendar: “Every year that is exactly divisible by four is a leap year, except for years that are exactly divisible by 100, but these centurial years are leap years if they are exactly divisible by 400.”
For example, valid_date 2020 "Feb" 29 = true
, and
valid_date 2010 "Jun" 50 = false
.
(Calendar geeks: pretend that the entire Common Era has used the Gregorian calendar.)
Testing.
We encourage you to get into the habit of testing your implementation
early and often. Of course, it’s convenient to do that in the toplevel.
But for repeatability, it’s important to express tests as part of
your code base. For this warmup, please put assertions in your warmup.ml
to test your function. (Later assignments will use OUnit, a more powerful
unit testing tool.)
The test cases provided above are a good starting point. Here they are, expressed as assertions:
let () = assert (valid_date 2020 "Feb" 29)
let () = assert (not (valid_date 2010 "Jun" 50))
Now add some more assertions to test other inputs.
Function 2: Syracuse
Define a function syr : int > int
that
takes a strictly positive integer n
as input, applies the following operation
repeatedly to that input until the result is 1, and returns the number
of times the operation had to be applied. If the input is already 1, the
function returns 0.

If
n
is even, divide it by 2. 
If
n
is odd, triple it and add 1.
For example, syr 1 = 0
, because the operation doesn’t need to be applied
at all: the input is already 1. Further, syr 2 = 1
, because applying
the operation once produces 1. Similarly, syr 10 = 6
.
Your function does not have to be tail recursive, nor does it have to handle integer overflow.
(Why call this function syr
? Because it is related to the
Collatz conjecture aka the Syracuse problem.
See Wikipedia and XKCD.
As far as we know, the function terminates on all positive OCaml integers.)
Add assertions to your file to test this function. Here are a few to get you started:
let () = assert (syr 1 = 0)
let () = assert (syr 2 = 1)
let () = assert (syr 10 = 6)
Function 3: Nacci
This problem relies on lists, which we will cover in the next lecture.
In the Fibonacci sequence, each number of the sum of the previous two numbers in the sequence. The \(n\)step Fibonacci sequence generalizes that to the sum of the previous \(n\) numbers in the sequence, where \(n\) must be at least 1. Let \(F_k^{(n)}\) denote element \(k\) of the \(n\)step Fibonacci sequence, defined as follows:

For all \(n\), let \(F_1^{(n)} = 1\) and \(F_2^{(n)} = 1\).

For all \(n\), and for all \(k\) such that \(k > 2\), let \[ F_k^{(n)} = \sum_{i=1}^n F_{ki}^{(n)}. \]

Since the summation above might need to include some “nonexistent” elements of a sequence, let them be 0. Formally, for all \(n\), and for all \(k\) such that \(k \leq 0\), let \(F_k^{(n)} = 0\).
Define a function
nacci : int > int > int list
that takes an integer n
and an integer k
as
input, both of which must be strictly greater than zero, and returns the first
k
elements of n
step Fibonacci sequence. For example,
nacci 2 6 = [1; 1; 2; 3; 5; 8]
. Your function does not have to handle
integer overflow.
Add assertions to your file to test this function. Here are a few to get you started:
let () = assert (nacci 1 6 = [1;1;1;1;1;1])
let () = assert (nacci 2 6 = [1;1;2;3;5;8])
let () = assert (nacci 3 6 = [1;1;2;4;7;13])
Scope
As discussed in the Core Values, we expect high quality code and timely completion from you. But if you’d like to reduce the scope of the assignment, you can do that. Here’s what we consider a satisfactory, good, and excellent solution:

Satisfactory: The solution passes
make check
. Thevalid_date
function returnstrue
for all valid dates except Feb. 29, where it may be incorrect; and it might be incorrect on invalid dates. Thesyr
function is correct. Thenacci
function is correct whenn
is 2 (i.e., just the standard Fibonacci sequence), but may run in time that is exponential ink
. Concretely, whenk
is small (i.e., 40 or less) the running time should be only about 1 or 2 seconds, but it might increase dramatically ask
increases. 
Good: The
valid_date
function is also correct for Feb. 29 and all invalid dates. Thenacci
function is also correct for all values ofk
, but it may still be as inefficient as in the Satisfactory scope. 
Excellent: The
nacci
function runs in time that is polynomial ink
andn
, and is tail recursive. That will require a more clever implementation that does not recompute values in the sequence. Concretely, whenn
is 2 andk
is large (i.e., on the order of 1 million), the running time is still only about 1 or 2 seconds; but that time may increase asn
increases.
Submission
Set the hours_worked
variable at the end of warmup.ml
to the number
of hours you spent working on this assignment, rounded to the nearest
integer. Please don’t include the time that you spent installing
OCaml or the VM.
Ensure that your solution passes make finalcheck
. That will do the
same as make check
, as well as two other things. First, it will check
to make sure you’ve set hours_worked
. Second, it will compute a short
“fingerprint” of your submission called an MD5 sum. These two “final
check” operations are beta functionality that we have not deployed
before in 3110. Please report any issues to consultants.
Submit your warmup.ml
on CMS. The MD5 sum that CMS reports for
your submission should be the same as the MD5 sum that make finalcheck
reported. If not, you probably uploaded the wrong file. Doublecheck
before the deadline that you have submitted the intended version of your
file.
Congratulations! You’ve finished your first 3110 assignment!