Courses/CS 460/Fall 2005/Homework/Xuong Tsan/Oct 8

From CSWiki

October 8th homework solutions

Contents 1 Homework Page 2 Question 3 To Singleton

[edit] Homework Page

Homework page is: | http://cs.calstatela.edu/~wiki/index.php/Courses/CS_460/Fall_2005/Homework/Xuong_Tsan

[edit] Question

Consider the following non-recursive version of merge-sort. For concreteness, we'll use the list [e f c b d a] as an example.

1. Convert the original list into a list of singleton lists [[e] [f] [c] [b] [d] [a]].
2. Merge pairs of lists to get [[e f] [b c] [a d]]
3. Repeat the pair merge process until only one sublist is left:
   1. [[b c e f] [a d]]
   2. [[a b c d e f]]
4. The one remaining sublist [a b c d e f] is the answer.

Write your version of this.

Note: You will have to use tail recursion to implement the iteration. But this will not be the standard recursive merge sort because you don't start with a complete list, which you split in half, sort each half recursively, and then merge together.

Implement 5 other recursive methods from the List module. Select at least two for which an argument is a function or a procedure.

Please don't use any of the built-in loop constructs. You may define your own For or other loop procedures and then use them.

[edit] To Singleton

  local 
     proc {Singleton List ?Ans}
       case List of nil then Ans = nil
       [] L|Ls then
          Ans = [L]|{Singleton Ls}
       end
     end
   in
     {Browse {Singleton [a b c d e]}}
  end