Schedule + Clarification
|
Dear students, Thank you for an engaging and interactive lecture. See two announcements below. Next weeks' schedule: As a reminder: (1) next week we will meet as usual and continue our discussion of lower bounds for dynamic problems. (2) The week after that (July 14) we will have no lesson. (3) Finally, our last lesson will take place on July 21, where we will discuss the use of matrix multiplication in dynamic algorithms (by popular demand). Algorithmic point: Regarding Adir's interesting suggestion to iterate the nm^alpha ==> m^(1+alpha/2) lemma on sparse graphs, having m=O(n) edges: this unfortunately does not work, since the subgraph G[H] is not necessarily sparse, that is its number of edges |E_H| could be asymptotically higher than |H| (possibly as high as |H|^2). Therefore |E_H|^(3/2) is not O(|H|*|E_H|^(1/2)) or even O(|H|*|E|^(1/2)), and we cannot recurse this argument. (Do shoot me an email if you have other thoughts about this.) Best, David |
| עדכון אחרון ב-30/6/2026, 13:12:55 Last updated on 30/6/2026, 13:12:55 Последняя модификация30/6/2026, 13:12:55 تمت الحتلنة الأخيرة ب-30/6/2026, 13:12:55 |
HW 2 typo fix and extension
|
Dear students, Following fixes of a couple typos in question 2 (thanks to Shirley for pointing these out!), the assignment was updated (see changes in red and blue) and the deadline was extended to next Sunday’s 20:00. Best, David |
| עדכון אחרון ב-29/6/2026, 09:20:26 Last updated on 29/6/2026, 09:20:26 Последняя модификация29/6/2026, 09:20:26 تمت الحتلنة الأخيرة ب-29/6/2026, 09:20:26 |
Midway report
|
Dear students, As announced in class, (1) You can submit the midway report via the course website (a link will be added in the HW tab later today). (2) You can submit it until Sunday, 12:00 (so, a slight extension). (3) I will reach out to you to schedule a meeting to discuss the paper you read and your suggested directions (to make sure you understood the paper and its context, and that you won’t get lost, respectively). Best, David |
| עדכון אחרון ב-23/6/2026, 13:32:20 Last updated on 23/6/2026, 13:32:20 Последняя модификация23/6/2026, 13:32:20 تمت الحتلنة الأخيرة ب-23/6/2026, 13:32:20 |
HW 2 out
|
Dear students, HW 2 is available on the course website. Due date is July 2nd. Enjoy! Wishing us all a quiet weekend, Course Staff |
| פורסם ב-12/6/2026, 10:31:44 Created on 12/6/2026, 10:31:44 Создано12/6/2026, 10:31:44 تم النشر ب-12/6/2026, 10:31:44 |
Tomorrow's class and HW updates
|
Dear Students, We hope you and your families are safe. Following the latest Technion announcement, tomorrow's class will be held on campus. For those unable to attend, the lecture and tutorial will be broadcast via Zoom and recorded (link available under the "Staff" section). Important Updates: HW1 Deadline: Extended to Sunday, June 14, at 20:00. HW2: Will be released this Thursday with a three-week deadline. Office Hours: Nitay will hold office hours on Tuesday (9.6) at 16:30 via the regular Zoom link. Stay safe, Course staff |
| עדכון אחרון ב-8/6/2026, 21:12:43 Last updated on 8/6/2026, 21:12:43 Последняя модификация8/6/2026, 21:12:43 تمت الحتلنة الأخيرة ب-8/6/2026, 21:12:43 |
Reading Before Lecture 6
|
Dear students, Thanks for yet another interactive lecture+recitation this week on deterministic dynamic matching and MIS. Next week we will shift back to randomized algorithms, and will in particular make use of Chernoff bounds, which we will state and use in class without proof. To better prepare for the lesson and recall/learn why these powerful bounds hold, we recommend reading the first two pages and the appendix of Lecture 6's lecture notes. For any questions, feel free to email the course staff. Wishing us all a quiet and pleasant weekend, Course Staff |
| עדכון אחרון ב-5/6/2026, 12:45:56 Last updated on 5/6/2026, 12:45:56 Последняя модификация5/6/2026, 12:45:56 تمت الحتلنة الأخيرة ب-5/6/2026, 12:45:56 |
HW 1 update (for real)
|
Dear students, Thanks to Amir for pointing out the recurring typo in HW 1 which apparently wasn't uploaded. Please verify that in Q3, part 1, you can see (in blue) update(i,v): set x_i <- x_i +v (and not x_i <- v). Best, David |
| פורסם ב-2/6/2026, 14:02:15 Created on 2/6/2026, 14:02:15 Создано2/6/2026, 14:02:15 تم النشر ب-2/6/2026, 14:02:15 |
Staff office hours in the coming couple of weeks
|
Dear students, Due to travel and some committee work, I (David) will not hold my regular office hours in the coming two weeks. Instead, This week: I will be available for a brief office hour in my office (Taub 518), starting right after Nitay's recitation, until 13:55. Next week: I will be available over email. Nitay's office hours over zoom on Monday evenings will be held as usual. Best, David |
| עדכון אחרון ב-31/5/2026, 14:18:02 Last updated on 31/5/2026, 14:18:02 Последняя модификация31/5/2026, 14:18:02 تمت الحتلنة الأخيرة ب-31/5/2026, 14:18:02 |
Updates to HW1 and Lecture/Recitation Notes
|
Dear students, Thank you for yet another interactive lesson! Regarding lecture 4's notes: some proofs were re-ordered and additional details in Lemma 4.6's proof were added. An additional paragraph of intuition (in blue) was added to the recitation's notes. The pseudocode of Algorithm 1 in Lecture 4 was also updated. This is not quite what Adir proposed, which is indeed simpler (thanks!), but the pseudocode I chose to present instead, with a single edge to a neighbor in R, seemed a tad simpler to interpret (to me). See if you can find other variants that work! Regarding HW1: A quick typo fix in Question 3: The update *increases* the coordinate. (Thanks Yaron for asking!) Best, David |
| עדכון אחרון ב-26/5/2026, 17:08:26 Last updated on 26/5/2026, 17:08:26 Последняя модификация26/5/2026, 17:08:26 تمت الحتلنة الأخيرة ب-26/5/2026, 17:08:26 |
This week’s office hours
|
Dear students, Nitay will not hold office hours this week, and David will hold his office hours today at 1:40-2:25 in his office, Taub 518. For any other questions you have about the course this week, feel free to email David. Best, Course staff |
| עדכון אחרון ב-26/5/2026, 10:03:25 Last updated on 26/5/2026, 10:03:25 Последняя модификация26/5/2026, 10:03:25 تمت الحتلنة الأخيرة ب-26/5/2026, 10:03:25 |
HW1 Available Online
|
Dear students, HW1 is available online. Due date is June 10th (i.e., in three weeks). To do well, see directions and recommendations in the HW. Submissions are individual, and should be typed. See the suggested HW-solution LaTeX template. For any questions, the course staff is available in class, and in office hours. Best, and chag sameach, Course Staff |
| עדכון אחרון ב-20/5/2026, 20:07:17 Last updated on 20/5/2026, 20:07:17 Последняя модификация20/5/2026, 20:07:17 تمت الحتلنة الأخيرة ب-20/5/2026, 20:07:17 |
Reminders: next lesson, paper preferences and HW1
|
Dear students, Looking forward to seeing you in class and discussing the next set of topics. Notes (but not recordings) will be available in the course site, though the in-person discussion should of course help understand them better. Regarding paper preference submission: these are due by Wednesday (via the link). HW1 will be uploaded in the next few days. It will consist of three questions and you will have three weeks to work on it. See you soon, Course Staff |
| עדכון אחרון ב-18/5/2026, 09:26:30 Last updated on 18/5/2026, 09:26:30 Последняя модификация18/5/2026, 09:26:30 تمت الحتلنة الأخيرة ب-18/5/2026, 09:26:30 |
Weeks 2 and 3
|
Dear students, Thanks for interactive live lessons yesterday! The lecture and recitation notes on the course site should help you revise and internalize the general tricks of the trade we saw yesterday, which will likely help you in your HW and project. Some tricks we didn't cover / externalize in class but can be found in the notes: - A standard reduction from Las Vegas (expected time) randomized algorithms to Monte Carlo (bounded error probability but worst-case time) - Random binary search using access to a random entry of the array rather than random access. - Approximation via discretization and rounding to powers of (1+eps). (This helps solving approximate MST using exact MST with few distinct weights, for example.) For next week, we will change things up and move on to shortest path problems. Looking forward to seeing you there and enjoying many more interactive lessons throughout the semester. Best, Course Staff |
| עדכון אחרון ב-13/5/2026, 09:59:46 Last updated on 13/5/2026, 09:59:46 Последняя модификация13/5/2026, 09:59:46 تمت الحتلنة الأخيرة ب-13/5/2026, 09:59:46 |
A few announcements (Back in person!)
|
Dear students, Looking forward to interacting with you in-person tomorrow and in future weeks, in Taub 3. As a reminder: please submit your paper preference list by May 20th (via the google form under "Requests for project papers" in the "course material"). For tomorrow's lesson: we'll pick up where we left off, and this time consider *randomized* connectivity algorithms with fast worst-case update time, followed by a recitation studying (approximate) dynamic MST. See you there, Course Staff |
| פורסם ב-11/5/2026, 11:31:29 Created on 11/5/2026, 11:31:29 Создано11/5/2026, 11:31:29 تم النشر ب-11/5/2026, 11:31:29 |
Theory Social
|
Dear students, I would like to advertise the Theory Seminar, and its social edition, which will take place next Wednesday at 13:00, in Taub 401. The seminar takes place Wednesdays 13:00-14:00 in Taub 401. Usually food is available from 12:45, followed by a talk by an invited speaker. Next week the "invited speakers" are all the theory group and friends, broadly construed: Students, postdocs and faculty members with interests in theory get to chat over lunch and then briefly introduce themselves and their interests to the group in a round table. A gong may or may not be used to enforce time :-) See the theory seminar website for more information, and a link to join the mailing list for future announcements. Wishing us a quiet, productive, and social semester, David |
| עדכון אחרון ב-7/5/2026, 18:17:07 Last updated on 7/5/2026, 18:17:07 Последняя модификация7/5/2026, 18:17:07 تمت الحتلنة الأخيرة ب-7/5/2026, 18:17:07 |
Project date updates
|
Dear students, Following the current projected timeline for the semester and exam period, the dates for the course project have been updated. For example, the project preferences are to be submitted by May 20 (a day after the third lecture). See course syllabus. God luck in your exam period. Best, Course Staff |
| עדכון אחרון ב-27/4/2026, 09:56:59 Last updated on 27/4/2026, 09:56:59 Последняя модификация27/4/2026, 09:56:59 تمت الحتلنة الأخيرة ب-27/4/2026, 09:56:59 |
Lectures 1 + 2
|
Dear Students, Thank you for a very lively and interactive first lecture this Tuesday. For those who missed the first lecture, the recording and whiteboard notes have been uploaded, and links can be found under course material->Lectures->Lecture 1. (See notes regarding the whiteboard notes PDF format.) Regarding the next lesson: Next Tuesday is Yom HaZikaron, so our next lesson will be in the next teaching week (either in three weeks or one, depending on developments in the Middle East). Wishing us quiet days ahead, and looking forward to seeing you soon. Best, David |
| עדכון אחרון ב-16/4/2026, 08:24:04 Last updated on 16/4/2026, 08:24:04 Последняя модификация16/4/2026, 08:24:04 تمت الحتلنة الأخيرة ب-16/4/2026, 08:24:04 |
Schedule for (hopefully just the) first few weeks
|
Dear students, We hope you and your families are doing well. We wanted to supply some level of certainty about the course plan for the first few week, beyond what the Technion is providing: Lectures and recitations: - Will be conducted over zoom, at least for the first two weeks. See course tab for zoom link, under David's lecture information. - If interrupted due to sirens where the staff member is teaching, the lesson might be paused, in which case the recording will be continued later. - To help in case you cannot attend for whatever reason or have sirens in your area during the lesson, we will upload recordings after each lesson. - Lecture and recitation notes will be made available in the course site before each lesson. - If you can attend lessons, we highly recommend you do so, and ask that you turn your cameras on. Interactive discussions should help us understand what points to clarify and help you internalize the topics and common tricks, which should help with your projects. Office Hours: Will be conducted over zoom. Exact time TBD. Please email David or Nitay if you want to schedule an office hour during the first week. Homework + project schedule: These are dependent on the Technion-wide decision as to when to conduct the Winter Moed B exams (currently scheduled for the two weeks starting April 26). We'll update once we have more clarity on this. Wishing us all a quiet and enjoyable semester, Course Staff |
| עדכון אחרון ב-10/4/2026, 11:28:00 Last updated on 10/4/2026, 11:28:00 Последняя модификация10/4/2026, 11:28:00 تمت الحتلنة الأخيرة ب-10/4/2026, 11:28:00 |
HW0: Refreshers
|
Dear students, We hope you and your loved ones are doing well. We are looking forward to interacting with and around some beautiful algorithmic ideas together this semester. To help you prepare for the semester, we have uploaded a homework 0, consisting of refreshers of background material relevant for the course. This HW is not for submission, but it is highly recommended you spend time on it. Best, and Chag Sameach, Course Staff |
| עדכון אחרון ב-31/3/2026, 16:40:17 Last updated on 31/3/2026, 16:40:17 Последняя модификация31/3/2026, 16:40:17 تمت الحتلنة الأخيرة ب-31/3/2026, 16:40:17 |
Update on Registration Process
|
Dear students, Registration to the course is now open, and can be done directly through SAP. The number of spots is limited, so if you cannot register through the system but would like to, do come to the first two lessons and talk to me. Some students will likely cancel registration (see next point). Course prerequisites will be enforced by the end of the registration period. If you did not yet take/pass Algorithms / Probability (or are not likely to do so by the end of registration period), please cancel your registration to leave room for others to register. A tentative schedule has been uploaded and can be found under the course material tab. Do also read the course information tab. Wishing us all a quiet and interesting semester, David |
| עדכון אחרון ב-28/1/2026, 11:25:19 Last updated on 28/1/2026, 11:25:19 Последняя модификация28/1/2026, 11:25:19 تمت الحتلنة الأخيرة ب-28/1/2026, 11:25:19 |
Hello World
|
Dear students (both registered and interested), Welcome to the course. Below is some relevant information regarding the course format (see also the "Syllabus" tab for more information). (1) The course won't have a final exam. It will include three homeworks and one project submission, which will require work throughout the semester. (2) Course prerequisites will be enforced by the end of registration period. If you did not yet take/pass Algorithms / Probability (or are not likely to do so by the end of registration period), please cancel your registration to leave room for others to register. Looking forward to seeing you in class and engaging in discussion around elegant algorithms and theory! Best, David |
| עדכון אחרון ב-28/1/2026, 11:22:37 Last updated on 28/1/2026, 11:22:37 Последняя модификация28/1/2026, 11:22:37 تمت الحتلنة الأخيرة ب-28/1/2026, 11:22:37 |