Lecture Summaries for Introduction to Algorithms and
Informatics Spring 2010
Prof. David
Avis
Wed
10:30-12
also check:
announcements
reports and grading return to: course home page
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 14: 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. Study the seive of
Eratosthenes: Does it
satisfy Knuth's criteria? Is it efficient?
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. 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 (please
hand in by next week if possible): Using Google maps or something
similar, find a small area of Kyoto near your house and solve the
Chinese postman problem.
Choose about 20 or more streets, with about 6 odd degree intersections
which are not adjacent. (You can simply by deleting a few edges if you
like). Estimate the distances between
the odd degree vertices, and show the minimum route the postman can
take. He should start and end at the same vertex.
April 28: 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. We also talked about what
happens when the graph has negative edge weights and the problem of
negative cycles.
Exercise: (1) Using your
map from April 21, calculate the shortest paths from one vertex
(intersection) to all others using Disjkstra's algorithm. Show the
intermediate steps.
(2) Investigate
the behaviour of Dijkstra's algorithm if some edges in a network have
weight zero.
Either prove it still works or give an example to show it can sometimes
fail.
(3) Study the currency conversion chart here.
Show
precisely
how
to
gain
by
exchanging
money
by
converting
it
to
a
problem
involving
finding
negative
cycles
in a graph. Find all negative
cycles in
the graph for the given chart.
May 5
Holiday Please
do all of the exercise above and hand them in on May 12.
May 12: 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.
Exercise: In Quicksort the
main work is in partitioning the numbers depending on the pivot
(comparison element) x. In
class we used an extra array to do this, but this is not necessary.
In the
course notes this step is done in Algorithm Paritition using no extra space.
(1) Do a complete simulation by hand of Partition using a random set of 20
numbers, all different. Let the pivot be x=8. (Just write down the numbers
1,2,...,20 in at random).
(2) Try to prove why Partition always works. That, is, give some
argument why you believe you will always end up with an array where the
first part has numbers less than x,
and
the
last
part
has
only
numbers
greater
than
x.
May 19: 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).
Exercises:
(1) Selection. Develop fast way to select the greatest k integers from
an unordered set of n integers using ideas from Quicksort. (Hint:
Consider keeping only one of the two sets determined after a random
pivot element is chosen.)
(2) PageRank. Find a small network of 5 or 6 linked web pages. Discard
any extra external links and calculate two iterations of the PageRank
algorithm.
If you know how to program, you may also write a small program to
calculate this.
May 26: 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.
Finally we discussed the efficiency of algorithms with reference to the
sieve of Eratosthenes (notes)
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
June 2. 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. The mathematica program for three
parties is here.
Exercise:
Work through by hand an example for three users, using p=11 and g=2,
showing all details.
June 9. No class. Please work on
your final report
June 16. Modeling and
optimization. We looked at the diet problem and how to model it with
linear programming. We looked at Dantzig's simplex method in three
dimensions. Finally we discussed how to find all solutions satisfying
for which the cost was at most a dollar. Please review these slides and slides
numbered 6-12 and 25-29.
Exercise:
Make a two dimensional linear program with at least 6 constraints
(including non-negativity), and solve it according to the method on
slides 25-29. Also list all vertices.
June 23. 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.
I
will
look
into
whether
Mathematica is available on campus.
June 30. 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 (
applet is contained in the middle of this ) 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.
Exercise: Set up your own
random number generator based on X_{n+1} = 11 X_n + 3 (mod 10)
(a) Choose any seed X_0 and verify that the generator gives a
permutation of {0,1,2,...,9}
(b) Add 10 to each of your numbers, so you have a permutation of
{10,11,...,19}.
(c) Use Fermat's test to find the first prime and the first non-prime
in your permutation. (Call a number prime if it passes 5 Fermat tests
with 5 different values of a)
(Review modular
exponentiation)
July 7. Can machines learn? We
looked at two examples of supervised learning:
(a) the nearest neighbour
rule Read and try the
applet here
(b) Hopfield networks. Read these notes
and try their excellent demo
July 14: 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.
July 21: Informal discussions of
projects, course feedback, and wrap-up.
You may hand in your project at this time, otherwise please send pdf by
email.
Have a good summer break!