Design and Analysis of Information
SystemsTopics in Advanced TheoreticalComputer ScienceAutumn-Winter 2011

Purpose of the lecture• Design of information systems– Statistics– Database management and query– Internet search– Pattern recognition– Logic problems– Computer graphics• Mathematical Modeling and Algorithm Design– ART and also FUN!

Text Books• Programming Pearls– Jon Bentley 2009 (2nd edition), Addison-Wesley $40• The art of computer programming vol 1-3– (Donald Knuth) 1997 (3rd edition), Addison-Wesley• Mathematical Puzzles– Peter Winkler, 2004, A.K. Peters Ltd.

• The Art of Mathematics– Bela Bollobas, 2006, Cambridge Press,

Day 1Searching, Searching, and SearchingAha Algorithms(from Programming Pearls)• I am thinking of a natural number in [1,1000]– I write down on a paper• You must find it– You can ask questions (question should be short)– I answer yes or no• Your task: write down your strategy• Winner: use least number of questions

Finding missing number• We have different 32bit numbers in a sequential
array of length 4000,000,000– Find a missing number, using only one-word memory• One word can contain 64 bits

– If you are allowed to use 1M byte memory, what you willdo?

• We have 50 cards among 52– In one trial, all cards are shown in a random order– Find a missing card with least number of trials

Debugging a program• I have a computer program with 1000 lines ofcodes, but it has a bug in a line, and aborts.
• Find out the bug– You can place a stopper at any line and run theprogram. The program runs correctly if there is nobug until then.

Computing power• Write a fast code to compute the t-th powerof a given natural number n.
• Write a fast code to compute the t-th powerof n modulo p.
– If you know p is prime, and p is much smaller
than t, can you do better? (say, p = 31 and t =10000)

Searching in the internet• We have 1,000,000 documents each contains
10,000 characters (in alphabet).
– Given any keyword (say, “Tokuyama”), find all
documents containing it– Given any string (say, “keshi Tokuy”), find all
documents containing it• You can preprocess the data
– What is preprocess? Make the data well-ordered
so that we can find necessary information easily.

We may encounter hard problems..
• Does the following program terminates for every integer x ?
(Bentley, programming pearls, exercise of Chap 4)
while x > 1 do
if even(n) then x = x/2
else x = 3x + 1• If x = 10,– 10 →5→16→8→4→2→１• If x = 9,
– 9→28→14→7→22→11→34→17→52→26→13→40→20→10→

Hint by Jon Bentley: If you solve this problem, run to the nearest mathematics
department and ask for a Ph. D.

Engineers should be flexible• An exercise in “Programming Pearls”– NASA needed for writing implements that work
well in the extreme environment of space. Amillion dollar project research developed a “spacepen”. According to the legend, how did theSoviets solve the same problem?

• I could not imagine the solution, but probably
you can.

QUIZES? ALGORITHMS!

Exchange two strings• Given an array of length n = ab, which isconcatenation of two strings a and b• Change the array to n’ = ba, but we can only
use additional one word memory– a = 0302040552, b = 02035530219852– n = 030204055202035530219852– n’ =020355302198520302040552• Write a smart programUSE OF RANDOMNES

Data checking• We have n data {1,2,…,n} in a random order– n is huge, and read from external disk
– We suspect that one data is modified by theenemy. Can you check it by using single word
additional memory?

• Can we check if we do not know how many
data are modified?

Use of randomness• Given 10000 nuts and 10000 bolts forming
10000 matching pairs. We can compare apair of bolts (or nuts) and see which is larger.
How to find one matching pair quickly?

Birthday trick• If we have 20 students in a class, what is theprobability that there is a pair of students withthe same birthday?

Danger of randomness• Lets make a deal! (host: Monty Hall)– There are three doors , behind one of whichcontains a gorgeous car.
– You pick one of them
– The host comedian opens one of the unselecteddoors, which is open.
– Now, “change or remain”.

• Too easy? Then….
Marilyn vos Savant

INVARIANTS

Generalized Tick Tack Toe• Let X = {S1,S2,…S7} where each Si is a set with 3elements (some elements may be shared bysome sets)• Alice and Bob color elements in turn. Alice colors
red, and Bob colors blue (each element can becolored only once).
• If Alice makes a set with all red elements, Alicewins, otherwise Bob wins.
• If Bob starts, prove that Bob always wins.
• If Alice starts, show that Alice may win (itdepends on X)

Black and white beans• We have 25 white beans and 20 black beans ina bin.
• We pick two beans randomly.
– If they are same color, remove them, and throw inan extra black bean.
– If they are same colors, return the white bean,
and remove the black bean

• What is the probability that the last remaining
bean is white?

Clock Solitaire game• We divide 52 playing cards into 13 card decks,
each contains 4 cards. We number the deck to 1
to 13.
• Starting the deck of number 13 we open cards,
where we next open the deck indicated by thecard.
– E.g., if we find 4 of harts, we next open the deck 4.
– If the deck is empty, we loose• We win if all cards are open
• What is the probability of win.