.he 'CSC3030'Programming Paradigms Practical Work'-%-'
.fo 'LA'Computer Science, Monash University'Sem1 1993'
.nh
The practical work counts for 30% of the course mark.
.sp 0.5
The objective is to become reasonably proficient at programming in
\fBIcon\fP.
This relates particularly to its novel features:
backtracking, co-expressions, dynamic typing, generators.
Do not just write C, Pascal or Turing in Icon!
.sp 0.5
Solve some or all of the exercises below.
Keep your solutions in your C.C. Dec-station directory.
You will have to demonstrate your solutions
(we will rlogin from CSci and run them),
explain them and discuss other programming problems
at a 20 minute interview.
.sp 0.5
Your mark will depend on your \fIunderstanding\fP of the solutions and of Icon.
.sp 0.5
Interviews will be held, at times to be arranged, in week 10 (10 May onwards).

.ne 4
1. Write Icon programs to solve some combinatorial problems eg:
   Thue sequences  (eg. 1 2 1 3 1 2 3 1, but not 1 2 1 3 2 1 3 (repeat 2 1 3)),
   partition n (eg. 5 = 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1),
   knight's-tour of chess-board,
   see N-queens problem in notes, solve in some other way.

2. Write a program to build a binary search tree
from a list of numbers
.(b
.ft CW
eg. 6 7 1 4 2 3 8 4 5
.sp 0.5
root--------->6
            .   .
          .       .
         1         7
          .         .
           .         .
            4         8
           . .
          2   5
           .
           3
.sp 0.5
infix: 1 2 3 4 5 6 7 8
.ft
.)b
Write a \fBgenerator\fP to traverse a BST in infix order [see Icon book
and example tree.icn].

.ne 3
3. Write \fBco-expressions\fP to traverse two binary search trees in infix 
order and to print out their combined contents in a single sorted output
stream.
(Do not build and merge lists, arrays, files
or other intermediate data structures.)

.ne 4
4. (a) Write a parser for propositional logic:
    identifiers:  eg. p, q, fred
    operators: &, or, ~ (not), => (implies)
    parentheses: (  )

.ne 5
4. (b) Write a "theorem prover" for propositional logic
   eg. ((p=>q) & (q=>r)) => (p=>r)   --> tautology
       (p=>q) => (q=>p)   --> satisfiable
       (p=>q) & ~q & p   --> contradiction
.br
Do not just translate the Turing theorem prover.

.ne 4
5. Stable Marriage Problem:
There are n unmarried women and n unmarried men and each one wants to
get married to someone (of the opposite sex).
Each woman lists the men in order of preference and
each man lists the women in order of preference.
A collection of marriages is \fIstable\fP iff
it does not contain any examples of marriages <w1,m1> and <w2,m2>
where w1 prefers m2 to m1 and m2 prefers w1 to w2
(or w1 and m2 would "run off" together).
.br
Use \fBco-expressions\fP to find
(i)\ a collection of stable marriages,
(ii)\ all collections of stable marriages.
.br
Note 1: The individual men or women do not necessarily get their
first or low-order preferences!
The women's optimal solution is where the sum of their preferences is as low
as possible.
The men's optimal solution is where the sum of their preferences is as low
as possible.
These solutions are not necessarily the same!
Hint: it pays to take the first step.
.br
Note 2: The university-admissions-problem is equivalent to the SMP.

.ne 3
6. Write a self-reproducing Icon program.
It must not do any input of any kind.
When compiled and executed it must print an exact copy of itself.
The "winner" is the shortest such program.