[ Posted by Urban Hafner
Mon, 26 Sep 2005 15:34:17 GMT ]
The problem
Quicksort. The following is a possible algorithm for sorting lists. Its inventor C.A.R. Hoare, called it quicksort, because it was the fastest known general-purpose sorting algorithm at the time it was invented. It uses a divide and conquer strategy to give an average time complexity of O(n_ log _n). Here is an informal description of the algorithm for the declarative model. Given an input list L, then do the following operations:
- Pick
L’s first element, X, to use as a pivot.
- Partition
L into two lists, L1 and L2, such that all elements in L1 are less than X and all elements in L2 are greater than or equal to X.
- Use quicksort to sort
L1 giving S1 and to sort L2 giving S2.
- Append the lists
S1 and S2 to get the answer.
Write this program with difference lists to avoid the linear cost of append.
My solution
I must admit that I didn’t really understand difference lists and what I did here is mostly based on modifying a version of QuickSort with appends into a version with difference lists. But what I did is mostly a copy the idea from the Flatten example in section 3.4.4 and is not based on a deep understanding of difference lists. Anyway, here it is:
fun {QuickSort L}
fun {Partition Li E Acc1 Acc2}
case Li
of nil then
Acc1#(Acc2)
[] Li1|Lir then
if Li1 < E then
{Partition Lir E Li1|Acc1 Acc2}
else
{Partition Lir E Acc1 Li1|Acc2}
end
end
end
proc {QuickSortD L ?Ds}
case L
of nil then Y in Ds=Y#Y
[] E1|E2|nil then Y in
if E1 < E2 then
Ds=(E1|E2|Y)#Y
else
Ds=(E2|E1|Y)#Y
end
[] E|nil then Y in Ds=(E|Y)#Y
[] X|_ then L1 L2 Y1 Y2 Y4 in
L1#L2={Partition L X nil nil}
Ds=Y1#Y4
{QuickSortD L1 Y1#Y2}
{QuickSortD L2 Y2#Y4}
end
end
Ys
in
{QuickSortD L Ys#nil} Ys
end
Tags book, conquer, CTM, difference, divide, exercise, list, mozart, oz, quicksort, sorting
[ Posted by Urban Hafner
Mon, 19 Sep 2005 10:39:50 GMT ]
The problem
Matrix operations. Assume that we represent a matrix as a list of lists of integers, where each internal list gives one row of the matrix. Define functions to do standard matrix operations such as matrix transposition and matrix multiplication.
My solution
Transposition
fun {Transpose Matrix}
{List.foldR Matrix
fun {$ R1 R2} {List.zip R1 R2 fun {$ E1 E2} E1|E2 end} end
for E in Matrix.1 collect:C do {C nil} end}
end
Multiplication
fun {Multiply Matrix1 Matrix2}
if {ColumnCount Matrix1}=={RowCount Matrix2} then
TM2={Transpose Matrix2} in
for Row1 in Matrix1 collect:R do
{R for Row2 in TM2 collect:S do
{S {List.foldL {List.zip Row1 Row2 fun {$ X Y} X*Y end}
fun {$ X Y} X+Y end 0}}
end}
end
else
raise domainError end
end
end
Addition
% Add any combination of matrices and numbers
fun {Add MN1 MN2}
fun {AddMatrices Matrix1 Matrix2}
{List.zip Matrix1 Matrix2
fun {$ R1 R2} {List.zip R1 R2 fun {$ E1 E2} E1+E2 end} end}
end
fun {AddNumberToMatrix Matrix Number}
for Row in Matrix collect:R do
{R {List.map Row fun {$ E} E+Number end}}
end
end
in
case MN1
of _|_ then
case MN2 of _|_ then
if {RowCount MN1}=={RowCount MN2} andthen
{ColumnCount MN1}=={ColumnCount MN2} then
{AddMatrices MN1 MN2}
else
raise differentSizes end
end
else {AddNumberToMatrix MN1 MN2} end
else
case MN2 of _|_ then {AddNumberToMatrix MN2 MN1}
else MN1 + MN2 end
end
end
Auxiliary functions
fun {RowCount Matrix} {List.length Matrix} end
fun {ColumnCount Matrix} {List.length Matrix.1} end
Tags book, CTM, exercise, list, matrix, mozart, oz
[ Posted by Urban Hafner
Mon, 19 Sep 2005 10:16:32 GMT ]
The problem
Complexity of list flattening. Calculate the number of operations needed by the two versions of the Flatten function given in section 3.4.4. With n_ elements and maximal nesting depth _k, what is the worst-case complexity of each version?
My solution
First of all, I’d like to make clear that I’ve never been good at complexity analyses. Secondly, I first forgot to incorporate the k_. So I will first present my solution without the _k and then try to incorporate it. But there I got stuck. So if you have a correct solution please help me out!
- For the
Flatten using lists the worst-case is a list of n_ Elements which are nested into each other. Then the second branch of Flatten will be selected _n times, and there will be 2n calls to Flatten and n_ calls to Append. While the calls to Flatten are of O(_1) the runtime of the Append calls depend on the length of the first argument to Append. In this case the first call takes n steps, the second call (n – 1), and so on. All the Appends together take n * (n – 1) / 2 time. Together the runtime is of O(2n + n * (n – 1) / 2) which is the same as O(n2^).
- Incorporating k_ into this analysis the worst case is a list of _n/k Elements which are lists nested to depth k_. Then there are in the order of _n calls to
Flatten and all the Append calls together take n/k x (2k 4(k-1) 8(k-2) + ...) time. This should be of O(n2^), but I don’t know how to prove it. And I don’t even see it :(
- The analysis of
Flatten with difference lists is much easier. As we have learnt in chapter 3 the append of two difference lists is of O(1_). So the only thing we have to look at are the number of calls to Flatten. As we have seen before in worst-case there are _n calls to Flatten, incorporating k_ there are even less. So it’s clear that this version of Flatten is of O(_n).
Tags book, CTM, difference, execution, list, mozart, oz, time
[ Posted by Urban Hafner
Sat, 17 Sep 2005 14:37:12 GMT ]
The problem
Limitations of difference lists. What goes wrong when trying to append the same difference list more than once?
My solution
Assume you have the two difference lists (a|b|c|X)#X and (d|e|f|Y)#Y. To append them you bind X to (d|e|f|Y). Using the Append function from 3.4.4 what you get is (a|b|c|d|e|f|Y)#Y. But this changes the first difference list into (a|b|c|d|e|f|Y)#(d|e|f|Y).
If you then try to use the first difference list in another append with, say (x|y|Z)#Z you will get a unification error because what you try to do in the Append function is unify (d|e|f|Y) with (x|y|Z). This will of course fail. But in the first append of the difference list the unification was X=(d|e|f|Y) which of course succeeds always as X is an unbound variable.
Tags book, CTM, difference, exercise, list, mozart, oz
[ Posted by Urban Hafner
Thu, 15 Sep 2005 18:55:59 GMT ]
The problem
Checking if something is a list. Section 3.4.3 defines a function LengthL that calculates the number of elements in a nested list. To see whether X is a list or not, LengthL uses the function Leaf defined this way:
fun {Leaf X} case X of _|_ then false else true end end
What happens if we replace this by the following definition?:
fun {Leaf X} X\=(_|_) end
What goes wrong if we use this version of Leaf?
My solution
What happens is that when you call the second definition of Leaf with a non-nil value the computation suspends. I’m also not entirely sure on this one. But what probably happens is this. The two _ create two new unbound variables in the store. This then means that the disentailment check can’t decide and blocks.
Tags book, CTM, exercise, list, mozart, oz
