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: April. 6th, 2016 @ 12:00pm (NOON)

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.

  • DUE DATE: April. 15th, 2016 @ 12:00pm (NOON)

Graphs and paths

You are given the following data definitions for a graph 

 
;; A Node is a Symbol 
;; INTERP: represents the name of a node in a graph

;; A Distance is a PosInt
;; INTERP: represents distance in miles

;; An Edge is (list Node Distance Node)
;; e.g. (list 'A 10 'B)
;; INTERP: represents an edge from 'A to 'B with the distance from 'A to 'B being 
;;         10 miles

;; A Path is a List<Edge>
;; A Graph is a Set<Edge>
;; NOTE: you can use the definition of Set from your previous assignment.

You are asked to provide the following functions on Graphs

  1. valid-path? that consumes a graph and a path, and returns true if the path is valid for the graph, and false otherwise. A path is valid for a graph if it is possible to follow the each edge in order from the path on the graph, i.e., the graph contains these edge from the path and we can follow them in the order given by the path.
  2. valid-st-path? that consumes a graph g, a start node s, an end node t, and a path p, and returns true if starting at node s in g and following, in order, the edges in p, will lead us to t. The function should return false otherwise.
  3. find-st-path that consumes a graph g, a start node s and an end node t and returns a path p that starts at s and ends at t in the graph g. The function should return false if there is no such path.
  4. find-shortest-distance-st-path that consumes a graph g, a start node s and an end node t and returns the path p that starts at s ends at t in the graph g and when we add the distances of each edge is p that is the shortest distance from s to t in g. The function should return false if there is no such path.

Your solutions should also work for graphs that contain cycles.