From:	Patrick Prosser
Sent:	06 November 2010 21:43
To:	zoe_1811@hotmail.com
Cc:	Patrick Prosser
Subject:	Problems, problems, problems ... 20 problems
Attachments:	dictionary.txt


1. Test for primality: read in a number and deliver true if number is prime 
http://en.wikipedia.org/wiki/Primality_test

2. GCD, read two numbers and print out greatest common divisor

3. Set theory: given 2 arrays representing sets implement the following 
functions
     - isMember, subset, union, intersection, setDifference, Carteasian 
product

4. Given an array find largest & smallest element, mean, and standard 
deviation

5. Given two strings S1 and S2 determine if S1 is a substring of S2

6. Given a word S1 and an an array of strings S determine number of times S1 
occurs in S (i.e. frequency of S1 in S)

7. Given an array of strings find most frequently occuring string (uses 6 
above)

8. Given an array of integers sort into non-decreasing order.

9. Find the median of a list of unsorted integers (see 8 above)

10. Given a string S, reverse it.

11.  Using the Havel Hakimi algorithm determine if a given degree sequence is 
graphical, as might be done
       to determine if a molecular equation is legal (naaaw, only kidding :)
       http://en.wikipedia.org/wiki/Degree_%28graph_theory%29

12. Given a string produce all permutations of that string, i.e. all possible 
rearrangements of S (kidding :)

13. Given a set S, produce the power set, i.e. all possible subsets of S 
(naaaw, kidding)

14. Given two strings S1 and S2 find the longest common substring within S1 
and S2, as used in genetics (kidding :)

15. Read in a boolean formula in disjunctive normal form and determine if it 
is true or false. Do this in polynomial time (and win $1,000,000)
       http://en.wikipedia.org/wiki/Boolean_satisfiability_problem
       http://en.wikipedia.org/wiki/Millennium_Prize_Problems

16. Read in a string of zeros and one, i.e. a binary string, and output the 
decimal equivalent

17. Read in two strings S1 and S2 of zeros and ones, representing sets, such 
that S_i[j] = 1 if and only if j is in set S_i
      Implement union, intersection, set difference

18.  Read in a set of n points given as (x,y) coordinates .  Starting at the 
1st point visit all of the points once and once only
       returning to the starting point covering the shortest distance 
       http://en.wikipedia.org/wiki/Travelling_salesman_problem

19. Read in the dictionary (attached). Read in a word from the keyboard and 
test if it is in the dictionary. This is a spelling checker.
      This could help in a crossword puzzle, or scrabble, or writing an essay.

20.  Read in a set of m pairs of the form (i,j), meaning that "i is related to 
j", then read in two numbers p1 and p2 and determine 
       if there is a path from p1 to p2 using the edges. This is similar to 
friends in facebook or finding a path through a maze,
       or finding a path in the internet, etc. Also, we could find the 
shortest path from p1 to p2, i.e. using least edges
--
Patrick Prosser                     tel:  +44 141 330 4934
Computing Science               fax: +44 141 330 4913
University of Glasgow           web: http://www.dcs.gla.ac.uk/~pat/
Glasgow G12 8RZ              email: pat@dcs.gla.ac.uk