Lecture Summaries and Exercises for Computer Science Fundamentals           Autumn 2011

Prof. David Avis                          Tohoku University          Nov 9,10,16,17

    Students should hand in exercises from 4 of the lectures or discussion sessions by Dec 22, 2011 at the Tokuyama lab 8F

   You are encouraged to discuss the exercises with other students, but you must write up your own solutions (no copying!)

2010 web page.

Here is some general material to start off with:

The Machine That Changed The World", developed and distributed by WGBH (PBS) and the British Broadcasting Company (BBC).


Nov 9_1 : History of algorithms. Knuth's 5 properties for an algorithm.  Euclid's gcd algorithm: statement, proof of correctness, number of steps required. Lecture notes will be posted. To see just how many algorithms are out there, have a glance at this huge list.
              Read: History of Algorithms and Algorithmics.   The seive of Eratosthenes      notes.
  Exercise. :  Choose a simple algorithm you know.
(If you don't know any choose one from the huge list above . Look up the details of the algorithm using wiki or similar source.)
(a) State the algorithm briefly and show it satisfies Knuth's 5 properties. (No need to prove my property 6 - correctness !)
(b) Give a small example of how it works.
Be sure to state all reference material you use, eg. URL for wiki, text book name etc.
Nov 9_2: Graphs as models. There are hundred's of definitions in graph theory, but we will only use a few of them.
Use this link as a dictionary. Be sure to go to the end of the link to the section "To be merged" for an essential basic list.
Key terms today: graph, vertex(or node), edge, path, connected, (connected) component, circuit(or cycle), matching, degree of vertex
We studied Euler paths and  circuits and the Chinese postman problem. Read the previous two links carefully. You may skip "Counting Eulerian circuits" in the first article.
  Exercise:  Draw a graph of the streets near where you live, where the vertices are intersections and the edges are roads. Use at least 10  vertices.
Estimate very roughly the length of each block (ie. road length between intersections) in meters. Eg. 100m, 150m etc.
Your goal is to walk along each street at least once with minimum total distance and end back at the starting point.
Ie. you solve the Chinese postman problem.
You may form teams of two to do this exercise. If you want to have some fun, buy a pedometer （万歩計）at the 100 yen shop!
Nov 10_1: Introduction to cryptography. The first part of the lecture is from Applied Cryptography by B Schneier. Read the first 5 pages of Chapter one here
We  discussed Caesar's cipher, and its improvement, the Vigenere cipher.
Basic ideas about public key cryptography. BBC article on Google and Bletchley park.
Exercise:
Discuss whether regular email satisfies the conditions that a normal letter does:  (a) Confidentiality (b) Authenticity (c) Integrity (d) Non-repudiation and (e) No duplication
Nov 10-2. Discussion. An experiment in key distribution using Merkle's puzzle scheme based on the Sudoku game.
Exercise:
The solution to our games was a string of 10 integers, row by row from the puzzle solution.
We let x be the sum of the first five and y be the sum of the second five. We computed the signature 3x+y to represent the solution.
(a) Show that the signature can often be computed without computing the complete sudoku solution. Illustrate with two example games you construct.
Hint: First show that a signature which is the sum of all ten solution numbers can be computed without solving the puzzle at all!
(b) Give some suggestions for a stronger signature function, that requires the puzzle to  be solved in order to compute it.
The function should be computable by hand and ideally have a maximum value of 200 or so.
Nov 16_1: Graph Drawing. Planar graphs, Euler's theorem and a proof of Fary's theorem that every planar graph can be drawn with straight lines only. wiki
We studied the spring embedding and spring electrical embedding algorithms developed by Peter Eades and others, using Mathematica.
Read this excellent survey. The Mathematica note book I used is here. The movie is here.
Exercises:  Show that the Petersen graph is not planar by showing it has either a subdivision of K_5 or a subdivision of K_3,3 as a subgraph.
(A subdivision of a graph is formed by inserting vertices into any of its edges)
Nov 16_2:  We began with The History of the Internet by Richard Griffiths. We covered how web pages are ranked by search engines such as Google, and its famous PageRank algorithm. The relationship between PageRank and random walks was discussed. A nice simulation for dimension 2 is here. The C program to compute the PageRank of the small example of these course pages is here.  A website  to get sample PageRanks is here. Read: wiki page for PageRank and for random walk. (Skip the part on Weiner processes).
Exercises:  Construct a small web graph with 5 or 6 nodes and compute the PageRank of each node. Either modify the C-code given above, or compute it exactly using a system of equations. Use a random jump probability of  α = 0.15.
Nov 17_1 : Can machines think? The Turing test and Loebner prize. Read: Turing's historic 1950 paper. Try the Turing test yourself with the 2008 winner Elbot . A sample transcript is here.   CAPTCHA is a very practical use of a Turing type test.
We also looked at game trees using the game of Nim as an example, see Luc Devroye's notes, and human-computer chess.
A documentary on the Kasparov-Deep Blue match is Endgame. A fascinating movie giving Kasparov's viewpoint is Game Over.
Exercise:   TBA

Nov 17_2: We did an experiment using a version of the Turing test.

Exercise: Read the first part of Turing's paper where he describes his experiment. Discuss how our experiment differs from what he proposed. Which test do you think is better in deciding whether a machine can think?
Answer should be 1-2 pages.