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 <math.h>

       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 <stdlib.h>

       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?