[CSE2304] [progress]

CSE2304, Tutorial #5, semester 1, 2000
Group A: week 11, 15 May...
Group B: week 12, 22 May...

  1. 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(nlog2(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.

  2. 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'.

  3. 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).
    1. Prim's algorithm
    2. Kruskal's algorithm
    to find a minimum spanning tree of the cities in your graph.

© 2000, L. Allison, Comp. Sci. & SWE, Monash University, Australia