The final grades are available online.
18 points were added to the total points of your homework assignments.
Good luck with the rest of your studies!
Grades for the 4th assignment published.
The grades and the solution for the 4th assignment are published.
Please submit all appeals until March 24th via email to the course staff.
When submitting appeals please attach a scan of your graded assignment.
HW #3 update
In HW3 Question 1, there were some submitted solutions that worked only assuming that it is already known that the random graph in question is connected with probability 1-o(1).
Officially it was required to prove both the connectedness of the graph and the number of queries of the algorithm, but it turned out that some of the solutions that did not prove the connectedness itself received a full grade by us. Nonetheless we will not retroactively reduce grades.
We have therefor decided that it would be fair if all solutions that have a completely correct proof on the number of queries assuming the high probability connectedness would receive a full grade. If you have a solution of this type and your grade was reduced only concerning the connectedness part, please contact Gregory until 14.3 about this. If you have made a non-electronic submission, please provide Gregory with the original as well.
Mistake in the solution for the 3rd assignment
There was a mistake in the solution published for the 3rd assignment (In the first question).
An updated solution will be published shortly.
Grades for the 3rd assignment published.
The grades for the 3rd assignment are available online.
The graded assignments will be at the secretaries tomorrow.
Please submit any appeals by March 6th to the course staff via email only.
Solution for the 3rd assignment
The solution for the 3rd assignment has been published.
A small clarification regarding the second question in the 4th assignmnet
A small clarification regarding mu defined in the second question - mu is a probability distribution over indices such that if you pick an index according to mu, for every word in C with probability at least 90% the value at the index chosen is 1.
This does not mean that with probability 90% the value at the index chosen is 1 for ALL words in C.
4th assignment released
The 4th assignment is available on the website.
The assignment is due on Feb 28th.
HW #2 Grading update
All students who lost 2 points in the second question because of expectation \ variance rounding, please email the TA a scan of the graded paper and you will be awarded back the 2 points.
The graded papers are now available at the secretaries.
Appeals should be submitted via email to the course staff.
Please attach a scan of the relevant questions when submitting appeals.
HW #2 grades published
The grades for the second assignment are available.
Your graded papers will be at the secretaries tomorrow around noon.
HW #3 postponement
The due date for HW #3 is postponed to 21/01.
HW #3 updated and HW #2 solution posted
The solution for the second assignment is now available.
A small correction was made to the second question in the third assignment, the matching need not be perfect, only maximal.
HW 3 released
The third assignment is released and is due by Jan 18th.
Electronic submission open and small clarification
The electronic submission for the second assignment is now open.
When submitting please write your name and ID on your assignment.
Another small clarification for Q2 - don't be alarmed if your solution has O(p) equations, this is completely OK and you're not doing anything wrong.
Second assignment clarification
What you really need to prove in the second question is the existence of two functions P and N. If p>P(delta), and n>N(delta,p), then the statement is true for any set of n points in (Z_p)^m.
Material for the second assignments
The material for the second assignment is everything until and including the second moment.
This does not include large deviations as I've told some students who asked me. My apologies.
Graded HW #1 assignments are at the secretaries
The remaining graded assignments are now at the secretaries.
Graded assignments available at 414
The secretaries are closed today.
You can pick up your graded assignments from the envelope outside office 414.
HW #2, question 2 clarification
In question 2, n cannot depend on m. Please avoid trying to cover then entire space with the set A...
HW #1 grades are available
The grades for the first assignment are available online.
The assignments will be returned to the boxes near the secretaries around noon tomorrow.
Questions regarding grading or appeals should be sent via email to the course staff.
HW #2 update and HW #1 solution
A solution to the first assignment and an updated version of the second assignment are available. Both are available under "assignments".
The update to the second assignment includes the correct due date, some typo corrections and clarifications for the second question.
The second assignment is published and is due on Dec 21st.
HW calendar (approximate)
Below is a tentative timeline of HW release and submission dates:
November 22: HW2 and SL1 (solution to HW1) posted.
December 20: HW3 posted (a day before the HW2 due date).
December 21: Due date for HW2.
December 27: SL2 posted.
January 18: Due date for HW3.
January 24: HW4 and SL3 posted.
February 28: Due date for HW4.
March 13: Grades submitted and SL4 posted.
Recitation notes updated
An updated version of the recitation notes is available.
The new proof of the Isolation lemma was added.
HW #2 release date
The second assignment will be released a week from today on Nov 22nd.
The solution for the first assignment will be posted on the same day.
Electronic submission for HW #1 available
The electronic submission for assignment 1 is now open.
Please submit your assignments in pdf format.
Handwritten assignments should be submitted to Eldar's mailbox on the 5th floor.
HW 1 Question 1 clarification
|In question 1 please avoid using the negative binomial distribution and it's properties in your proof. |
You are asked about a specific case of the distribution, thus using the general distribution beats the point of the question.
HW submission guidlines
|Please do not submit the HW assignments to the course box on the 1st floor.|
An electronic submission will be opened roughly a week before the due date.
It would be best if you submit a pdf of your solution. If you prefer to write it by hand please put it in Eldar's mailbox on the 5th floor.
The graded assignments will be returned to the boxes on the 0th floor.
HW #1 Question 2 clarification
|In question 2 the bits are added after the LSB. |
For example, if our current number is 111 and our new bit is 0, then the new number is 1110.
HW #1 submission date
|Small correction, the submission date is 16/11, not 15/11.|
HW assignment #1 released and small update to the exercise booklet
|HW assignment #1 is now available and is due on 15/11.|
There is a also an updated version of the exercise booklet available.
The changes are minor and will be reviewed during recitations, so don't worry if you've printed the older version.
Complementary recitation room update
|The complementary recitation will be held at Taub 3.|
|A complementary recitation will be held Sunday (25/10) at 16:30 after Eldar's lecture.|
First homework assignment release date
|The first homework assignment will be published on Sunday morning 25/10.|
The reason for this is that you will need to use the material learned in Sunday's lecture.
I understand some of you wish to use the first assignment to estimate the difficulty / workload of the course, trying to solve it before the upcoming lecture might give you the wrong impression.
|Welcome to Probabilistic methods and algorithms Winter 2015-2016!|
Please make sure you are subscribed to automatic updates from the GR system.
Assignment #1 will be released shortly after the start of the semester.
I wish everybody a productive and enjoyable semester.