Skip to main content

Indian Loop

Recommended Week

Year 1 : Weeks 5 - 10

Originator

James Marshall, Raphael Clifford

Problem 1

This tutorial should only be done after the relevant assignment deadline has passed in Intro to CS, i.e. after 4th week! It presents the solution to the advanced portion of one of the questions, which very few students are likely to have solved by themselves. If any of the members of the tutor group did it, he or she can chair the tutorial, drop the hints, and tell the rest of the group when they've got the right answer, etc.

The problem is to find an efficient way of exponentiation... All students have already implemented the naive recursive and loop methods as part of the assignment. The objective is to find a better than linear complexity exponentiation algorithm that only uses a single loop, uses only basic arithmetic operators (i.e. no exponentiation!) and does not make use of any large storage structures such as arrays. Try to write pseudocode for this algorithm.

Version with answers (available for CS staff only)

Problem 2

Demonstrate that the algorithm developed works. Then show formally that the above algorithm is correct.

Version with answers (available for CS staff only)

Problem 3

Calculate an upper bound on the number of multiplications that the above algorithm will carry out.

Version with answers (available for CS staff only)