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

כמו שהבטחנו, הציון מורכב מ-80 אחוז מבחן, 10 אחוז פרוייקטים, 10 אחוז שיעורי בית.
לציון המבחן ניתן פקטור של 6 נקודות.
בונוס 3 נקודות ניתן למי שענה את התשובה היעילה ביותר עבור שאלה 10.

כמקובל בפקולטה, ציונים בין 55 ל-59 עוגלו ל-60.
בבדיקת המבחנים של גרסה 2 הורדו 9 נקודות למי שסימן תשובה נכונה בשאלה אחת.
הנקודות הוחזרו בעידכון ציונים נוסף. לא הורדו נקודות לאף אחד.
מי שסימן תשובה אמריקאית נכונה קיבל את כל הנקודות.
ניקוד חלקי של 4 נקודות ניתן בשאלה על מיון וחסם תחתון למיון, כאשר היו 2 סעיפים נכונים וסומן רק אחד מהם.

במקרה של בעיה נא להגיש ערעור.
מבחן שיתקבל לערעור ייבדק מחדש במלואו.
במידה ויתגלו טעויות, הציון יעודכן (מעלה או מטה) .

ניקוד המבחן by Danny FeldmanDanny Feldman, 12 Aug 2009 21:31

מצטרף.
בסריקה אין שום יכולת להבין את הניקוד בפועל.

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

Re: Exam
Danny FeldmanDanny Feldman 10 Aug 2009 18:30
in discussion Hidden / news » Exam

Sorry, it is now updated (version 2, q1).
We are now checking whether there was a problem with the grading of this question.

Re: Exam by Danny FeldmanDanny Feldman, 10 Aug 2009 18:30
Re: Exam
nivsteinnivstein 09 Aug 2009 21:55
in discussion Hidden / news » Exam

Could you please explain how to get that E(L) = 2N in the question about Huffman coding (question #1)?

And how were the 9 points divided between questions 4+5 and 7+8?

Thank you

Re: Exam by nivsteinnivstein, 09 Aug 2009 21:55

שלום

האם אפשר לפרסם את התשובות לשאלות אמריקאיות מהמבחן?

יעזור מאוד במיוחד לאלה שחושבים אולי להגיש ערעור

תודה

Exam
Danny FeldmanDanny Feldman 09 Aug 2009 19:20
in discussion Hidden / news » Exam

Version 1: 2,6,1,2,2,4,4,3,5
Version 2: 4,3,6,1,2,2,4,4,5

Exam by Danny FeldmanDanny Feldman, 09 Aug 2009 19:20

למי שעדיין קורא את זה, נראה שפורסמו הציונים.

Re: פרסום המבחן by yoavniryoavnir, 04 Aug 2009 09:29

מתי, אם בכלל, תפרסמו את המבחן באתר?

תודה

פרסום המבחן by dutzidutzi, 22 Jul 2009 18:30
Re: מיונים
YahavYahav 18 Jul 2009 20:05
in discussion Forums / Data structures » מיונים

בקצרה -
חסם עליון נקבל, כמו תמיד, בעזרת אלגוריתם.
למשל - נמיין בעזרת עץ חיפוש מאוזן.
במקום כפילויות, נחזיק מונה לכל ערך.
לכן, כל פעולה על העץ תהיה
$O(\log k)$.

חסם תחתון במודל ההשוואות נקבל כמו למיון רגיל.
נראה מה עומק עץ ההשוואות.
לשם כך נחשב את כמות הפלטים האפשריים,
כלומר המיונים השונים של המערך,
שהם מספר העלים בעץ.
וזה סדר גודל של
$k^n$.

Re: מיונים by YahavYahav, 18 Jul 2009 20:05

That's what I thought, I was wondering about it because the solution given was with the "standard" way; finding n/k smallest element, then 2n/k smallest….. with O(nk) WC.

Hi,
I don't remember exactly what was said in class, but what u wrote won't necessarily work(the element that appears n/lgn times might "span" over 2 of the arrays u got at the last step), but it's almost there I think.

How about this:
Let's say we want to find out if some element appears c times, in general. (in your case c=n/lgn)
We preform O(lg(n/c)) steps till we have 2n/c subarrays each of size c/2 (by selecting the median each time).

At this point our element must occupy a whole sub-array by itself. Collecting all sub arrays that contain a single element (that repeats itself) takes O(n).

Now, for each of the subarrays that we got, we need to check how many times does their element appear in the subarrays on their right, and on their left (both should add up to c/2 for returning true).
Checking this takes 2c = O(c) for each sub array. since we may have as many as 2n/c satisfying our first criteria, this should take no longer than O(2n/c*2c) = O(n).

alltogether we get O(nlg(n/c))

ok, I've still thought about this, and this is what I think that should be done.
(I'm writing in English as I see my question in Hebrew is messed.)

We get (approximately) lgn sub-arrays, each of size n/lgn. We choose one element from each sub-array.
Then, for each element, we compare it to the n/lgn elements to the right of it (or less if there aren't n/lgn),
and we also compare to elements to the left of it.
If we do find it equals (n/lgn)-1 of the elements, the answer is 'yes'. If we never find out such a case, the answer is 'no'.

The total time for the second portion (after the partial sorting) is therefore O(lgn)*O(n/lgn) = O(n).

כאשר המערך "כמעט ממוין" בחר נציג מכל גוש (תת-מערך).
זה יבטיח שבמערך הממוין לקחת נציג מכל תת-קבוצה קטנה של איברים רצופים

ראינו שלשום בתרגול שאפשר לבדוק אם יש איבר במערך שחוזר n/lgn פעמים בזמן קצר יותר אסימפטוטית מ-Theta(nlgn).
נעשה שימוש ב-Quick sort חכם (לפי מיטב הבנתי, נק' ה-pivot בכל שלב היא ה-median, אותו מוצאים בזמן Theta(N) ע"י שימוש ב-Select).
אבל עוצרים את האלגוריתם כאשר מגיעים לתת-מערכים מגודל n/lgn.
השאלה היא, מה בדיוק עושים מכאן? ניסיתי לראות איך אפשר לבדוק ביעילות אם איבר חוזר על עצמו n/lgn פעמים.
מה שאני מבין זה שהמערך "כמעט ממוין", כלומר כל תת-מערך קטן מזה שמימינו. אבל עדיין אני לא בדיוק רואה מכאן מה ניתן לעשות.

תודה.

מיונים
hadarbhadarb 18 Jul 2009 07:04
in discussion Forums / Data structures » מיונים

זו שאלה שנשאלה בתרגול חזרה, אבל אפשר בכל זאת לחזור על ההסבר לגבי מהו החסם העליון והתחתון למיון מערך בגודל
n
עם
k
ערכים שונים?

תודה.

מיונים by hadarbhadarb, 18 Jul 2009 07:04

Don't forget that for a fast quicksort, you only need O(n) in each side of the partition. You don't need to have exactly n/2 items in each side.
In this case, you can partition around the round_up(k/2)*n/k index.

Re: מטלה 8
Danny FeldmanDanny Feldman 17 Jul 2009 20:52
in discussion Forums / Homework » מטלה 8

נא התעלם מהשאלה, אתם לא אמורים לדעת לפתור אותה.
רק את הגירסא של או קטן במקום אומגה, שהופיעה באחד המבחנים האחרונים.

Re: מטלה 8 by Danny FeldmanDanny Feldman, 17 Jul 2009 20:52

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

Re: שאלה ממבחן by Danny FeldmanDanny Feldman, 17 Jul 2009 20:48
מטלה 8
urisuris 17 Jul 2009 09:18
in discussion Forums / Homework » מטלה 8

יש למישהו פתרון לשאלה 3 סעיף ב?

תודה….

מטלה 8 by urisuris, 17 Jul 2009 09:18
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License