שאלת מבחן במבוא למדעי המחשב - הטכניון 2017 - מחרוזות

שאלה 3 (25 נקודות): סעיף א' (15 נק') עליכם לממש את הפונקציה: ```c int strcmp_new(char *s1, char *s2, char *abc); ``` הפונקציה צריכה להשוות בין המחרוזות s1 ו-s2 על-פי סדר האותיות במערך abc. המערך abc הוא מערך בגודל 26 אשר מגדיר סדר חדש של אותיות קטנות באנגלית (כל אות אנגלית קטנה מופיעה בו פעם אחת בדיוק). המחרוזות s1 ו-s2 מכילות אותיות אנגליות קטנות בלבד. אם s1 תופיע לפני s2 במילון שמוגדר ע"י סדר האותיות במערך abc, יש להחזיר מינוס 1. אם s1 ו-s2 בעלות תוכן זהה יש להחזיר 0, ואם s1 תופיע אחרי s2 במילון שמוגדר ע"י סדר האותיות במערך abc, יש להחזיר 1. לדוגמא, אם מערך abc בעל התוכן הבא (משמאל לימין): 'b' 'c' 'd' 'a' 'e' 'f' 'm' 'g' 'h' 'i' 'j' 'k' 'l' 'n' 'o' 'z' 'p' 'q' 'r' 's' 't' 'u' 'v' 'w' 'x' 'y' המחרוזת "air"=s1 תופיע במילון אחרי "balloon"=s2 כי במערך abc האות b קודמת לאות a, וערך ההחזרה של הפונקציה יהיה 1. המחרוזת "zero"=s1 תופיע במילון לפני "root"=s2 כי במערך abc האות z קודמת לאות r, וערך ההחזרה של הפונקציה יהיה מינוס 1. המחרוזת "bool"=s1 תופיע במילון אחרי "boom"=s2 כי במערך abc האות m קודמת לאות l, וערך ההחזרה של הפונקציה יהיה 1. עבור "language"=s1 ו-"language"=s2 ערך ההחזרה יהיה 0 כי המחרוזות זהות. דרישות: סיבוכיות זמן Θ(n) וסיבוכיות מקום נוסף Θ(1), כאשר n הוא מספר התווים במחרוזת הקצרה מבין s1, s2. אסור לשנות את תוכן המערכים שמתקבלים כפרמטרים. אם לפי חישוביכם לא עמדתם בדרישות הסיבוכיות אנא ציינו כאן את הסיבוכיות שהגעתם אליה: זמן ____________ מקום נוסף _______ ```c int strcmp_new(char *s1, char *s2, char *abc) { ``` סעיף ב' (10 נק') עליכם לממש את הפונקציה: ```c int find_sorted_words(char *words[], int m, char *abc); ``` הפונקציה מקבלת מערך words של m מחרוזות ומחזירה אינדקס $0 \leq i \leq m-2$ עבורו הקריאה לפונקציה strcmp_new(words[i], words[i+1], abc) תחזיר -1. לדוגמא, אם נתון המערך abc מהדוגמא שניתנה בסעיף א': 'b' 'c' 'd' 'a' 'e' 'f' 'm' 'g' 'h' 'i' 'j' 'k' 'l' 'n' 'o' 'z' 'p' 'q' 'r' 's' 't' 'u' 'v' 'w' 'x' 'y' ונתון המערך: char *words[6] = {"bool", "air", "balloon", "root", "zero", "language" } הפונקציה יכולה להחזיר 0 כיוון שהמילה "bool" מופיעה לפני המילה "air". הפונקציה יכולה גם להחזיר 2 כיוון שהמילה "balloon" מופיעה לפני המילה "root". ניתן להשתמש בפונקציה מסעיף א' גם אם לא מימשתם אותה. ידוע כי: • m>=2 • המילה הראשונה במערך מופיעה לפני המילה האחרונה במערך, לפי סדר האותיות במערך abc, כלומר מובטח כי הקריאה לפונקציה strcmp_new(words[0], words[m-1], abc) תחזיר -1. דרישות: סיבוכיות זמן Θ(n⋅logm) וסיבוכיות מקום נוסף Θ(1) כאשר n הוא מספר התווים במחרוזת הארוכה ביותר ב-words ו-m הוא מספר המחרוזות ב-words. אם לפי חישוביכם לא עמדתם בדרישות הסיבוכיות אנא ציינו כאן את הסיבוכיות שהגעתם אליה: זמן ____________ מקום נוסף _______ ```c int find_sorted_words(char *words[], int m, char *abc) { ```

רמז: בסעיף א', שימו לב שבניית מערך הפוך (rank) בגודל 26 עולה $\Theta(1)$ זמן ומקום (קבוע!), ומאפשרת השוואת כל תו ב-$O(1)$. בסעיף ב', הערובה ש-`words[0] < words[m-1]` מאפשרת לשמור **אינווריאנט של טווח עולה** לאורך חיפוש בינארי.

פתרון: **סעיף א' — מימוש `strcmp_new`** הרעיון המרכזי: בונים מערך **rank** בגודל 26 (קבוע ← $\Theta(1)$ מקום נוסף) כך ש-`rank[c - 'a']` = המיקום של האות `c` בתוך `abc`. בנייתו עולה $\Theta(26) = \Theta(1)$ זמן. לאחר מכן סורקים את שתי המחרוזות תו-תו — סך-הכל $\Theta(n)$ זמן. ```c int strcmp_new(char *s1, char *s2, char *abc) { /* בניית טבלת rank — O(1) זמן ומקום (26 תאים קבועים) */ int rank[26]; for (int i = 0; i < 26; i++) rank[abc[i] - 'a'] = i; /* השוואה תו-תו לפי ה-rank */ int i = 0; while (s1[i] != '\0' && s2[i] != '\0') { int r1 = rank[s1[i] - 'a']; int r2 = rank[s2[i] - 'a']; if (r1 < r2) return -1; if (r1 > r2) return 1; i++; } /* אחת המחרוזות (או שתיהן) הסתיימה */ if (s1[i] == '\0' && s2[i] == '\0') return 0; if (s1[i] == '\0') return -1; /* s1 קצרה יותר → קודמת */ return 1; /* s2 קצרה יותר → קודמת */ } ``` **ניתוח סיבוכיות סעיף א':** - **זמן:** $\Theta(26) + \Theta(n) = \Theta(n)$ ✓ - **מקום נוסף:** מערך `rank` בגודל 26 = $\Theta(1)$ ✓ --- **סעיף ב' — מימוש `find_sorted_words`** הרעיון המרכזי: **חיפוש בינארי** עם **אינווריאנט**: בכל שלב מתקיים `words[lo] < words[hi]` (לפי abc). *הוכחת נכונות האינווריאנט:* - **בסיס:** `lo=0, hi=m-1` — מובטח ש-`words[0] < words[m-1]`. ✓ - **צעד:** נגדיר $mid = \lfloor(lo+hi)/2\rfloor$. - אם `strcmp_new(words[mid], words[hi]) == -1` (כלומר $words[mid] < words[hi]$): מציבים `lo = mid`. כעת $words[lo] = words[mid] < words[hi]$. ✓ - אחרת ($words[mid] \geq words[hi]$): מכיוון ש-$words[lo] < words[hi] \leq words[mid]$, מתקיים $words[lo] < words[mid]$. מציבים `hi = mid`. כעת $words[lo] < words[hi] = words[mid]$. ✓ - **עצירה:** כאשר `lo + 1 == hi`, האינווריאנט מבטיח $words[lo] < words[lo+1]$, כלומר `strcmp_new(words[lo], words[lo+1], abc) == -1`, ומחזירים `lo`. ✓ ```c int find_sorted_words(char *words[], int m, char *abc) { int lo = 0, hi = m - 1; /* אינווריאנט: words[lo] < words[hi] לפי abc */ while (lo + 1 < hi) { int mid = (lo + hi) / 2; if (strcmp_new(words[mid], words[hi], abc) == -1) lo = mid; /* words[mid] < words[hi] → עלייה בתחום [mid, hi] */ else hi = mid; /* words[mid] >= words[hi] → עלייה בתחום [lo, mid] */ } return lo; } ``` **ניתוח סיבוכיות סעיף ב':** - **מספר איטרציות:** בכל איטרציה הטווח $[lo, hi]$ מתחלק לשניים → $\Theta(\log m)$ איטרציות. - **עלות כל איטרציה:** קריאה ל-`strcmp_new` עולה $O(n)$ (כאשר $n$ = אורך המחרוזת הארוכה ביותר). - **זמן כולל:** $\Theta(n \cdot \log m)$ ✓ - **מקום נוסף:** משתנים `lo`, `hi`, `mid` בלבד = $\Theta(1)$ ✓