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. The assignment will be worth only 1% of your final grade to ensure that any initial stumbles won’t have a seriously negative effect.
Please track the time that you spend working on this assignment. We ask you to report it in your submission, and we will make a statistical summary available afterwards. On a similar (but somewhat easier) assignment last year, the mean was 6.4 hours, and the standard deviation was 3.4 hours.
Collaboration policy: This assignment is to be completed as an individual. Before continuing with this assignment, it is mandatory that you read the course Academic Integrity policies.
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. Only the last problem relies on material from lecture 4, so you can safely wait until that lecture has occurred before attempting it.
Before Beginning
Can we, the course staff, ask for your help? Every semester, there are many questions asked on Campuswire that could have been answered just by reading more closely. Remember that you are part of a learning community. It’s good to have and to ask questions, and the course staff is here to help you learn by answering them. But, it’s not okay to make the course staff do the reading for you. Our expectation is that you do the due diligence to search for the answers first. Use the website’s search feature, as well as the Find feature built into your web browser.
It is mandatory that you immediately read all five documents linked at the top of the programming assignments page. They describe how your work will be graded, and they answer many questions that you will have. You also need to read this entire assignment handout. Do that before you ask any questions, and before you write any code, just so that you have an idea where you are headed.
Thanks for your help with this! It will keep the entire course running more smoothly.
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 docs
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 amore powerful
unit testing tool called OUnit.)
The test cases provided above are a good starting point. Here they are, expressed as assertions:
(* Test leap day in a noncentury leap year. *)
let () = assert (valid_date 2020 "Feb" 29)
(* Test invalid day. *)
let () = assert (not (valid_date 2010 "Jun" 50))
Now add at least three more assertions to test other inputs. Before each, add a brief comment (like the ones above) to explain why you chose that test case. Make sure that none of your test cases are (with high probability) redundant: don’t, for example, add a test of day 51, because we already have a test for day 50.
After those three, you are free to add even more assertions, but you do not have to keep commenting them.
Code quality: Now, take some extra time to make your code as readable and elegant as you can. See the code quality rubric at the end of this handout for suggestions.
Function 2: Syracuse
Define a function syr : int > int
that
takes a strictly positive integer n
as input, applies the following Collatz
operation repeatedly to that input until the result is 1, and returns the number
of times the Collatz 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 Collatz 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.)
Testing: Follow the same instructions for testing as Function 1: at least three commented, nonredundant cases, plus more test cases as you wish.
Code quality: Again, take some extra time to make your code as readable and elegant as you can. See the code quality rubric at the end of this handout for suggestions.
This is the stopping point for satisfactory scope.
Function 3: Nacci
This problem relies on lists, which we will cover in the next lecture.
In the Fibonacci sequence, each number is 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 the n
step Fibonacci sequence. For example,
nacci 2 6 = [1; 1; 2; 3; 5; 8]
. Your function does not have to handle
integer overflow.
Efficiency:
Your implementation of nacci
must be tail recursive, and it must run
in time that is polynomial in k
and n
. It is actually quite easy
to design a naive exponentialtime algorithm by simply implementing the
equations above in code, and you might even try that first. If you’ve
forgotten the difference between polynomial and exponential time, here’s
what’s important: your algorithm is going to have to avoid recomputing
values in the sequence. That is, if the algorithm has already computed
\(F_k^{(n)}\), then it should not recompute that value as part of
computing \(F_{k+1}^{(n)}\). It is your responsibility to invent the
algorithm. We strongly suggest that you design it on paper first, rather
than immediately trying to implement it.
Concrete execution time bounds are somewhat meaningless, since some people
have slower or faster machines. But as an example, when n
is 2 and k
is 1 million, a polynomialtime algorithm
will probably execute within about 2 seconds. That execution
time will of course increase as the inputs increase.
Testing: Follow the same instructions for testing as Function 1: at least three commented, nonredundant cases, plus more test cases as you wish. For this function, you will probably want to have several more to convince yourself that your implementation is correct.
Code quality: You know what to do by now.
This is the stopping point for good scope. There is no excellent scope on this assignment.
Rubric
 30 points: submitted and compiles
 25 points: satisfactory scope
 25 points: good scope
 10 points: testing
 10 points: code quality
Testing Rubric. Later in the semester we will focus much more heavily on developing test suites. For this first assignment, though, here is what the graders will assess:
 Each of the three required functions, whether it was implemented fully or not, has at least three test cases that are explained in a comment and are nonredundant.
 Any test cases that are failing are commented out, so that the program does not actually produce an exception when executed.
Code Quality Rubric. There are many aspects of quality that make code easier to read. We will focus on just a few for this first assignment. The graders will assess the following aspects of your source code:
 The programmer’s name and NetID are supplied at top of file.
 Each of the three required functions has a specification comment documenting the function in the way described by the 3110 textbook in sections 2.3.7 and 2.3.8, including preconditions. You may not punt by writing, “see the handout.” But, it is fine to copy information from this handout. You may assume the reader knows the definitions of the terms “leap year rule”, “Collatz operation” and “nstep Fibonacci sequence”. Anything else has to be explained. Other functions you add ought to have specification comments, too, but we won’t assess it on this assignment.
 White space (the space character and empty lines) is used effectively.
 Indentation of
let
andif
follows the OCaml Community guidelines.  Identifiers consistently use
snake_case
, notcamelCase
.  No line is wider than 80 columns.
 No tabs (ASCII character 9) are used, only spaces.
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.
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!