2023年11月25日

Haskell代写 | 函数式编程 | Assignment 3

Submission Instructions

This is a team assignment. Just as with all other homework, submitted work should be strictly the work of your team. Course staff runs plagiarism detectors, and will treat excessive similarities between submissions as evidence of cheating. Form teams and submit in Submitty for autograding. Your Scheme file must be named lis.rkt. As with HW6, Submitty grades running a command-line r5rs interpreter.

Longest Increasing Subsequence

You will write two Scheme functions that compute a longest increasing subsequence from a list of numbers. For example, if you type

> (lis '(1 2 3 2 4 1 2))

you might get

(1 2 3 4)

Note that there may be more than one longest increasing subsequence. In the above example, your program might also find (1 2 2 4) or (1 2 2 2). (Strictly, you will be computing the longest non-decreasing subsequence, although I am calling it the “longest increasing subsequence”.)

You should concentrate first on simply getting a solution working. One possibility is simple exhaustive search:

    for i := n downto 1, where n is the length of the input list
        for all i-element sublists s of the input list
            if s is an increasing sequence of numbers
                print s and quit

Unfortunately, this algorithm is inefficient. The number of distinct sublists of a given list is 2n (to generate a sublist, we have two choices — include or exclude — for each of n elements).

Once you have a simple version running using the above altorithm, your next task is to find a polynomial-time solution.

To avoid typing long lists at the interpreter line, I suggest you create a few sample arguments in a file, say my_lists.rkt. You can create those definitions in DrRacket’s definition window and save them in file my_lists.rkt. For example, if my_lists.rkt may contain definitions

  (define list1 '(1 2 3 2 4 1 2))
  (define list2 '(2 4 3 1 2 1))

you can call

> (lis list1)

and

> (lis list2)
  • Write two functions, lis_slow, which implements the pseudocode above and lis_fast, which implements a polynomial solution. Both lis_slow and lis_fast consume a list of numbers as arguments and produce a list as a result, as shown in the lis examples above. Include functions lis_slow and lis_fast in your lis.rkt file.
  • You are not allowed to use imperative features of Scheme. Do not use side-effecting functions (i.e., functions with exclamation point in their names such as set!), sequencing, iteration (e.g., do, for-each) or vectors. Do not use input/output mechanisms other than the regular read-eval-print loop. (You may find imperative features useful for debugging. That’s ok, but get them out of your code before you turn anything in.) Code the algorithms in terms of the purely functional subset of Scheme we have covered in class, however you are allowed to use some additional built-in list operations, e.g., reverse, list-ref, etc.
  • Do not forget to comment your code! Just as in HW6, write comments in the style described here.

NOTEs on grading: This homework is worth a total of 60 points: lis_slow is worth 20 points and lis_fast is worth 40 points. 48 points will be awarded for functional correctness by the autograder. However, we will override the autograder if you have violated the restrictions specified above! 12 points will be awarded for the quality and completeness of your comments.

Note that when testing lis_fast we expect the “leftmost” subsequence. For example, the expected output for (1 2 3 2 4 1 2) is (1 2 3 4), not (1 2 2 4) or (1 2 2 2). Sometimes we test for the length of the subsequence only, and sometimes we test for the “leftmost” subsequence. There is no restriction on lis_slow — we test with inputs with unique longest increasing subsequence, or we test the length only.

Errata

None yet. Check the Announcements page regularly.