Lecture Summaries and Exercises for Computer Science
Fundamentals
Autumn
2010
Prof. David
Avis
Tohoku
University
Nov 24,25 Dec
1,2
Students should hand in exercises from 4 of the
lectures or discussion sessions by Dec 28, 2010 at the Tokuyama lab 8F
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
Nov 24_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.
Read:
History
of
Algorithms
and
Algorithmics. notes.
Exercise. Study the seive of
Eratosthenes: 1. Does it
satisfy Knuth's criteria? 2. Is it efficient? To answer the
second question you may assume that the number of primes less than an
integer n is about n/logn.
Nov 24_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 Using
Google maps or something
similar, find a very
small area of Sendai near your house and solve the
Chinese postman problem.
Choose at most 20 streets, with 6 odd degree intersections
which are not adjacent. (You can simply by deleting a few edges if you
like). Roughly
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. To find the minimum
weight matching, evaluate all possibilities.
Nov 25_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: Draw the complete
Nim tree for a 4 pile game with the starting position 2,2,1,1. Now by
ordering the moves in a clever way, try to draw the smallest tree
possible that shows that player one can always win.
Nov 25_2: We did an experiment
using a version of the Turing test. Our questions and answers are here
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.
Dec 1_1: 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.
Dec 1_2: 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.
Dec 2_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
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
Dec 2-2. Discussion. An
experiment in key distribution.