...
- When making function examples, we need even more examples, as they help us to find the algorithm we will use.
- When making a template, we don't follow the structure of the data. Instead, we ask ourselves six questions:
- What is (are) the trivial case(s)?
- How do we solve the trivial case(s)?
- For the non-trivial case(s), how many subproblems do we use?
- How do we generate these subproblems?
- Can we combine the results of these subproblems to solve the given problem?
- How do we combine the results of these subproblems?
- We use the answers to the preceding questions to fill in the following very general template:
*Code Block (define (f _args_) (cond [(_trivial_? _args)) (_solve-trivial_ _args_)] [else (_combine_ (f (_generate-subproblem-1_ _args_)) ... (f (_generate-subproblem-n_ _args_)))]))
- We add a step to reason about why our algorithm terminates, since this is no longer provided by simply following the structure of the data.
...
The open and close parenthesis objects (not the symbols '|(|
and '|)|
) clearly play a critical role in token streams because they delimit general lists.
Examples:
(listify empty)
{{= empty
}} .(listify (list (make-open) (make-close))
{{= (list empty)
}} .(listify (list (make-open) 'a (make-close))
{{= (list '(a))
}}(listify (list (make-open) 'a 'b (make-close))
{{= (list '(a b))
}}(listify (list (make-open) (make-open) 'a (make-close) 'b (make-close))
{{= (list '((a) b))
}}
You will probably want to define the following predicate
...
in your program. As a rough guideline follow the parse.ss (https:wikiriceedudisplayCSWIKI211lab04parsess) program that we wrote in class on Monday, Feb 2. Note that finding the first input is more involved than finding the first line. You will probably want to explicitly check for errors in the input because they correspond to natural tests on the form of the input.
...
Code Block |
---|
;; insertion sort (define (isort alon) (cond [(empty? alon) empty] [(cons? alon) (insert (first alon) (isort (rest alon)))])) (define (insert new sortedlon) (cond [(empty? sortedlon) (list new)] [else (if (< new (first sortedlon)) (cons new sortedlon)] (cons (first sortedlon) (insert new (rest sortedlon))))])) ;; quicksort (adapted to functional lists) (define (qsort alon) (cond [(empty? alon) empty] [(cons? alon) (local [(define pivot (first alon)) (define other (rest alon)) (define lesser (filter (lambda (n) (<= n pivot)) other)) (define greater (filter (lambda (n) (> n pivot)) other))] (append (qsort lesser) (list pivot) (qsort greater)))])) |
...
If your programs only sort small lists a few times, it doesn't matter; any sort that is easy to write and have correct woks correctly is fine. However, for longer lists, the difference really is huge. In the real world, sorting is an operation often done on very long lists (repeatedly).
...
- We need some data to use for our timing experiments. Write a function
up: nat -> (list-of nat)
which constructs a list of naturals starting with0
in ascending order or retrieve it from a previous lab. For example,(up 7)
returns(list 0 1 2 3 4 5 6)
. You can probably write it faster usingbuild-list
that you can retrieve it. Similarly, write a functiondown: nat -> (list-of nat)
that constructs a list of naturals ending in0
in descending order. For example,(nums-down 7)
returns(list 6 5 4 3 2 1 0)
. - Now write a function
that constructs a list of random numbers in the range from {{Code Block rands
Wiki Markup 0
}} to {{32767
}}. To create a single random number in the range from {{0
}} to {{_n
_}}, compute {{(random
_n+1
_)
}}. For larger numbers in the range {{\[0,
32768)
}}, try:
Note:Code Block (define max-rand 32768) (random max-rand) ; random is built-in
random
is a function in the Scheme library, but it is not a mathematical function, since the output is not determined by the input. Now, make - Make sure you know how to use
time
. Time by using it to timeisort
on a list of 200 elements. Run the exact same expression again a couple times. Note that the time varies some. We typically deal with such variation by taking the average of several runs. The variation is caused by a number of low-level hardware phenomena that are beyond the scope of this course (see ELEC 220 and COMP 221). - Continue timing, filling Use the
time
operation to fill in the following chart. When you're done, compare results with other pairs in the lab.input size
...
...
...
input size
input size
...
200
...
1000
...
5000
...
up
...
...
isort
down
...
down
...
down
rand
...
...
rand
up
...
...
qsort
down
...
...
down
rand
...
...
rand
...
- When you are done, compare your results with those generated by other pairs in the lab.
COMP 280 introduces concepts of how these algorithms behave in general.
The punchline is that we can say that both insertion sort and
quicksort on lists are "_O(n
HTML |
---|
<sup> |
2
HTML |
---|
</sup> |
)_"
*2) in the worst case.
I i.e., for a list of n elements, they each take about
_c × n
HTML |
---|
<sup> |
2
HTML |
---|
</sup> |
_ n**2 evaluation steps to sort
the list, for some constant
HTML |
---|
<var> |
c
HTML |
---|
</var> |
.
Furthermore, in the "average" case, Quicksort does better: O(n log n).
A well-coded formulation of quicksort using arrays almost never exhibits worst-case behavior. COMP 280, and later COMP 482, show precisely what big O notation means these statements
mean and how to derive them.
...
Ackermann's Function Example
...
...
</A>
HTML |
---|
<strong> |
If you have time…
HTML |
---|
</strong> |
Here's time, here is the definition of a strange numerical function on natural numbers,
called Ackermann's function:
HTML |
---|
<PRE> |
Code Block |
---|
A(m,n) = |
...
n+1 if m=0 = A(m-1,1) if m>0 and n=0 = A(m-1,A(m,n-1)) |
...
if m>1 and n>0
|
HTML |
---|
</PRE> |
Note that this definition is not structurally recursive.
In fact, it cannot be defined in a structurally recursive manner.
( In technical jargon, the function is not
HTML |
---|
<DFN> |
primitive recursive
HTML |
---|
</DFN> |
.
See
HTML |
---|
<A HREF="http://www.owlnet.rice.edu/~comp481/"> |
HTML |
---|
</A> |
for what that means.)
Here's the equivalent Scheme code (assuming m
nad n
are natural numbers:
HTML |
---|
<PRE> |
...
Code Block |
---|
|
...
(define |
...
(ack m n |
...
)
|
...
|
...
(cond |
...
|
...
[ |
...
(= m 0 |
...
) |
...
|
...
(add1 n |
...
) |
...
]
|
...
|
...
[ |
...
(= n |
...
0) (ack |
...
( |
...
sub1 m) |
...
1)] |
...
|
...
[else (ack (sub1 m |
...
) |
...
(ack m |
...
(sub1 n |
...
) |
...
) |
...
) |
...
] |
...
) |
...
)
|
HTML |
---|
</PRE> |
HTML |
---|
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent"> |
HTML |
---|
<CAPTION class="MsoBodyTextIndent"> |
Ackermann's function exercises
...
...
</CAPTION>
HTML |
---|
<TR> |
HTML |
---|
<TD> |
HTML |
---|
<OL> |
HTML |
---|
<LI> |
Try it out on some inputs.
HTML |
---|
<STRONG> |
Warning:
HTML |
---|
</STRONG> |
...
- Try
ack
on some small inputs. Warning: try very, very small inputs form
, like 0, 1, 2, or 3,
...
HTML |
---|
</li> |
HTML |
---|
<LI> |
Argue why this always terminates (for natural numbers).
HTML |
---|
</li> |
HTML |
---|
</OL> |
HTML |
---|
</TD> |
HTML |
---|
</TR> |
HTML |
---|
</TABLE> |
This function isn't very useful, except as a theoretical example of a
function that grows faster than probably any one you've seen before.
In
HTML |
---|
<A HREF="http://www.owlnet.rice.edu/~comp482/"> |
COMP 482
HTML |
---|
</A> |
,
you'll learn one use for this function.
HTML |
---|
</div> |
!! Access Permissions
...
- because
(ack 4 1)
takes a very, very long time to compute. You can compute(ack 4 1)
using DrScheme if you infer a simple non-recursive formula for(ack 3 n)
and add a clause containing this short-cut for computing
(ack 3 n)
to the Scheme code forack
. Do not try to compute(ack 4 2)
. The answer is more than 19,000 digits long. - Prove why
ack
always terminates for natural numbers. Hint: you need to use "double-induction".
Ackermann's function is not useful in constructing real software applications, but it is an important mathematical defintion because it is provably not primitive recursive and it plays an important role in the complexity analysis of some algorithms (notably union-find). In COMP 482 you will learn about union-find and its complexity analysis.