Lecture Summaries for Introduction to Algorithms and Informatics        Spring 2012

Prof. David Avis                          Wed 10:30-12         Tentative schedule

      also check:      reports and grading    return to:  course home page
Check this page often. All reading material for the course and announcements are here.

Here is some general material to start off with:

History of Algorithms and Algorithmics developed by Scriptol.

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

The History of the Internet by Richard Griffiths

Top 10 Algorithms of the 20th Century from SIAM News, Vol 33, Number 4.
April 11: 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.
              Read: History of Algorithms and Algorithmics.  notes.
    Exercise: Choose any algorithm that you know (not too complicated ! ) and write it down concisely. Show that it satisfies the 6 conditions given in page 1 of the notes.       
April 18:　April 21: 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. Just look up the terms you need, do not try to memorize the list!
Key terms today: graph, vertex(or node), edge,  path, connected, circuit(or cycle),  degree of vertex
We studied Euler cycles in a network. Read this handout.
  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 with exactly 6 odd degree 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!
April 25: Shortest paths  Three examples of shortest path applications on the web are google maps,  train schedules, and the collaboration graph, which is part of the Erdos Number project.
(The collaboration graph is at http://www.ams.org/mathscinet/collaborationDistance.html , but this URL does not seem to work inside Kyoto Univ. system)
              We studied Dijsksta's algorithm which works when all the edge weights are non-negative. Here is the demo and slides.
Exercise: Consider a directed network with positive weights on both the edges and the vertices. The cost of a path from s to t is the sum of the edge weights and the vertex weights along the path, including s but not including t. Show how to use Disjkstra's algorithm to solve this problem.
An example of this situation is a railway network where you pay a fixed cost + a variable cost depending on distance. Vertices would be stations where you change railway companies  (eg. San-jo) and have to pay a new fixed charge. Make an example of this type with at least 7 transfer stations (vertices) and compute the shortest cost routes from one vertex to all the others. You can use real data obtained from train schedules, or just make up your own data.
May 2: No class
May 9: We watched the film sorting out sorting that covered 9 sorting algorithms, and also discussed merge sort, randomization, worst case analysis and average case analysis.
For Quicksort, read carefully these course notes.
Exercise: (modified May 15)
In the film it stated that (1) bubble sort and shaker sort use exactly the same data movements (in a different order) and (2) shaker sort does fewer comparisons.
You can find the code for both algorithms here.    Are these statements true or false?
First generate a small array of random integers (at least 6) and try to verify these statements directly by simulating the two algorithms by hand (or by adding a trace and executing the code.)
Then give a formal proof or counterexample for each statement.
May 16: First report due! The early days of the internet and search engines. Read: History of the internet (above) Chapters 2 and 4.
No exercise.
May 23: We covered how web pages are ranked by search engines such as Google. This includes "on page information" related to keywords in the search multiplied by PageRank, which estimates how important a page is. 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.  The website we used to get sample PageRanks is here. Read: wiki page for PageRank and for random walk. (Skip the part on Weiner processes). The slides of the ISAAC talk are here.
Exercises: (a) Construct a small undirected graph with at least 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. The graph should have at least 4 pairs of vertices not connected by an edge.
(b) Consider adding edges one by one to pairs of vertices that are not connected by an edge. An edge is added only if the PageRank of each end point increases.
Which graph results from this process?
May 30: Introduction to communication and cryptography. The first part of the lecture was this movie. The second part is from Applied Cryptography by B Schneier. Read the first 6 pages of Chapter one here   (scroll past the table of contents, etc.) We  discussed Caesar's cipher, and its improvement, the Vigenere cipher.
Exercise: The movie explained that English is quite a redundant language. For example native speakers can understand most of this sentence with half the words deleted:
  Student xxxxx and xxxx Quebec xxxx appear xxxx be xxxx the verge xxxx agreement  xxxx resolving an xxxxx 15-week conflict xxxx tuition xxxx hikes.
（See first paragraph of article ) However if English is not your native language this may be difficult.
In this exercise I would like you to empirically test the redundancy of your own language. (If you are an English native speaker, use English!)
(a) Find some simple texts of a couple of paragraphs or so from the internet.
(b) Randomly delete a subset of the words with probability p. Find the rough value of p for which the text can still be more or less understood. (If possible try this with a friend who speaks the same language) Eg. for Japanese これ は 日本語 の 新聞 です I would count 6 words, so deleting words 2 and 5 gives これ *** 日本語 の *** です
(c) Randomly delete a subset of the characters of the string (eg. for Japanese これは日本語の新聞です　deleting characters 2,6,8 gives こ*は日本*の*聞です)
Yes, this exercise is a bit vague, but see what you can do with it!
June 6: Key distribution by public cryptography. We discussed Merkle puzzles, the first method of public key distribution. Read: Merkle project proposal,    wiki
We discussed an implementation of Merkle puzzles using Sudoku, see notes, and did an experiment using these Sudoku puzzles.
Exercise: Do the exercises in the notes.
June 13. Modeling and optimization. As a first representative problem we saw that the sushi problem can be formulated as an integer linear program. We looked at the diet problem and how to model it with linear programming.  Finally we discussed how to find all solutions satisfying for which the cost was at most a dollar. Please review these slides.
June 20. Second report due!
Special guest lecture by Bill Cook:  In pursuit of the traveling salesman
His acclaimed book is available on  amazon and if you bring a copy to class, he will likely sign it for you!
June 27. Special guest lecture on graph drawing by Peter Eades. Planar graphs, Euler's theorem and a proof of Fary's theorem that every planar graph can be drawn with straight lines only. We studied Tutte's 'amazing' theorem  and  spring embedding  algorithms developed by Peter. slides The movie is here.
BTW, all graphs on the blackboard are different drawings of the Petersen graph .
Exercises:  Complete the proof of Fary's theorem given on slide 45 by showing
(a) In every planar graph there are at least 4 nodes of degree at most 5
(b) In every simple (ie non-crossing) polygon  in the plane with 5 vertices one can find a point in the interior of the polygon that can be connected by straight lines to all 5 vertices without crossing any edge of the polygon.
July 4. Can machines think? We looked at game trees and human-computer chess. Luc Devroye's course notes on game trees.
A documentary on the Kasparov-Deep Blue match is Endgame. A fascinating movie giving Kasparov's viewpoint is Game Over.
Exercise: Run by hand simulation the alpha-beta algorithm given in the wiki pseudocode on the game tree in Figure 1 of Luc Devroye's course notes.
Show the value of returned by each recursive call to the function alphabeta.
Bonus question: Luc Devroye's notes contain various misprints, especially in the alpha-beta algorithm. Correct as many of these as you can and submit a printed version in class and email the corrected html file to me. We will post the best solution.

July 11 Follows the Monday schedule, so there is no lecture.
July 18: Third report due! 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.
No Exercise.