מבוא למדעי המחשב מ'/ח'

שאלה 1 25 נק' — סיבוכיות

לכל סעיף ציינו סיבוכיות זמן וסיבוכיות מקום נוסף, בסימון Θ, כפונקציה של n. חובה לפשט את הביטוי ככל שניתן. הניחו כי סיבוכיות הזמן והמקום של printf ו-free היא Θ(1), וכי סיבוכיות הזמן של malloc(n) היא Θ(1) וסיבוכיות המקום שלה היא Θ(n). הניחו כי sqrt פועלת בזמן Θ(1).

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

א.

void f1(int n) {
    for (int i = 1; i < n; i++)
        for (int j = i; j < n; j *= 2)
            printf("*");
}

ב.

void f2(int n) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 1; k < n; k *= 2)
                printf("*");
}

ג.

void f3(int n) {
    for (int i = 0; i < n; i++)
        for (int j = 2; j < n; j = j * j)
            printf("*");
}

שאלה 2 25 נק'

נתון מערך arr באורך n של מספרים שלמים, הממוין בסדר לא-יורד, ומספר שלם x. ייתכנו ערכים שליליים וערכים חוזרים.

על הפונקציה להחזיר את מספר הזוגות (i, j) המקיימים 0 ≤ i < j < n וגם arr[i] + arr[j] < x.

• ניתן להניח כי הקלט תקין וכי n ≥ 1.
• אין לשנות את תוכן המערך ואין להקצות זיכרון דינמי.
• שימו לב לדרישת הזמן. מספר הזוגות עצמו יכול להיות Θ(n²) — לכן אי-אפשר לספור אותם אחד-אחד, ומצד שני חיפוש בינארי לכל i ייתן Θ(n log n) ואינו עומד בדרישה.

שאלה 3 25 נק'

נתונה מחרוזת s באורך n המכילה אך ורק את התווים 'a', 'b', 'c', 'd'.

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

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

• אין לשנות את תוכן המחרוזת s, אפילו לא באופן זמני.
• ניתן להניח כי הקלט תקין וכי s אינה ריקה.
• מערך בגודל קבוע (שאינו תלוי ב-n) נחשב מקום Θ(1).
• רמז: מה שקובע הוא רק הזוגיות של ארבעת המונים בכל קידומת — יש מספר קבוע של מצבי זוגיות אפשריים.

שאלה 4 25 נק' — רקורסיה

נתונים שני מערכים של מספרים שלמים, שניהם ממוינים בסדר לא-יורד: a באורך na ו-b באורך nb.

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

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

איך עובדים כאן

• כתבו בעורך שמשמאל. שלושה קבצים, לשונית לכל שאלה. אל תשנו את main.
• הרץ בדיקות מריץ את הפונקציה שלכם מול מקרי הבדיקה של השאלה — כולל בדיקות של האילוצים (לולאות ברקורסיה, שינוי הקלט, פונקציית מעטפת).
• סיבוכיות אינה נבדקת אוטומטית. פתרון שעובר את כל הבדיקות בסיבוכיות שגויה — נכשל בשאלה.
• בסיום לחצו סיום והגשה, שמרו את קובץ ההגשה, ובקשו מ-Claude ציון עם /grade.