CSE2304 Tutorial #5 semester 1, 2000

A very large integer, too large to fit into a single computer word, can be represented by an array of of its digits in (say) base 10. The high-order digits can be selected by a pointer into the array. Show how the [O(n^log₂(3))-time] multiplication algorithm for large integers, as described by Knuth, can be programmed recursively in C. You do not have to write a full program, but make it clear how you would represent, select and manipulate (parts of) the very large integers in the algorithm.
A Thue sequence (after Axel Thue) is a sequence over {1,2,3}, such that it contains no adjacent repeated substrings.
e.g. 1 2 1 3 1 2 1 is a Thue sequence, but it cannot be extended because 12131211 repeats `1', 12131212 repeats `12' and 12131213 repeats 1213. Nevertheless, Thue sequences of any length do exist. Give a [recursive] algorithm to generate a Thue sequence of arbitrary length `n'.
Draw an undirected, weighted [graph] representing the capital cities of Australia {Adelaide, Brisbane, Canberra, Darwin, Hobart, Melbourne, Perth, Sydney} and the air-routes between them flown by jet aircraft (as far as you know or estimate).
Use
1. Prim's algorithm
2. Kruskal's algorithm
to find a minimum spanning tree of the cities in your graph.