שאלות מבחן

הנחות

1. ניתן להשתמש בטיפוס bool ובפונקציה malloc ללא שימוש ב-include#.
2. ניתן להניח שסיבוכיות הזמן של malloc(n) היא $\Theta(1)$ לכל n.
3. שלום שלום, ( \Theta = 5 ).
4. למשל אפשר לקבל \( x = 5 \)
5. ואולי גם אפשר לכתוב \( \theta(5) = 5 \)

שאלה 1

נתון מערך שלמים שאורכו n, בו כל האיברים אי-שליליים (גדולים/שווים ל-0) וקטנים ממש מקבוע x נתון. נגדיר מערך k-יחודי בתור מערך בו אם האיבר a מופיע, כל המספרים שבמרחק k ממנו לא מופיעים. כלומר, בהנתן איבר a במערך k-יחודי, האיברים הבאים לא מופיעים:

למשל, המערך הבא הוא 2-יחודי, ואינו 3-יחודי:

סעיף א

כתבו פונקציה המקבלת מערך ואורכו, וקובעת האם הוא 1-יחודי. על הפתרון לעמוד בדרישות סיבוכיות זמן \( \Theta(n + x) \) וסיבוכיות מקום \( \Theta(x) \).

פתרון

ננסה לפרק את הדרישה. מערך 1-יחודי הוא מערך בו אם המספר a מופיע, המספרים a - 1 ו-a + 1 אינם מופיעים. השאלה מאפשרת להשתמש בסיבוכיות מקום $\Theta(x)$ - זו אינדיקציה טובה מאוד להשתמש במערך באורך $x$. אפשר להשתמש במערך כזה על מנת לסמן את האיברים שכבר פגשנו בדגל בוליאני - בהגעה לאיבר a, נבדוק האם פגשנו כבר את האיברים a - 1 ו-a + 1. כמו כן, נבדוק האם a לא מופיע פעמיים. נבדוק בזהירות את האינדקסים על מנת לוודא שאנחנו לא חורגים מגודל המערך ונקבל את הפתרון הבא:

bool is_one_unique(int* arr, int n, int x) {
    bool* visited = malloc(sizeof(bool) * x);
    for(int i = 0; i < x; i++) {
        visited[i] = false;
    }
    bool is_unique = true;
    for(int i = 0; i < n; i++) {
        int a = arr[i];
        if((a >= 0 && visited[a - 1]) ||
            (a < x - 1 && visited[a + 1]) ||
            visited[a]) {
            is_unique = false;
            break;
        }
        visited[a] = true;
    }
    free(visited);
    return true;
}

מבחינת סיבוכיות, הפונקציה שלנו מבצעת שתי לולאות של x ו-n איטרציות בהתאמה, ובכל אחת מבצעת מספר קבוע של פעולות, ולכן סיבוכיות הזמן היא אכן $\Theta({n+x})$. סיבוכיות המקום היא $\Theta(x)$.

סעיף ב

כתבו פונקציה שמקבלת את אותם הפרמטרים ומחזירה האם מערך הוא k-יחודי. על הפתרון לעמוד בסיבוכיות זמן של $\Theta({nk + x})$.

פתרון

הגישה לא מאוד שונה מהסעיף הקודם. טריק חשוב שניתן ללמוד בשאלה הוא להשתמש בסיבוכיות הזמן המבוקשת בשביל להבין מה הפתרון הנדרש. בשביל לקבוע האם מערך הוא k-יחודי כש-$1 = k$, קיבלו סיבוכיות של $\Theta({n+x})$, השקולה ל-$\Theta({nk+x})$ עבור $1=k$. לכן נדרש רק להתאים מעט את הגישה שלנו. לכל מספר a במערך, במקום לבדוק אותו רק מול שני שכניו המיידים, כעת יש לבדוק אותו מול k שכניו - זה יהפוך ל-$nk$ בשתי לולאות מקוננות:

bool is_one_unique(int* arr, int n, int x) {
    bool* visited = malloc(sizeof(bool) * x);
    for(int i = 0; i < x; i++) {
        visited[i] = false;
    }
    bool is_unique = true;
    for(int i = 0; i < n; i++) {
        int a = arr[i];
        int start = (a - k < 0) 0 : a - k;
        int end = (a + k >= x) ? x - 1 : a + k;
        for(int j = start; j <= end; j++) {
            if(visited[j]) {
                is_unique = false;
                break;
            }
        }
        visited[a] = true;
    }
    free(visited);
    return true;
}

שאלה 2

נתוך מערך שלמים באורך n. לכל אינדקס i במערך, נגדיר פונקציה $f(i)$ שערכה הוא ההפרש בין סכום האיברים בין 0 ל-i (כולל) לבין סכום האיברים בין i + 1 ל-n - 1:

למשל, עבור המערך [1, 5, 3-, 10, 2] והאינדקס i = 1, מתקיים:

כתבו פונקציה המקבלת מערך ואורכו ומחזירה את האינדקס עבורו $f(i)$ מינימלית. אם יש מספר אינדקסים $i,j$ עבורם $f(i) = f(j)$ ניתן להחזיר כל אחד מהם. על הפתרון שלכם לעמוד בסיבוכיות זמן $\Theta(n)$ וסיבוכיות מקום $\Theta(1)$.

פתרון

זו שאלה שדורשת מעט להתחכם עם הגישה שלנו. פתרון אחד יכול להיות לחשב מפורשות את $f(i)$ לכל $i$ בגבולות המערך ולקחת את המינימלי - עם זאת, זה לא עומד בדרישות הסיבוכיות (חישוב n פעמים סכום של כל המערך יגיע לסיבוכיות $\Theta(n^2)$). עם זאת, נשים לב שאם נעשה חישוב עזר קטן של סכום איברי המערך, נוכל לחסוך חישוב חוזר בכל איטרציה. נסמן:

1. $s$ יהיה סכום כל המערך (אותו ניתן לחשב בריצה אחת על איברי המערך ב-$\Theta(n)$)
2. $_1p$ יהיה סכום איברי המערך מ-0 ועד i כלשהו (האיבר הראשון ב-$f(i)$)
3. $_2p$ יהיה סכום איברי המערך מ-i + 1 ועד n - 1 (האיבר השני ב-$f(i)$)

בהנחה שחישבנו את $s$ ו-$_1p$, מתקיים:

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

int min_f(int* arr, int n) {
    int sum = 0;
    for(int i = 0; i < n; i++) {
        sum += arr[i];
    }
    int s1 = 0, s2;
    int min_val = INT_MAX;
    int min_index = 0;
    for(int i = 0; i < n; i++) {
        s1 += arr[i];
        s2 = sum - s1;
        if(s1 - s2 <= min_val) {
            min_val = s1 - s2;
            min_index = i;
        }
    }
    return min_index;
}

שאלה 3

בהנתן מערך ממוין arr, נגדיר נקודת שבת בתור אינדקס i עבורו מתקיים arr[i] = i. כתבו פונקציה שמקבלת מערך ואורכו ומחזירה אינדקס של נקודת שבת אם קיימת, אחרת 1-. על הפתרון לעמוד בסיבוכיות זמן של $\Theta(\log n)$ וסיבוכיות מקום $\Theta(1)$.

פתרון

שאלה 4

נתון מערך מספרי int באורך n.