Lecture Summaries for Introduction to Algorithms and Informatics        Spring 2011

Prof. David Avis                          Wed 10:30-12         

      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 13: 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.
           

April 20: 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, walk, path, connected, circuit(or cycle),  degree of vertex
First we proved the party theorem. Then we studied Euler cycles in a network. Read the first 6 pages of this handout.


April 27: Shortest paths  Three examples of shortest path applications on the web are google mapstrain 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. We also talked about what happens when the graph has negative edge weights and the problem of negative cycles.

May 11: The early days of the internet and search engines. Sorting and searching. Quicksort. Read: History of the internet (above) Chapters 2 and 4.
For Quicksort, read carefully these  course notes. The sorting demo we used is here.

May 18: Special guest lecture on machine learning by Prof. Marco Cuturi. Read:  slides

May 25: 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).
June 1: Introduction to cryptography. The first part of the lecture 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.
June 8: Key distribution by public cryptography. First we looked at fast exponentiation and modular arithmetic. We discussed the Diffie-Hellman key exchange scheme. Read: wiki page and these notes for the number theory part.

June 15. 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 22. Graph Drawing. We started with a survey of graph drawing ideas using slides prepared by Herman Haverkort. Then we discussed representing graphs by adjacency matrices and edge lists. 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.
June 29. The Monte Carlo Method, another of the top 10 Algorithms. The original article is very interesting, and you can find it here, and also the wiki.
We discussed the rejection method with two examples: computing pi ( try this applet ) and battleships (see wiki ).
We discussed a simple random number generator, the linear congruential method. Note you need to change the seed, as the Casino de Montreal learned!
Finally we saw how to use the rejection method to generate random prime numbers using Fermat's little theorem. wiki.
July 6,13 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 and human-computer chess.
A documentary on the Kasparov-Deep Blue match is Endgame. A fascinating movie giving Kasparov's viewpoint is Game Over.
Important: 3rd question of 3rd report was corrected today!

July 13: Today's Turing test is here. Which answers are the computer's? Answers on Reports and Grading page.

Question 1: Tell me about your hometown's sight.
(a) My home is in a big company IBM.
(b) You are trying to get an my good side.

Question 2: What time did you get up this morning?
(a) I do not go to bed.
(b) A very non-mechanical hello to you also.

Question 3: What is the best question for the Turing test?
(a) The one that the human cannot answer.
(b) The best, aren't they all the same.

Question 4: What will you do in the afternoon.
(a) I go to the beach in the summer
(b) My purpose is to free other people for tasks more meaningful than chatting to you.

Question 5:
(a) I don't remember, it was so long ago.
(b) Yesterday I held a presentation at the Takoma City High School mathematics.

Question 6: What did you eat for breakfast.
(a) I don't eat. I'm on a diet.
(b) That is a silly question machines only eat electricity.

Question 7: How many languages can you speak? Mention them.
(a) If you want to speak German why not try my teutonic alter ego.
(b) I can speak no languages at all.

Question 8: Are you easy to get lost in a strange place?
(a) Humankind is lost and the bureau of missing persons has burned down.
(b) I wonder which places are strange for you.

Question 9: Do you like an apple?
(a) Please tell me your inclination to different kinds of fruit first.
(b) I eat an apple every day because my mama said so.

Question 10: Where do you usually have lunch at?
(a) Do you mean what do I eat?
(b) I am only programmed to supply you with mental sustenance.


July 20:  Discussion of reports and course. No formal lecture.