Algorithms Course Home Page

Algorithms 2004

Messages

Here are the final grades for Moed A (updated 1.3.05).

Here are the final grades for Moed B (updated 7.8.05).

Here are the exercises grades (updated 1.3.05).

A syllabus for the exam. ps pdf
The material about operations on matrices (the last topic taught in this course) is NOT for the exam.
Some reshut questions that are not for the exam: ex4 q4(b) and q6(c), ex9 q5.
More material that is not for the exam: transversal matroids. The algorithm of Hopcroft-Karp for bipartite matching. In other words, the only algorithm for maximum bipartite matching that you need to know is the one via network flows.
All of the above is relevant for moed B as well.

Previous exams: moed A (of this year). Last year's exam ps pdf.

Info

Class:

Sunday 12:00-12:45 Chemistry 7
Thursday 10:00-11:45 Chemistry 7

Targil:

Monday 10:00-11:45 Shp 217
Monday 12:00-13:45 Levi 7
Tuesday 10:00-11:45 Shp 27
Tuesday 18:00-19:45 Shp 217
Wednesday 10:00-11:45 Shp 26

Teacher - Alex Samorodnitsky, Room 210, Ross +2. e-mail: salex@cs, phone: (65)86176.
Reception hour - Sunday 13:00-14:00, Ross +2, room 210.

TA - Danny Gutfreund, Room 25, Ross -1. e-mail: danig@cs, phone: (65)84805.
Reception hour - Wed. at 14:00. Or any other time by appointment.
TA - Evgeni Begelfor. Room 54, Ross 0. e-mail: aristo@cs, phone: (65)84406
Reception hour - Wed at 12:00. Or any other time by appointment.

Exercises:

Exercise 1[ps][pdf] submission by Wednesday 27/10 24:00. Solution [ps] [pdf].

Exercise 2[ps][pdf] submission by Sunday 7/11 24:00. Solution .

Exercise 3[ps][pdf] submission by Thursday 11/11 24:00. Solution .

Exercise 4 [ps][pdf] submission by Thursday 18/11 24:00. Solution [ps] [pdf] .

Exercise 5 [ps][pdf]. In Hebrew:[page1][page2] submission by Wednesday 1/12 24:00. Solution .

Exercise 6 [ps][pdf] submission by Wednesday 8/12 24:00. Solution (ps) Solution (pdf).

Exercise 7 [ps][pdf]. NOTE: We have changed the submission to Sunday 19/12 24:00. Solution (ps) Solution (pdf).

Exercise 8 [ps][pdf] submission by Wednesday 29/12 24:00. Solution .
In the hint to question 1, you need to subtract from column j+1 the j'th column multiplied by x_{n-1}, but you don't change the j'th column.
In question 2(a), you can assume that p(x) can be divided by (x-x_0) with no remainder.

Exercise 9 [ps][pdf] submission by Wednesday 5/01 24:00. Solution .

Exercise 10 [ps][pdf] submission by Thursday 13/01 24:00. Solution (ps) Solution (pdf).
Question 5: Assume that y has at least two distinct prime factors which are strictly larger than 2. Also, in the third line of the algorithm it should be: run the algorithm A on c. When we say that there is no guarantee on the behavior of A when p is not a prime number, we mean that it can either return a square root or return some other number, or stop with an error message.
Clarification: question 3 says that if e=3 and you know d, then you can efficiently factor n.

Exercise 11 [ps][pdf] submission by Sunday 23/01 24:00. Solution [ps] [pdf] .
In question 4(a), the matrix A should be symmetric.
In 3(b), in the definition of the norm, p_1 should be in the denominator (mechane) and p_2 in the numerator (monne). We only ask you to prove 3(b) for the case p_1 = p_2.
Question 5: The "sehem" is a linear combination of bagrut mean and psychometric test. You need to show how to find the coefficients.

Books

Introduction to Algorithms, by T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Second Edition
you'll need the DjVu plug-in to read the file.
Randomized Algorithms, by R. Motwani and P. Raghvan

Useful Links

Technion, The Algorithms course

Introduction to complex numbers

On Rabin's public-key cryptosystem

Lecture notes

21/10 (greedy algorithms: the knapsack problem)

24/10, 28/10 (greedy algorithms)

31/10 (greedy algorithms: matroids)

4/11 (greedy algorithms, dynamic programming)

Additional notes about matroids, taken by Alex. ps pdf

7/11 (dynamic programming)

A correct solution to the Traveling Salesman Problem with bitonic tours (that first go all the way to the right and then return all the way to the left).

14/11 (approximation algorithms)

18/11 (approximation algorithms) 1 2 3 4

21/11 (approximation algorithms) 1 2

Tirgul 24/11 (approximation algorithms) 1 2 3 4 5

25/11 (approximation algorithms) 1 2 3

28/11 (approximation algorithms, using probability)

2/12 (approximation algorithms, flows in networks)

5/12 (flows in networks) 1 2 3 4

9/12 (flows in networks) 1 2 3 4 5 6

Tirgul 14/12 (flows in networks)

16/12 (flows in networks)

Tirgul 20/12 (matrices, polynomials, and complex numbers)

19/12 (flows in networks, FFT) 1 2 3

23/12 (FFT) 1 2 3 4

26/12 (FFT)

Tirgul 28/12 (GCD, modular operations)

30/12 (cryptography)

2/1 (cryptography) 1 2

Tirgul 4/1 (Chinese remainders, Rabin's public-key encryption) 1 2 3 4

6/1 (groups) 1 2 3 4

9/1 (The algorithm of Miller-Rabin for primality testing)

Tirgul 11/1 (operations on matrices)

13/1 (primality testing, matrices)

16/1 (matrices) 1 2 3

Lecture notes from last year

Huffman Codes [ps , pdf]

Greedy algorithms [ps][pdf]

Matroids [ps][pdf]

Dynamic programming [ps][pdf]

Matrix Operations[ps][pdf]

Least squares, SVD decomposition [ps][pdf]

Algebra [ps,pdf]

GCD & Modular Equations[ps][pdf][msword]

FFT [ps][pdf]

FFT - continued [ps][pdf]

Flows in networks [ps][pdf], Appendix - figures for the flow networks notes [ps][pdf]

The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate, Uri Zwick. Published in Theoretical Computer Science 148, 165-170 (1995).[ps][pdf]

Number theory and Cryptography[ps][pdf]

Prime numbers[ps][pdf]

Approximation algorithms[ps][pdf]

Grading Policy and other:

There will be 12 -13 exercises.
The exercises will be published in this home page every Wednesday (unless we announce something else).
Each exercise is given for a week.
The exercises should be submitted by Wednesday 24:00, the week after they are given.
The exercises grade will be the average of all the exercises, discarding the two with the lowest grades. The weight of the exercises grade in the final grade is 12%.
Submitting exercises is not mandatory. You can do the exam even if you haven't submitted a single exercise. However, you get 0 for an exercise that you do not submit. So if you haven't submitted any exercise, then your final grade can't be more than 88. needless to say, we strongly recommend you to do the exercises. It will be much easier to follow the course, since some of the material is technical and needs to be done by hand.
The exercises will include questions that are classified as "reshut". These questions will not be graded or checked (however, we will publish a solution for them). The material for the exam will include all exercises including the "reshut" questions.

Submit your solutions in the course exercises box in Ross -2.