ISE 390 -- Programming Challenges -- Week 5 Notes
This Weeks Goals:
To review the basic numerical summation and
counting formulas.
To discuss math library functions
To introduce this weeks problems on arithmetic and divisibility.
(hint: brains can count for more than brawn)
Topic for Discussion:
Should we do the problems in groups instead of individually?
Do we send a team to: The Consortium for Computing
in Small Colleges (Northeast Region) will hold an undergraduate programming
contest as part of its 2001 conference at Middlebury College in
Middlebury, Vermont. The contest will be held on Friday, April 20,
from 9:00am to 12:30pm. It is open to teams of up to 3 undergraduate
students from any institution (not just small colleges). The contest
languages will be C, C++, and Java. Teams may use any or all of the
languages to solve the set of problems given at the start of the
contest. The rules will be similar to those used at the ACM Northeast
Regional competition (see http://cs.wsc.ma.edu/acm/rules.html). The
prizes, sponsored by Microsoft Corporation, are $300 for the 1st place
team, $180 for the 2nd place team, and $120 for the 3rd place team.
The contest registration fee is $90 per team and includes conference
registration for all participants.
Programming Ideas:
The standard C/C++ math library has several useful functions:
#include
double sqrt(double x);
double exp(double x);
double log(double x);
double log10(double x);
double pow(double x, double y);
double floor(double x);
double ceil (double x);
double fabs(double x);
double cos(double x);
SEE ALSO
acos(3), asin(3), atan(3), atan2(3), sin(3), tan(3)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The exp() function returns the value of e (the base of
natural logarithms) raised to the power of x.
The log() function returns the natural logarithm of x.
The log10() function returns the base-10 logarithm of x.
The pow() function returns the value of x raised to the
power of y.
The floor() function rounds x downwards to the nearest
integer, returning that value as a double.
The ceil() function rounds x upwards to the nearest inte
ger, returning that value as a double.
The fabs() function returns the absolute value of the
floating-point number x.
The cos() function returns a value between -1 and 1.
The standard library has other mathematical functions:
#include
int abs(int j);
int rand(void);
void srand(unsigned int seed);
The abs() function computes the absolute value of the
integer argument j.
The rand() function returns a pseudo-random integer
between 0 and RAND_MAX.
The srand() function sets its argument as the seed for a
new sequence of pseudo-random integers to be returned by
rand(). These sequences are repeatable by calling srand()
with the same seed value.
In Numerical Recipes in C: The Art of Scientific Computing
(William H. Press, Brian P. Flannery, Saul A. Teukolsky,
William T. Vetterling; New York: Cambridge University
Press, 1990 (1st ed, p. 207)), the following comments are
made:
"If you want to generate a random integer between 1
and 10, you should always do it by
j=1+(int) (10.0*rand()/(RAND_MAX+1.0));
and never by anything resembling
j=1+((int) (1000000.0*rand()) % 10);
(which uses lower-order bits)."
Assigned Problems:
138 -- Find pairs of integer ranges over which summations are equal.
Is efficiency an issue?
200 -- Sort the symbols of an alphabet according to given constraints.
338 -- Implement schoolhouse multiplication, with proper spacing.
343 -- Base conversion and equality. Why do programmers think Christmas
is Halloween?
344 -- Decimal to Roman number conversion.
369 -- How can we compute binomial coefficients without large intermediate
sums? This has at least two clever solutions.
Problems for Discussion
-----------------------
Basic counting formulas
Prove that the sum of 1 to n is n(n+1)/2.
Prove that the sum of 1^2 to n^2 is > c n^3 and < d n^3.
Generalize to any power.,
Know that the sum of any geometric series converges if the
exponent < 1
Know that the sum of 1/i as i goes from 1 to n is the nth
Harmonic number, and grows like the log of n.
The Fundamental theorem of Arithmetic
Despite the impressive title, all it states is that each
integer can be expressed only one way as the product of
primes. This simple fact can be very useful.
Puzzle: how many divisors does an integer have (2^n, n!, 10000).
Which has the largest number? Which has the smallest number? What
about sums of divisors?