CSL 100: Introduction to Computers and Computer Science (3-0-2-4)
I Semester 2013-14
Instructor: Subhashis Banerjee and S. Arun-Kumar
Last modified: Sat Aug 10 09:57:13 IST 2013
Week 3: 12-17 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 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
Last modified: Sat Aug 10 11:08:19 IST 2013