Here are some more questoins:
1) A magic square is a 3 x 3 array of numbers with the property that you get the same total if you sum up any row, any column, or even any diagonal. I have a 3 x 3 array of empty boxes, and some coins. I want to put the coins into the boxes in such a way that the total amount of money in each box forms a magic square. I have 5 quarters, 8 dimes, and 13 nickles. a) Give me a way to do this that uses all the coins b) Give me a way to do this using as few coins as possible (but at least one) 2) A square picture is cut into 16 squares and they are shuffled. Write a program to rearrange the 16 squares to get the original big square. 3) The numbers 1 to 9999 (decimal base) were written on a paper. Then the paper was partially eaten by worms. It happened that just those parts of paper with digit "0" were eaten. Consequently the numbers 1200 and 3450 appear as 12 and 345 respectively, whilst the number 6078 appears as two separate numbers 6 and 78. What is the sum of the numbers appearing on the worm-eaten paper? 4) You are given n programs p1 ... pn, each of which take an ASCII string as input. Each program will either output an ACCEPT signal, or a REJECT signal, or will loop forever. You are also given n strings s1 ... sn, each affiliated with a respective program. Your task is to write a meta-program that determines which of the N program-string pairs output an ACCEPT. To assist you in this task, your meta-program is allowed to query an oracle, a black box that takes a program and a string as inputs, and immediately tells you if the computation ACCEPTs, REJECTs, or loops forever. However, you can only query the oracle log n times.
