Welcome

Tel-Aviv University
School of Computer Science
Algorithms
0368.2160
Spring Semester 2020

News

ציוני מועד א'


שלום לכולם,
בעוד זמן קצר יהפכו לזמינות מחברות ה-gradescope של הבחינה.
שימו לב שהציון שמופיע ב-gradescope הוא סך הנקודות על השאלות, אבל ציון הבחינה חושב כך:
לכל אחת מ-3 השאלות הטובות ביותר ניתן משקל של 0.3, ולשאלה הפחות טובה ניתן משקל מופחת של 0.1.
אלו שציון הבחינה שלהם 55 ומעלה, הוזן להם 'עובר'.
הציוניים הבינאריים צפויים להתעדכן במידע האישי הערב.
בהצלחה לכולם!


(09 Aug 2020 10:15)

מבנה המבחן


שלום לכולם,
הבחינה תהיה דומה לבחינות משנים קודמות, תכיל 4 שאלות, חלקן מרובות סעיפים על חומר שכוסה בהרצאות, תרגולים, ותרגילי הבית. החומר סגור, ניתן להשתמש בדף העזר משנים קודמות הנמצא כאן [http://tau-algorithms.wdfiles.com/local--files/exams/appendix.pdf]. משך הבחינה 3 שעות. הנחיות טכניות ולינק ל-zoom ימסרו לקראת הבחינה.
בהצלחה!


(11 Jul 2020 21:15)

ציוני תרגילים 1-4 הועלו למודל‎


שלום לכולם,
העלינו את ציוני תרגילים 1-4 ל-moodle (ניתן לגשת דרך לחיצה על "ציונים"), והציון המופיע ב-moodle הוא ציון התרגיל הסופי (לציון תרגיל בית 1 יש להוסיף את ציון הבחנים, שמופיע גם הוא).
בנוסף, שימו לב שבאתר פורסם מסמך שגיאות נפוצות בתרגיל בית 4 שנכתב ע"י הבודקים, ומופיע תחת Excercises.
שבוע נעים לכולם.


(21 Jun 2020 17:33)

תרגיל 6 פורסם


שלום לכולם,
תרגיל 6 זמין כעת, וההגשה היא ב-2 ביולי.
אפשר לבחור לא להגיש את הפיתרון לשתי שאלות (יש אפשרות לקבל ניקוד מוסף).
שימו לב שמובטח לגבי שאלות 1-4 שהן ללא תלות בתירגולים הבאים.
גם שאלות 5-8 ניתנות לפיתרון כבר עכשיו, אבל יש ביניהן כאלה שהתירגול הבא יכול לעזור. לשיקולכם בתיכנון הזמן.
נדגיש בעקבות שאלות, שאין תרגיל כלשהו שהוא עם חובת הגשה כתנאי להקלות שפורסמו.


(12 Jun 2020 14:17)

הקלות הנוגעות לציון שיעורי הבית


שלום לכולם,
ברצוננו לעדכן בהקלות הבאות הנוגעות לציון שיעורי הבית:
1. ציון שיעורי הבית יחשב כמגן.
2. במקום שיקלול של 95% לממוצע 5 התרגילים הטובים ו-5% לתרגיל הפחות הטוב, השיקלול עודכן ל-95% לממוצע 4 התרגילים הטובים ו-5% התרגיל השני פחות טוב (כאשר התרגיל הכי פחות טוב לא ייחשב).
3. בתרגיל 6 תוכלו לבחור לא להגיש שתי שאלות לבחירתכם (עם אפשרות לקבלת ניקוד מוסף).
אנו סבורים ששינויים אלו (אופן חישוב ציון מיטיב) הולמים את התקופה החריגה, והם נועדו לעזור.
שבוע נעים לכולם.


(11 Jun 2020 14:37)

תוספת זמן לתרגיל 5 והודעות נוספות


שלום לכולם,

נוסף זמן לתרגיל 5, ותאריך ההגשה עודכן ל-10.06.
בנוסף, בשבוע הקרוב עקב חג השבועות לא יתקיימו תירגולים (גם לא ברביעי). בשבוע הבא התירגולים ישובו לסדרם עם תירגול בנושא דואליות.

המשך שבוע נעים,
ג'אד וטל


(25 May 2020 17:29)

Homework 5


Hi everyone,

We have uploaded homework 5 to the site, the deadline is 4.6.2020.

Best.


(21 May 2020 18:51)

Taking over from Haim + Linear Programming


Hi everyone

I am taking over from Haim now and will cover the topics until the end
of the semester. I will try to match the high standards set by Haim.

The next topic on our agenda is Linear Programming. You can find links
to the presentation and to the first recordings on Haim's web-page. More
recordings will be added later today and possibly tomorrow.

More material will be added to the presentation, so download the latest
version from time to time.

Enjoy the rest of the course!

Uri Zwick


(17 May 2020 08:18)

last part of the week's lecture


Dear all
The last ~30min of this week's lecture (on algorithms for transitive closure) is now available.
regards
Haim


(11 May 2020 18:02)

This week's lecture


Dear all

I uploaded the videos of this week (except of the last 1/2 hour or less, which I have not managed to finish yet, hopefully I will be able to add it soon).
In anycase what is up there now should suffice for this week's tirgul.
The first video is still about point to point shortest paths. The others present algorithms for finding all pairs shortest paths (they all use techniques that we have already developed).

best regards,
Haim


(10 May 2020 13:44)

Please refresh Ex4


If you already downloaded Ex4, please refresh the exercise file (so it is not cached by your browser), as we made a slight modification.


(07 May 2020 16:47)

Homework 4


Hi everyone,

We have uploaded homework 4 to the site, the deadline is 21.5.2020.
We are aware that some of you are going to take your exams from the previous semester. Any student that takes such an exam and finds it hard to submit the homework on time is welcomed to send an individual request via the Moodle forum (we will be understanding). 

We feel that solving the homework is an essential part of the learning process (especially in Algorithms). Thus we believe, that it is in your interest (the students) to solve these questions individually and in a timely manner, while at the same time we understand that this semester is challenging.

Best.     


(07 May 2020 15:50)

This week videos


Hi all

I uploaded ~2/3 of this week's lecture. This is the 2/3 that you would want to watch before your recitation on Wed/Thu. I will try to prepare and record the remaining material soon. But, in anycase, the remaining material would not be important to watch before the recitation, you can also watch it afterwards.

Update:
I uploaded the last part of this week's lecture, hope you'd enjoy it.

regards
Haim


(02 May 2020 18:10)

Friday's recitation at 11:00


Hi everyone,

The link for Friday's recitation tomorrow at 11:00 is given below (recall that this is a substitution for Wednesday's recitation that was cancels):

https://zoom.us/j/98013459563

Best.


(30 Apr 2020 10:23)

לינקים לתירגולים


שימו לב שהלינקים לתירגולים הם קבועים, אז אפשר ללחוץ על הלינקים המופיעים למטה ↓


(29 Apr 2020 20:37)

First videos on shortest paths


Dear all

I uploaded the first set of videos on shortest paths. They cover the general framework that we will use to find shortest paths, and the algorithm of Bellman-Ford for single source shortest paths in directed weighted graphs (allowing negative edges as along as no negative cycles are reachable from the source).

I hope you'd enjoy watching this. It is split into 4 relatively short videos, each about 30 minutes long.

Please watch this before your upcoming recitation after the holiday.

יום עצמאות שמח
Haim


(27 Apr 2020 10:14)

תירגולים והודעות נוספות


שלום לכולם,
1. בנוגע להצעה שקיבלנו לעבור ל-4 תירגולים מוארכים במקום 6, אנחנו מודים לכל מי שנתן פידבק. קיבלנו הערות רבות רלוונטיות וטובות. עקב כך שכ-30% מאלו שהשיבו העדיפו זאת, אנחנו נשאיר את המצב הקיים על כנו (על מנת לבצע שינוי כזה דרושה הסכמה רחבה). בפרט מחר יתקיימו 5 תירגולים בשעות הרגילות.
2. תרגיל בית 3 הועלה לאתר, והוא להגשה ב-06.05.
3. ציוני תרגיל בית 1 פורסמו, ציון התרגיל הוא סך הנקודות שקיבלתם פחות ציון השאלה הכי פחות טובה, יחד עם הבונוסים של הבחנים (ב-gradescope הציון שמופיע הוא סך הנקודות, אבל אצלנו רשום הציון שמחושב כך).
4. לקבוצת התירגול של יום רביעי עם ג'אד: בשבוע הבא באופן חד פעמי התירגול יתקיים ביום שישי ב-11:00 בעקבות יום העצמאות שחל ברביעי (הלינק כרגיל יפורסם באתר).

ערב טוב לכולם,
ג'אד וטל


(22 Apr 2020 17:12)

Dynamic programming

Dynamic programming

Dear all,

By now all the videos on this topic are on the web site. There are two more examples in the book which I did not cover. I may add a video on one of them (which you can think of as an extra recitation on the topic), but, i think that even without it there are plenty of examples there. You will get a few more in the recitation.

Please try to view lectures before your recitations on Wednesday and Thursday.

As usual feedback and questions are welcome.

Regards
Haim


(21 Apr 2020 12:08)

מועד ההגשה של תרגיל 2


מועד ההגשה של תרגיל 2 עודכן להיות ה-19.04.


(05 Apr 2020 13:03)

Recent Forum Posts

** אם יש לכם שאלה ממבחן, נא לצרף אותה כטקסט או כצילום מסך. ראו איך לעשות זאת כאן מצד ימין <—. מומלץ לנסות לענות לאחרים! **

ציון סופי: ציון סופי

By guy alt on 09 Aug 2020 11:38

האם אין התחשבות בתרגילי הבית? מירב המאמצים והזמן הושקעו בתרגילים השונים ומן הראוי שלפחות תהיה התחשבות בציוניהם. עבור תלמידים שהשקיעו את מירב זמנם בפתירת התרגילים ובפתרון הבחנים על מנת לשפר את ציונם זוהי גישה לא הוגנת.
בנוסף, במבחני הפקולטה תמיד אי מענה על שאלה מזכה ב-20% מנקודות השאלה על אי מענה מוחלט. מדוע לא מקיימים זאת במבחן ספציפי זה? במידה וזה לא כך אזי תמיד היה כדאי ל"נחש" תשובה.

2019BB שאלה 4: Re: 2019BB שאלה 4

By tal_yank on 16 Jul 2020 15:54

לשני הסעיפים יש פיתרון לינארי, ואחת הדרכים לפתור היא באמצעות תכנון דינאמי.
כדאי ראשית לנסות לחשוב על הגדרת תת-בעיה מתאימה לסעיף א', ולהשתמש בה (ואולי בתת-בעיה נוספת ודומה) בשביל סעיף ב'.

אייפד במבחן: Re: אייפד במבחן

By tal_yank on 16 Jul 2020 15:48

היי,
על פי ההנחיות לא ניתן.
טל

מבחן 2016 אא שאלה 4: Re: מבחן 2016 אא שאלה 4

By tal_yank on 16 Jul 2020 15:45

היי,
אז כאן הגרף כולו נתון (למעשה מדובר בגרף המלא), ונקבע רק ע"י n1,n2,3. כמה איטרציות של מציאת זרימה חוסמת דיניץ יבצע על גרף כזה? (התשובה אולי מפתיעה)
לאחר שעונים על השאלה הזאת- צריך לחשוב כמה זמן תקח מציאת זרימה חוסמת.
במקרה של סעיף ב' התשובה היא כמובן O)E( (במונחים של n1,n2,n3), אבל גם לגבי הרשת של סעיף א' אפשר להגיד משהו.
טל

תרגיל 6 שאלה 6: Re: תרגיל 6 שאלה 6

By Jad Silbak on 16 Jul 2020 14:30

Hi Erez,
I recommend that you focus on the min-cut in this question (this is not a typical matching problem).
Try to construct a graph that for every "subject z_i" the min-cut will either contain an edge with x_i or y_i (but not both).
Try to represent every z_i by a node.

Best.

2014B A Q4 - Dynamic Programming: Re: 2014B A Q4 - Dynamic Programming

By tal_yank on 16 Jul 2020 14:19

היי,
אפשר להגדיר תת-בעיה עם ערך בוליאני.
נשים לב שלכל x_i יש לנו 3 אפשרויות: או שהוא ב-I, או שהוא ב-J, או שהוא לא באף אחת מהן. כדאי לחשוב איך הבעיה משתנה בהתאם לכל אפשרות (כלומר מה תת-הבעיה שמתאימה לכל אפשרות).
טל

מבחן 2020אב שאלה 2: Re: מבחן 2020אב שאלה 2

By Gai greenberg on 16 Jul 2020 13:45

אני הוכחתי בלי אינדוקציה, אלה יותר מההגדרה של PRIM תגידי לי אם נראה לך הגיוני
נניח בשלילה כי משקלה של הקשת f יותר גדול מהמקסימום של e1,e2
בגדול ניתן להניח כי בשלב כלשהוא שעוד לא נגמרו האיטרציות הצומת u1 בה"כ (כי הצומת ב-U ) תתגלה ע"י פרים
כעת אם הקשתות שנוגעות ב-u1 הן f או e1 אז בהכרח האלג' של פרים יבחר את e1 שכן משקלה יותר קטן - סתירה לנתון
אם יש קשת יותר קטנה על p שהיא לא אותו f שאנו בודקים אז נבחר בה אבל לא יכולות להיגמר האיטרציות לפני שנגיע ל-u2 , לכן בהכרח מתישהו האלג' שוב יגיע להתלבטות האם לבחור את e1 או את f וכמובן שיבחר בe1 במקרה שלנו דבר שיוביל שוב לסתירה
ניתן להראות באותה צורה על u2 אבל ההחלטה כי בחרנו בלי הגבלות הכלליות אמורה להספיק , כן כן להרואת ש-f יחידה לא מקיימת את ההגדרה מספיק לסתירה כי דורשים שכל קשת על המסלול p תקיים את התנאי .
נקודה אחרונה היא שאם מגלים בה"כ את u1 לפני u2 אז הגילוי של U2 יהיה דרך u1 שכן יש מסלול p בגרף T

מקווה שזה היה ברור

מבחן 2020אב שאלה 2: Re: מבחן 2020אב שאלה 2

By estykkk on 16 Jul 2020 08:49
0437jO.jpg

התמונה לא עלתה כמו שצריך… נשמח לעזרה להבין איך להוכיח את ב. תודה

תרגיל 6 שאלה 6: תרגיל 6 שאלה 6

By Erez C on 16 Jul 2020 06:48

היי,
אפשר כיוון לפתרון השאלה?
היא נראית כמו בעיית התאמה אבל לא ברור לי איך לבנות את הגרף, ואיך להוציא מתוך הזרימה המקסימלית בו מחיר מינימלי בדעת הקהל.

תודה רבה

מועד 2020 סמסטר א מועד ב: Re: מועד 2020 סמסטר א מועד ב

By noakohavi on 16 Jul 2020 06:44

בהמשך לשאלה זו- בפתרון נאמר כי לאחר שנעשה צעד לכל משתנה שאינו 0 נסיים. איך ניתן לדעת שלא נחזיר משתנים שכבר הורדנו מפונקציית המטרה? (כלומר נחזיר בצעד על משתנה אחר משתנה שכבר העברנו להיות בסיסי, להיות לא בסיסי?)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License