Reports and Grading
Introduction to Algorithms and
Informatics
Spring 2011
return to: course home page
1. The course grade is based on 3
reports with due dates: Mon. May
16, Mon. June 13, Fri. July 15 by 5pm (note new time!)
2. Each report will be graded pass/fail.
3. Final grades: A: 3 passes, B: 2 passes, C: 1
pass, No Credit: 0 passes.
Graduate students
may try for an S grade by passing all three reports, and doing
additional optional bonus questions.
4. Reports will be based on exercises given in class, which will be
posted on this web page.
5. Reports should be left in the report box at the entrance to
Engineering Building 10.
Teaching Assistant:
Paku Daichi
Engineering Building 10, Room 324
Email: dpaku@kuis.kyoto-u.ac.jp
Turing test (See lecture
summaries July 13) The computer answers are
b, b, b, b, b, a, a, a, a, b
Third
Report.
Due
July 15, 5pm,
Engineering #10 1F Project Drop Box June 29
question revised July 13!
The
questions
for this report are
now complete.
June 15: Diet Problem
Review the slides for the diet problem. Now formulate your
own diet problem using at least 6 foods available from your local
supermarket and the packet labels.
Choose at least 4 daily requirements mentioned on the labels, such as
calories, fat content etc.
(If you cannot read Japanese, you will have to make up some reasonable
data.) Also put in any other
reasonable constraints that you can think of.
Finally solve the problem using a
linear programming solver such as this one: http://www.zweigmedia.com/RealWorld/simplex.html
June
22: Graph
drawing.
Either by hand or by using any
software you can find, find a nice
way to draw the mystery graph given at
http://www.graphdrawing.de/contest2010/graphs/mystery.txt
which has 17 nodes and 49 edges.
By nice, I mean in a way that you
feel gives some information about its structure. Can you guess what the
graph represents?
June
29 :Random Prime generation. Set up your own
random number generator based on X_{n+1} = 11 X_n + 3 (mod 10) (Revised July 13: the earlier formula
does not make a permutation!)
(a) Choose any seed X_0 and verify
that the generator gives a
permutation of {0,1,2,...,9}
(b) Add 5 to each of your numbers, so
you have a permutation of
{5,6,...,14}.
(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)
Second
Report.
Due
June
13, 5pm,
Engineering #10 1F Project Drop Box
The questions
for this report are
now complete.
May
18: (k-nearest
neighbour rule)
In this exercise you will use this
rule to predict the cholesterol content of McDonalds sandwiches.
First review
slides 20-22 from the lecture.
Next choose a sample 10
different sandwiches from the list at:
http://nutrition.mcdonalds.com/nutritionexchange/nutritionfacts.pdf
Record the data: (Total fat,
Saturated Fat, Trans Fat) and Cholesterol for each sandwich.
Now choose three other sandwiches.
Use Euclidean distance and the
k-nearest neighbour rule to predict the cholesterol level for each
based on the data (Total fat, Saturated Fat, Trans Fat).
Do this for k=1,2,3. Which value of k
gives the best results?
May
25: 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.
June
1: Do the reading for today's
lecture. In a known plain
text attack you know a message
M and its encryption C.
In a chosen
plaintext attack you can
generate your own message M and get its encryption C.
Explain, using examples, why a chosen
plaintext attack is more powerful than a known plain text attack for
(a) a general substitution cipher (b) a transposition cipher.
(In a substitution cipher each letter
of the alphabet is mapped to an arbitrary letter. In a transposition
cipher you permute the order of blocks of n letters, for some given n )
June
8: Work through by hand an example of
the Diffie-Hellman key exchange for three users A,B,C, using p=13 and
g=2.
(a) Create a public key for each
user. (b) Use these keys to establish a private key for each pair of
users.
First
Report.
Due
May
16, 5pm,
Engineering #10 1F Project Drop Box
The questions
for this report are
now complete.
April 13:
Consider
the
algorithm
gcd2(a,b) for finding the greatest common divisor when a
>= b > 0. (Similar to GCDbad in the class notes)
gcd2(a,b)
1. If a=b then output a and stop.
2. If a > 2b compute gcd2(a-b,b) else
compute gcd2(b,a-b).
(i) Prove that gcd2(a,b) correctly computes the greatest common divisor
of a and b.
(ii) What is the worst case
behaviour of gcd2? Ie. if a has n digits, estimate the maximum number
of times gcd2 is computed as a function of n. Compare with Euclid's
gcd(a,b) discussed in class.
April
20:
(Question 1 corrected
April 22)
1. You
are given an undirected graph
with all vertices of even degree except
vertices s and t which have odd degree.
Directly prove by giving an algorithm that there is a path from s to t
that uses every edge at least once.
2.
Review the Party theorem for 6 people. Use it to
prove the following:
In any party of 11 people there are
always either 4 mutual friends or 3
mutual strangers (or both).
Hint: Pick any person. Either she
knows at least 6 people or she does
not know at least 4.
April
27: Solve the shortest path problem described here using Dijkstra's algorithm.
There are 40 edges. Assign weights at random, using each of the numbers
1,2,3,...,10 four times each.
Show only the first three iterations of the algorithm in detail.
Give the final answer, showing the set S and the distance from s to
each node in S, directly on the given graph.
Optional
Bonus
Question: Show using elementary
arguments that the Sieve
algorithm for listing all primes less
than or equal to n runs in time polynomial
in the output size.
You should not quote any theorems,
but try to find a direct proof
yourself.
The algorithm is as follows:
Build a list of all the integers
greater than one and less than or
equal to n.
Strike out the multiples of all
primes less than or equal to the square
root of n,
then the numbers that are left are
the primes.