CSCI 4430 Programming Languages

Homework 5: Scheme Problem 2

Due: Friday November 4 @ 1:59pm

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 HW4, Submitty grades running a command-line r5rs interpreter.

Longest Non-Decreasing Subsequence

You will write two Scheme functions that compute a longest non-decreasing 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 non-decreasing subsequence. In the above example, your program might also find (1 2 2 4) or (1 2 2 2).

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 a non-decreasing sequence of numbers
         print s and quit

Unfortunately, this algorithm is inefficient. The number of distinct sublists of a given list is 2ⁿ (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 algorithm, 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 HW4, 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. When testing lis_slow we test with inputs with unique longest non-decreasing subsequence, or we test the length only.

Errata

None yet. Check the Announcements page regularly.