Recent Forum Posts
From categories:
page 1123...next »

I think it is best to ask regarding specific questions when it's relevant. In this course we do our best to IGNORE what type of representation we use, and focus on algorithmic aspects. We consider specific representations only when we wish to show that they improve the runtime.

Moreover, typically we don't require a runtime that is better than linear in the input (i.e., less than O(V+E)), HW 2 question 2 is a rare exception, and it doesn't require a special representation.

במקרה כזה האלגוריתם הנדרש באמת לא יהיה
O(V),

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

בנוסף, הכוונה שלי מקודם הייתה שאם אלגוריתם רץ בזמן
O(f(k)*V)
אז הוא גם רץ בזמן
O(f(k)*V + E)

by ophirfophirf, 24 Apr 2017 12:32
Student (guest) 22 Apr 2017 11:45
in discussion Discussions / Q&A, Spring 2017 » תרגיל בית 2 - מועד הגשה

שלום,

ישנם 3 תאריכים שונים להגשת שיעורי בית #2:

- בקובץ כתוב: 27.04
- במייל שנשלח: 04.05
- בדף התרגילים באתר: 05.05

מהו התאריך הנכון ביותר?

by Student (guest), 22 Apr 2017 11:45

Computing the lists lengths takes $\Theta(V+E)$ so it can't be computed for some algorithms. (Non that we've seen so far, but I'm asking this for the rest of the course).
In the adjacency lists representation we keep an array of adjacency lists for each vertex. What I meant by "vertex own index" is that the vertices, as objects, would store their own index in that array (so in an undirected graph $G$, if $v.index = 7$ and $G.adj[7] = [u,w]$ than $u,w$ are the only vertices adjacent to $v$). Another representation could store an array of vertices, each storing their own adjacency list ($v.adj = [u,w]$ and $G.vertices[7] = v$).
But more than I'm interested in specific teaks to the representation, I'm interested if we can choose EXACTLY how to implement the adjacency list representation and under which constraints.

Thanks

Tomer Solomon (guest) 21 Apr 2017 15:17
in discussion Discussions / Q&A, Spring 2017 » תרגיל 2 שאלה 2

היי,

לא כל כך הבנתי מה הסיבוכיות המבוקשת בשאלה.
אם הסיבוכיות שאתה מכוון אליה היא O(f(k)*V), למה היא נחשבת ל-O(V + E)? (האם ה-f(k) נכלל פה במסגרת הקבועים של O?)
בפרט, מה קורה כאשר לדוגמה k הוא מאותו סדר גודל של v, למשל k = v/2

תודה רבה,
תומר

by Tomer Solomon (guest), 21 Apr 2017 15:17

הניסוח באמת מבלבל,
שים לב שאם משהו רץ בזמן
O(V)
אז הוא גם רץ בזמן
O(V+E)
הכוונה היא שהאלגוריתם ירוץ בזמן של
O(f(k) * V)

by ophirfophirf, 19 Apr 2017 13:03
גיא (guest) 18 Apr 2017 10:03
in discussion Discussions / Q&A, Spring 2017 » תרגיל 2 שאלה 2

אבל כתוב שזמן הריצה צריך להיות
O(E+V)
בשני המקרים, אז
?Eאיך יכול להיות שהוא לא תלוי ב
?kהתכוונת ל
אם כן אפשר פשוט לרוץ k פעמים
לחינם ואז יש תלות בk..

by גיא (guest), 18 Apr 2017 10:03

הכוונה בתרגיל היא שזמן הריצה לא יהיה תלוי ב
E
באחד המקרים.

Re: תרגיל 2 שאלה 2 by ophirfophirf, 18 Apr 2017 09:00

You can compute the lists' lengths without it affecting the runtime so there's no reason to assume the length is computed..
Lists you can assume are bidirectional, when it's relevant, note sure what you mean by its own index in the list,
perhaps be more specific with the question you have trouble with.

תרגיל 2 שאלה 2
גיא (guest) 16 Apr 2017 16:57
in discussion Discussions / Q&A, Spring 2017 » תרגיל 2 שאלה 2

k-האם יכול להיות שקיים אלגוריתם שפותר את הבעיה גם לגרף מכוון וגם לגרף לא מכוון ללא תלות ב
?O(V + E) שרץ בזמן ריצה של

האלגוריתם שחשבתי עליו:

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

סריקה של גרף העל בסדר הההפוך למיון הטופולוגי ובמעבר על קודקוד להוסיף לשדה את סכום השדות של כל הקודקודים שיש ממנו קשת אליהם פחות 1
s לעבור שוב על הגרף ולקחת ל
את כל הקודקודים שנמצאים ברכיב קשיר שהשדה שלו שווה ל
k.

O(V + E)

תרגיל 2 שאלה 2 by גיא (guest), 16 Apr 2017 16:57

In questions where the graph representation is not explicitly mentioned, can we assume any of the representations we were shown in class? Also, can we tweak it a little bit to fit our needs? e.g. assume in the adjacency list representation that the lists store their own length, they're bidirectional, that each vertex stores its own index in the adjacency lists array (and thus, that it can be changed in $O(1)$), etc.?

Thanks

Leo Messi (guest) 13 Apr 2017 21:22
in discussion Discussions / Q&A, Spring 2017 » תרגיל 2 - שאלה 8

thanks

by Leo Messi (guest), 13 Apr 2017 21:22

שאלה 8 מתייחסת לחומר שטרם למדתם.

Re: תרגיל 2 - שאלה 8 by ophirfophirf, 13 Apr 2017 13:24
ophirfophirf 13 Apr 2017 13:22
in discussion Discussions / Q&A, Spring 2017 » שאלה 2

הכוונה היא להתייחס אליו כפרמטר (כמו מספר הצמתים), לא לחשוב עליך כקבוע שנעלם בסימון.
בסעיף א' נסה לחשוב על סיבוכיות יותר טובה מזו שנתת שלא מסתמכת על
k
ואז נסה למצוא אלגוריתם שעבור
k
קטן מספיק נותן זמן ריצה משופר

by ophirfophirf, 13 Apr 2017 13:22

עודכן גם בקובץ

by ophirfophirf, 13 Apr 2017 12:27

היי, המסלול הריק הוא מצומת לעצמו, אבל הצומת עצמו לא נספר כי מבקשים רק קודקודים "אחרים"

Re: שאלה 4
ophirfophirf 13 Apr 2017 12:25
in discussion Discussions / Q&A, Spring 2017 » שאלה 4

הכוונה היא לכתוב אלגוריתם שמחשב עבור כל צומת את הצומת המינימלי שממנו ניתן להגיע לצומת. האלגוריתם צריך להיות יעיל ככל האפשר

Re: שאלה 4 by ophirfophirf, 13 Apr 2017 12:25

מספיק להסביר במילים, רק שיהיה חד משמעי איך משנים את הקוד

תרגיל 2 - שאלה 8
Leo Messi (guest) 12 Apr 2017 09:45
in discussion Discussions / Q&A, Spring 2017 » תרגיל 2 - שאלה 8

היי
האם בתרגיל 2 בשאלה 8 אנחנו מתבקשים לתת פתרון על בסיס BFS או DFS שלמדנו?
ניסיתי לחפש גם באינטרנט ונראה שהפתרונות המוצעים מתבססים על אלגוריתמים שטרם למדנו (prim, Kruskal)

אשמח להתייחסותכם ,

תודה וחג שמח!

תרגיל 2 - שאלה 8 by Leo Messi (guest), 12 Apr 2017 09:45
Student (guest) 11 Apr 2017 16:21
in discussion Discussions / Q&A, Spring 2017 » תרגיל בית 2 - מועד הגשה

דחו את המועד ל-27 באפריל (המתרגל שלח מייל לכולם). הקובץ כנראה לא עודכן

by Student (guest), 11 Apr 2017 16:21
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License