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?