Gonville & Caius College

Preparatory work for Computer Science at Caius

Read chapters 1, 11, 15 and 35 of Dewdney's New Turing Omnibus then answer the following questions.

Chapter 1

1. Write a program using the code style in the chapter to calculate whether a number is a factorial
2. Modify the above program to output all factors up to a number N

Chapter 11

1. Write the programs to insert and delete items from a tree as described in the text. What is the complexity of these two operations in time.
2. Write a program to report how many levels there are in a tree.
3. If data is inserted in a tree what will the tree look like if the data is
   1. random
   2. ascending order
   3. descending order
   Draw out the trees for the data 6,1,8,2,4,9 and for inceasing and decreasing sorts of that list.

Chapter 35

1. Write a program to bubble sort (compare each pair of elements). What is the time and space complexity of this algorithm.
2. Write a program to merge two ordered lists of numbers. What is its time complexity? How might you make use of this merge operation to provide a sorting routine?