CS 246 Programming Paradigms
Project #1
Due on Thursday, February 7
Design and implement the following problems as primary functions in IFP. You may choose to do ANY two of the following three problem statements.
PROBLEM STATEMENTS
(1) Prime Classes:
Students in the class of 2003 entered college in 1999. What is special about these numbers is that both 1999 and 2003 are prime numbers. We are interested in finding out all such prime classes that exist between 1900 and 2100 (you will be surprised by the answer!). Write an IFP function, primeclasses that finds all the prime classes between any two given years.
Example:
show <1900, 2100> : primeclasses -> <....<1999, 2003> ...>
The output will be ALL prime class pairs between the two given years.
a<c, b<c, c<d, d<e, d<f
In this case there are many total orderings acceptable as output, three of which are
Given the information about the initial partial ordering, we have to produce any one of the compatible total orderings as output. (By the way, in various guises, this is a problem that repeatedly turns up in Computer Science). The partial ordering will be input as a list of pairs such that if <p q> is in the list, then p immediately precedes q in the ordering. For the partial ordering shown above, this would be
< <a c> <b c> <c d> <d e> <d f> <g h> >
We also need our function to input the set of all elements involved in the ordering. At first sight one might think that this set could be deduced from the list of pairs. There might be isolated elements (elements that do not precede nor are preceded by, anything else), however, and these would not be present in the list of pairs, since our notion of 'immediately precedes' is irreflexive, i.e., does not allow for pairs like <p p>.
Example:
show <<>,<>> : tsort --> <>
show <<a b c d e f g h> <<a c> <b c> <c d> <d e> <d f> <g h> >> : tsort --> <b a c g h d f e>
(or any of the other total orderings possible).
(3) Hamming Numbers
Generate, in ascending order, the first k terms of the series
1 2 3 4 5 6 8 9 10 12 15 16 18 ...
of those numbers whose prime factors are 2, 3, 5 only.
Example:
show 0 : ham --> <>
show 7 : ham --> <1 2 3 4 5 6 8>
show 10: ham --> <1 2 3 4 5 6 8 9 10 12>
You are allowed to make reasonable assumptions about any situation not mentioned in these three specifications.
INPUT DATA
Testing these functions is your responsibility. When ready to submit, design a test run that showcases all the possibilities in input. There is no point in submitting multiple runs on similar data. Rather, each run should exhibit a different aspect of your implementation.
IMPLEMENTATION NOTES
A substantial portion of your grade on this project will be based on the DESIGN of your program, not just its correctness. To that end and others, these points should be kept in mind:
(1) The functional facilities of IFP should be fully utilized. Do NOT use the "while" form of IFP under any circumstance.
(2) For reasons that will be elaborated in the lecture class, it is preferable to write non-repetitive functional code, if at all possible.
(3) There is no need to comment every line of code! Major code sections should be preceded by terse, but not cryptic, comments.
(4) You will, almost certainly, need to code helper functions to the three primary functions. It would be a good idea to identify common tasks needed in all three parts, and code them as helper functions for use wherever needed. (HINT: a function that takes an element, and a set of elements, and returns the set with the element removed, will be useful for this project).
(5) See the directory ~dkumar/cs246/IFP for some useful information and examples.
(6) You are urged to start early. Last minute work is rarely of top quality.
WHAT YOU HAVE TO SUBMIT
Learn to use the 'script' facility of Unix. When ready to submit, simply create a script file of your interactive IFP run, and add it to the relevant section of your report.This is what you submit on the due date.
Alternatively, you could run a shell inside GNU-Emacs, run a IFP session, and save the buffer to be added in the report.
Submit a printout of all your function definitions and all sample runs.