CSL 100: Introduction to Computers and Computer Science (3024)
I Semester 201314
Instructor: Subhashis Banerjee and S. ArunKumar
Last modified: Sat Aug 10 09:57:13 IST 2013
Week 3: 1217 Aug 2013
 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?
 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 nonnegative 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
nonnegative integer is divisible by 3
 divisible_by_9 which determines whether a
nonnegative 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 divisibilitychecking algorithms might actually be useful?

 Write an algorithmic definition of fast_power which
computes integer powers of real numbers (x^{m})
so that the number of multiplication operations required is no
more than n where
2^{(n1)} ≤ m ≤ 2^{n}
 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 nonnegative integer powers of nonnegative integers
numbers (k^{m})
so that the number of multiplication operations requidarkgreen is no
more than n where
2^{(n1)} ≤ m ≤ 2^{n}
 Write an algorithmic definition of sum_powers_int
which for any nonnegative integers n and m
computes the sum of the mth 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. ArunKumar
Last modified: Sat Aug 10 11:08:19 IST 2013