In this module we introduce a set of problems whose solution does not solely rely on the structure of our data but rather on a condition involving our data that we need to discover. We show how to design algorithms that use general recursion and how to informally argue for correctness and termination of our algorithm using a termination argument and a halting measure.

  1. Explain the difference between structural and general recursion.
  2. Identify algorithms that cannot be solved using structural recursion.
  3. Summarize the purpose of a termination argument.
  4. Summarize the purpose of a halting measure.
  5. Use rackunit to write tests.
  6. Use rackunit to debug a function.
  7. Explain the difference between structural and general recursion.
  8. Identify algorithms that cannot be solved using structural recursion.
  9. Summarize the purpose of a termination argument.
  10. Summarize the purpose of a halting measure.
  • DUE DATE: Nov. 30th, 2017 @ 11:59pm

Refactor Space Invaders

  1. Start by copying your solution from Assignment 6.
  2. Update your Assignment 6 to address all comments made by your Grader. All comments means
    1. comments made that did not cost you points
    2. comments made that cost you points
  3. Review your solution to Assignment 6 and refactor your code such that
    • your code uses generic data definitions
    • your code uses the predefined Higher Order Functions provided by DrRacket (e.g., map, foldl, filter, etc. when appropriate. You are also encouraged to develop your own generic functions if that is applicable (i.e., none of the predefined higher order functions can be used)
    • your code uses local appropriately for helper functions and/or common sub-expressions

Save your refactor Space Invaders into a separate file called space-invaders-refactor.rkt

Problem 1

Design a function called list->chunks that will consume a non-empty list and a positive integer n and returns a list of lists of size n, each list of size n is a sub-sequences of the input. You may assume that the length of the input list is divisible n 

 
 > (list->chunks (list "a" "b" "c" "d" "e" "f") 3)
(list (list "a" "b" "c")
      (list "d" "e" "f"))

Problem 2

DNA is often modelled by strings of the characters A, C, G and T. They are very long and so often need to be compressed. A simple way to do this is to replace all substrings of identical consecutive characters with the character followed by the length of the substring. These substrings must be as long as possible. For example, the run-length encoding of the string "AAGCCCCTTAAAAAAAAAA" is the string "A2G1C4T2A10". This is the unique run-length encoding – something like "A2G1C4T2A4A6" is not valid. Use generative recursion to write a function called dna-encode that consumes a DNA string and produces its run-length encoding.

Here are a couple of examples 


 > (dna-encode "AAGCCCTTAAAAAAAAAA") 
 "A2G1C3T2A10"

 > (dna-encode "") 
 ""

You may assume that the input string consists of capital letters only.

Also design the function dna-decode that will perform the opposite operation, i.e., given a run-length encoding return the full string. 


 > (dna-decode "A2G1C3T2A10") 
 "AAGCCCTTAAAAAAAAAA"

 > (dna-decode "") 
  ""

Problem 3

Design a function that implements bubble sort. Your function should consume a list of numbers and produce the same list of numbers but in sorted order, from smallest to largest, using the algorithm for bubble sort.