# CSL 100: Introduction to Computers and Computer Science (3-0-2-4)

### Since Thursday 15 Aug is a holiday, the lab for Thursday groups will be held on Saturday 17 Aug 2013.

1. Consider an obvious extension of the definition of GCD to all integers. Write a new algorithmic definition of the gcd function to all integers. Program it in SML and test it out.
Question What is a suitable collection of tests which will convince anybody that your program works correctly?

2. Find out when two natural numbers are relatively prime. Use the gcd algorithm given in the last week's labs to determine whether a pair of numbers is relatively prime.
Question Can two negative integers be relatively prime to each other?

• Give an algorithmic definition of a function sum_digits which finds the sum of the digits of a non-negative integer.
• Give a proof of correctness of your algorithm.
• Program sum_digits in SML and test it out.
Question How will you extend your function for negative integers?

• Use the function sum_digits to give algorithmic definitions of the following functions
• divisible_by_3 which determines whether a non-negative integer is divisible by 3
• divisible_by_9 which determines whether a non-negative integer is divisible by 9
• Give a proof of correctness of your algorithm.
• Program sum_digits in SML and test it out.
Question Is it not easier to check divisibility by 3 and 9 simply by actually dividing the numbers by 3 and 9 respectively?Can you think of a situation where your divisibility-checking algorithms might actually be useful?

• Write an algorithmic definition of fast_power which computes integer powers of real numbers (xm) so that the number of multiplication operations required is no more than n where 2(n-1) ≤ m ≤ 2n
• Prove the correctness of your algorithm
• Program fast_power in SML and test it out
Question Here again design a collection of tests which gives you confidence and may convince your TA that your program works correctly.

• Write an algorithmic definition of fast_power_int which computes non-negative integer powers of non-negative integers numbers (km) so that the number of multiplication operations requidarkgreen is no more than n where 2(n-1) ≤ m ≤ 2n
• Write an algorithmic definition of sum_powers_int which for any non-negative integers n and m computes the sum of the m-th powers of all positive integers from 1 to n.
• Prove the correctness of your algorithm sum_powers_int (assuming the correctness of fast_power_int).
• Program fast_power_int in SML and test it out. Program sum_powers_int and test it out.
Question Here again design a collection of tests which gives you confidence and may convince your TA that your program works correctly .

S. Arun-Kumar