Honors Class (Foundations of) Informatics: Algorithmic Adventures

Fall/Winter 2009

[ Schedule | Assignments | Literature | Downloads ]

This course is part of the TU/e Honors Program 2009-2011

Schedule

You are expected to read the material before the lecture.
The assignments shown in the table are due before the lecture.

Classes start at 17:30 sharp in MultiMedia Pavilion MMP (as of 16 Nov 2009; 15 minutes earlier than originally scheduled). Dinner is at 19:15 (or at 19:00, when there is no break during the lectures).

Assignments

Work for assignments can be handed in via peach. You need to register with your student identification number. Deadlines are shown in peach.

1. 1. What is characteristic of science?
   2. For a science of your choice, what role do information and algorithm play in that science?
2. 1. Alan Turing also worked on embryology and code breaking. How do these topics relate to information and algorithms?
   2. For the two puzzles handed out after the first lecture, describe (in natural language) algorithms for solving them.
   3. Consider the Simple Language, which has three statements:

      Statement	Meaning
      inc(x)	Increment variable x by 1.
      dec(x)	Decrement variable x by 1. if x was already zero, nothing happens.
      while x do S od	If variable x is not zero, then execute the statement list S and repeat.

      These programs work on non-negative integer variables denoted by a, b, ...

      The program while x do dec(x) od sets variable x to zero. We abbreviate this program by x := 0.

      Write programs to accomplish the following (see how far you can get):

      Abbreviation	Goal
      x := 1	Set x to one.
      x := n	Set x to some given constant value n. E.g. 3 or 10
      x := x + y	Add to x the value of variable y. (Hint: First try this without preserving the value of y. Then use a temprorary variable; see notes below.)
      x := y	Set x to the value of variable y
      x := x * y	Multiply x by y
      x := x ^ y	Raise x to the power y
      if x = 1 then S fi	if x equals one, then execute statement list S, and if x = 0 do nothing; other values of x need not be considered.
      if x < y then S fi	if x is less than y, then execute statement list S, and otherwise do nothing.

      Notes:
      • Variables that are not explicitly required to change value, should be preserved, i.e., initial and final value should be the same, except for (temporary) variables t0, t1, ... Variables may change in between, as long as at the end the original value is restored (except for temporary variables).
      • In each program, you may use earlier programs through their abbreviation.

3. 1. Study Conway's Game of Life (see literature/tools below, in particular, you should read Ch. 25 of [WW] at least up to page 947).
   2. There is a configuration of 8 gliders that collide to produce a Gosper Glider Gun (a 13 glider version is described in [WW]; try it). Find such an 8-glider configuration (you may search the web) and verify that it works (e.g. with Golly or a Java applet). Submit a description of this pattern and how you found it in peach.

4. Solve the problems about Settling Multiple Debts Efficiently. See how far you can get. Submit your work in peach.

5. Solve the Challenge to write a self-reproducing program for Tom's JavaScript Machine. You are encouraged to submit intermediate results and ideas, as you progress. Do not search the internet for solutions. Every week, you will receive a further hint.

   Note the resemblance of this Challenge to RepRap, the Replicating Rapid-prototyper that can construct its own parts. Also see:

   • One-page summary
   • TechWorld article: RepRap: An open source 3D printer for the masses

6. 1. Describe some useful applications of randomness in real life and science.
   2. Generate, without using any aids or tools (just using your own brain), a random 0-1-sequence of 30 elements.
   Submit your work in peach.

Literature

Course book:

[AA]

Juraj Hromkovic.
Algorithmic Adventures: From Knowledge to Magic.
Springer-Verlag, 2009.
[See this book at Google Books]
[See this book at Amazon.com]
Also see under Downloads

Further reading:

[KRP]

Mark Notturno.
On Popper.
Wadsworth Publishing, 2002.
[See this book at Amazon.com]

This is a short (100 pages) and outstanding book about the philospher Karl Popper. Popper wrote about science (what distinguishes science from other human activities; what is scientific knowledge), but also about society (and the dilemma of personal freedom). For my review, see the Amazon page above.

Wikipedia article about Karl Popper

[GEB]

Douglas R. Hofstadter.
Gödel, Escher, Bach: An Eternal Golden Braid.
Basic Books, 1979, 20th anniversary edition 1999.
[See this book at Amazon.com]
Wikipedia article about this book

From a review:

"Besides being a profound and entertaining meditation on human thought and creativity, this book looks at the surprising points of contact between the music of Bach, the artwork of Escher, and the mathematics of Gödel. It also looks at the prospects for computers and artificial intelligence (AI) for mimicking human thought. For the general reader and the computer techie alike, this book still sets a standard for thinking about the future of computers and their relation to the way we think."

[AMT]

Andrew Hodges.
Turing: a natural philosopher.
Routledge, 1999.
[See this book at Amazon.com]

A short (some 60 pages) but complete biography of Alan Turing, by the author who earlier wrote a more extensive biography, titled Alan Turing: The Enigma (an ambiguous title, alluding to both the German Enigma Cipher that Alan Turing helped break, and the mysterious nature of his person). Unfortunately, it does not mention Turing's work on embryology, other than listing a paper he wrote in 1952, titled ''On the Chemical Basis of Morphogenesis'').

Alan M. Turing (in Wikipedia)

Turing Machine (in Wikipedia)

[WW]

Ch.25, "What is Life?", pp.927-961 from:
Winning Ways for Your Mathematical Plays, Volume 4.
by E.R. Berlekamp, J.H. Conway, R.K. Guy.
[See this book at Google Books]
[See this book at Amazon.com]

This chapter is about Conway's Game of Life and explains why this "game" is universal. See Downloads.

[GoL] Game of Life and other (Cellular) Automata

1. Wikipedia article about Conway's Game of Life
2. Conway's Game of Life at ExperimentGarden: a brief introduction
3. What is the Game of Life?: another brief introduction, with runnable examples through an embedded Java applet (no need to install software)
4. Golly: a program to explore Conway's Game of Life on various platforms (Linux, Mac OS X, Windows); includes many complex patterns
5. Cellular Automaton (Wikipedia article); especially, see the Wolfram classification with Rule 30 and Rule 110 as interesting examples

[QC] Recent News about Quantum Computing

1. Super-Fast Quantum Computer Gets Ever Closer: Quantum Particles Pinned Down, in ScienceDaily, 9-Nov-2009:

   "Researchers at the Kavli Institute for Nanosciences at Delft University of Technology, have succeeded in getting hold of the environment of a quantum particle. This allows them to exercise greater control over a single electron, and brings the team of researchers, led by Vidi winner and FOM workgroup leader Lieven Vandersypen, a step closer still to the super-fast quantum computer."

2. NIST Demonstrates 'Universal' Probrammable Quantum Processor, NIST News Release, 16-Nov-2009:

   "Physicists at the National Institute of Standards and Technology (NIST) have demonstrated the first "universal" programmable quantum information processor able to run any program allowed by quantum mechanics---the rules governing the submicroscopic world---using two quantum bits (qubits) of information. The processor could be a module in a future quantum computer, which theoretically could solve some important problems that are intractable today."

3. First Programmable Quantum Computer Created, ScienceNews, 19-Dec-2009, 176(13):13 by Laura Sanders
4. Quantum age edges closer, The Univ. of New South Wales, Australia, 05-Jan-2010
5. Princeton scientists make a leap in quantum computing, News at Princeton, 08-Apr-2010
6. Toshiba invention brings quantum computing closer (ELED: Entangled Light Emitting Diode), Reuters, Ben Hirschler, 02-Jun-2010
7. World first for quantum memory storage ANU News, 24-06-2010
8. 'Quantum Computer' a Stage Closer With Silicon Breakthrough, UCL News, 24-06-2010

[MC] (Recent) News about (Bio)Molecular (DNA) Computing

1. Researchers make significant advances in molecular computing, University of Kent, 10-Dec-2009
2. DNA computer 'ansers questions', BBC News, 05-Aug-2009
3. Future directions in computing: DNA Computing, BBC News, 13 Nov 2007
4. How DNA Computers Will Work, How Stuff Works
5. DNA logic gates herald injectable computers, New Scientist, 02 June 2010

[R] Randomness

1. Wikipedia article on Randomness
2. At the National Institute of Standards and Technology:
   1. Random Number Generation in the Cryptographic Toolkit, which also refers you to
   2. Random Number Generation and Testing, which also offers testing software and publications like the following:
   3. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, NIST publication SP 800-22rev1, August 2008
   4. Statistical Testing of Random Number Generators by Juan Soto (NIST), Proceedings of the 22nd National Information Systems Security Conference, October 1999. (Overview and introduction to preceding publication)
3. 'True' Randomness
   1. RANDOM.ORG: Statistical Analysis (in particular, see the Visual Analysis of the PHP rand() function)
   
4. Coin Tossing:
   1. Dynamical Bias in the Coin Toss by P. Diaconis, S. Holmes, R. Montgomery, SIAM Review 49(2):211-235 (2007, technical paper!)
   2. The Coin Flip: A Fundamentally Unfair Proposition? by James Devlin (29 March 2009; simplified exposition)
5. Gregory Chaitin. Exploring Randomness. Springer 2001.
   From the point of view of Algorithmic Information Theory.
   [See this book at Google Books]
6. W.A. Wagenaar. ''Generation of random sequences by human subjects: a critical survey of literature''. Psychological Bulletin, 77(1):65-72 (1972).
7. Resources concerning Random Number Generators
8. Truly random numbers, AlphaGalileo, 22-Feb-2010.

[SR] Self-Reproduction

1. Self-reproduction challenge for Tom's JavaScript Machine
2. Wikipedia article about Quines, that is, about self-reproducing programs
3. David Madore's Discussion of Quines, which also provides a theoretical background on the universality of self-reproduction
4. RepRap, the Replicating Rapid-prototyper, an open-source 3D-printer that can construct its own parts
5. Richard Dawkins. The Blind Watchmaker: Why the evidence of evolution reveals a universe without design. 1st Ed., W.W. Norton, 1986 (book, various editions)
   Also see under Downloads
6. Gregory Chaitin about Metabiology: "to have a mathematical understanding of basic biological concepts and to be able to prove that life must evolve in very general circumstances."
7. Scientist Creates Virtual Evolution by Sharon Hill, Canwest News Service, 11-Dec-2009.

[C] (Recent) News about Cryptography

1. Security Researchers Uncover SSL Vulnerability, by Sophie Curtis, eWeek Europe, 05-Nov-2009
2. How you can build an eavesdropper for a quantum cryptosystem, at 26th Chaos Communication Congress, 27-Dec-2009
3. Cellphone Encryption Code Is Divulged, by Kevin J. O'Brien, New York Times, 28-Dec-2009.
   Explains about the recent practical breaking of GSM encryption. Theoretically, it was already broken longer ago.
4. Q&A: Researcher Karsten Nohl on mobile eavesdropping, by Elinor Mills, CNet News, 01-Jan-2010.