לגבי המבחן

[vogel]

שלום,

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

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

אשמח להתייחסות,
תודה,
הדס.

[ury]

והיו עוד דברים מעצבנים, למשל:
לא מציינים הגבלות מקום בזיכרון שקיימות
לא נותנים שמות לקבוצות של קלט ולא מציינים באיזה מבנה מתקבל הקלט

[eyalwu]

יאללה מספיק

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

[ury]

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

[yakirmanor]

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

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

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

[Michael]

עד עכשיו חשבתי שהלך לי טוב במבחן,
עכשיו מסתבר שלא...

[yakirmanor]

או לדוגמה מערך בגודל 200 שבה ה100 מספרים משמאל ממויינים וה 100 מספרים מימין ממויינים, איזה 100 שייכים למערך המקורי??????

[ury]

או לדוגמה מערך בגודל 200 שבה ה100 מספרים משמאל ממויינים וה 100 מספרים מימין ממויינים, איזה 100 שייכים למערך המקורי??????

וואלה צודק!
יש 2 אפשרויות ואי אפשר לדעת מה נחוץ ומה מיותר
נראה לי שהם לא חקרו את השאלה הזאת לעומק מספיק
נראה לי שהם לא חשבו על כל המקרים, וגם אם כן, 3 שעות זה לא מספיק זמן לחשוב על כל המקרים!
(ו-3 שעות זה בלי לפתור שאלות אחרות!)
אם הפתרון היה מיון בועות אז לא למדנו את המיון הזה ולכן אסור להם לשים אותו כפתרון במבחן
בכל מקרה, אני הולך למועד ב' ומצפה שהם לא יעשו את השטות הזאת שוב!

[pavelger]

הפיתרון של התרגיל הוא במיון הכנסה רגיל, אין צורך לדעת מי הם המאה שלא ממוינים.
כי כאשר יגיע תורו של מישהו מהמספרים הממוינים להיכנס למערך הממוין החדש במקרה הכי גרוע הוא יחליף מקום ויתקדם רק 100 פעם שזה סופי ויש n-100 מספרים כאלו לכן O(n
כאשר אחד מהמאה מספרים הלא ממוינים יכנס למערך הוא כמובן יכול להגיע גם לתחילת המערך כלומר להתחלף n פעמים אבל יש רק 100 כאלה לכן גם זה O(n

מקווה שההסבר ברור.

[vogel]

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

אני מקווה שמרצה או מתרגל כלשהו יואיל בטובו להגיב לעניין.

תודה ויום טוב לכולנו.

[ury]

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

[litanil]

רגע,
לא הבנתי מה לא בסדר לבדוק את ה-101 האיברים הבאים בתור?
אם האיבר ה-i הוא הכי נמוך מבין ה-101, והוא גם יותר גדול מהאיבר האחרון ברשימה של הממויינים בוודאות, אז למה שהוא לא יהיה ממויין בוודאות?

[orankap]

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