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 |