Computer Science 269
Introduction to Data Structures
Fall 2000
Assignment 2 Due September 12, 2000
-
Write two algorithms to calculate the sum of the first
n squares, that is:
12 + 22 + ... + n2
One algorithm
should have time complexity O(n) and the other time complexity O(1).
Write these algorithms as two functions
having as parameter the integer n
and as returning the value of the summation.
Write this by hand, using C++ or any other computer language, or even
pseudocode. Hand in a handwritten version, not a typed version or
a computer output.
-
Problem 2.1 page 62 in the textbook.
-
Problem 2.7 page 62 in the textbook.
-
Problem 2.16 page 64 in the textbook.
GCD is the greatest common divisor of two numbers. For example,
gcd(2,6)=2, gcd(35, 56)=7.
Don't forget that:
- gcd(0,a) = a, for every integer a.
- gcd(1,b) = 1, for every integer b.
Write the algorithm as a function having as parameters the two integers
and as returning value the gcd of the two numbers.
-
Problem 2.21 page 65 in the textbook.
-
Problem 2.25 page 65 in the textbook.
The problems must be written by hand, and in your own handwriting and
submitted in class. Do not write them into a computer file and then hand in a
printout, and do not type your homework. Turn it in in class on
September 12, 2000. Late assignments will not be accepted.