Lecture Summaries for Introduction to Algorithms and Informatics        Spring 2013

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 10: 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: (a) 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.  
(b) As pointed out in class, the proof of Claim 1of the notes  is not quite complete.  In fact it shows gcd(a,b) <= gcd(b,r). Prove that gcd(b,r) <= gcd(a,b).
April 17　April 20: 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 24: 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 1:  News Flash: Although there is no formal class, we will show the film in class at the usual class time if you would like to watch it there. Informal discussion to follow . Please watch 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.
May 8: Follows Monday schedule. No class.
May 15: First report due! Guest lecture by David Rappaport on data compression. slides
Exercise: This exercise is to compare the compression rate of two different languages.
1. Choose two languages (whether you understand them or not does not matter!) that can be written in a non-kanji alphabet.
2. Get some basic text of at least a few hundred words from the internet in both languages. Discard all punctuation, numbers, special characters.
3. Choose either the Shannon-Fano or Huffman method and compute an encoding. Estimate the compression rate compared to a 5-bit coding for an alphabet of 17-32 letters, 6-bit coding for 33-64 letters.
Note: (a) if the language uses kanji choose a non-kanji text: eg. romaji or hiragana for Japanese, pinyin for Chinese
(b) if the language uses accents you may either discard the accents or treat them as different letters ( eg French e,é,è,ê could be all different)
(c) you may compute the frequency counts by hand or by writing a small program
May 22: 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: Test how much the entropy of English (or another language) increases when you encrypt it with a Vigenere cipher.
1. Get some basic text (or use the text from May 15 exercise)
2. Encrypt it using a Vigenere cipher of key length 1 (Caesar cipher), length 3 and length 10. (Generate a random key)
3. Use Shannon-Fano or Huffman to compute an encoding of the three cipher texts reporting how many bits are needed in each case (should increase !)
You may do by hand or write a small program (recommended)
May 29: . 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 .
No exercise.
June 5: 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 exercise in the notes. Explain why the signature (= identifier I) we used in class is better than the one in the notes. Can you find any weakness of the one we used in class?
(If you were not there we used I=k1*k2 + k3*k4+k5*k6+k7*k8+k9*k10)
June 12: Modelling 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.
No Exercise.
June 19. Second report due! Based on lectures given on May 15, May 22, June 5
 In pursuit of the traveling salesman.  Special guest lecture by Bill Cook:
His acclaimed book on the travelling salesman problem is available on  amazon and if you bring a copy to class, he will likely sign it for you!

June 26.  The early days of the internet and search engines. Read: History of the internet (above) Chapters 2 and 4.We also 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).
Exercises: (a) Construct a small directed graph with  5 nodes and 12-15 edges 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.
(b) Choose the node X with the least number of out-going edges. Consider in turn adding out-going edges from X to nodes to which it is not already linked. Which new links increase the page rank of X and which decrease its page rank?
July 3. 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: Study the alpha-beta algorithm given in  Luc Devroye's course notes. Run it by hand simulation on the tree in Figure 4, however first randomly permute the leaf values 1,2,...,9.
Show the value of returned by each recursive call to the function alphabeta.
July 10: The Turing test and Loebner prize. Read: Turing's historic 1950 paper. Try the Turing test yourself with  Elbot or Goostman.    CAPTCHA is a very practical use of a Turing type test.
We did a Turing-type test in class between Elbot, Goostman, and David. There were 8 questions and the answers from E, G and D were given in random order. The students had to decide which answer came from who. The questions are here and the results are here. In the results, each question is a row and each student is a column. One point was given for each correct answer for a maximum of 24 points per student. At the left is the total correct score for D,G,E. At the right is the correct answer for each question and at the bottom the total score for each student.
Exercise: First read Turing's original 1950 paper.
Then write a short essay (about one page) that compares the test done in class with Turing's original idea. Points you may wish to address:
1. Did either computer win the Turing test?
2. If the students guessed answers at random would the scores be significantly different?
3. How does having two computers and one human change the situation?
4. How else does the test setup differ from Turing's?
5. What would be a better way to organize the test?
News flash: Negobot, a "14 year old Lolita" tries to catch sex offenders. If she does, does she pass the Turing test?  Discuss it in your essay if you like !
July 17: Third report due! Based on exercises from June 19, 26 July 3, 10
Hand in and pick up reports. Discussion on previous report questions with Long Cheng.
Please complete course evaluation form!
This is the final class. Hope you learned something and enjoyed it!