מבני נתונים ואלגוריתמים - מחברת קורס/שיעורי בית 1/שאלות

שימו לב: *נא להגיש רק את שאלות 1-5. שאלה 6 שייכת למעשה לקורס חדו"א. אנא וודאו שהנכם מבינים את המשפט, אך אין צורך להגיש את התשובה. שאר השאלות הן לצורך חזרה למבחן בלבד. אין צורך להגיש את התשובות להן.

1

אנא הוכח או הפרך את הטענות הבאות:

1. $\displaystyle 80=O(3\cdot n)$.
2. $\displaystyle 2^{n+1003}+30=O(2^{n})$.
3. $\displaystyle 2\cdot n+7=O(2\cdot n+3)$.
4. $\displaystyle 3\cdot n=O(1)$.
5. $\displaystyle \log _{2}(n)=O(\log _{10}(n))$.

שימו לב: הכוונה בסעיף הראשון לפונקציה הקבועה $\displaystyle f(n)=80$,‏ ולא לקבוע 80.

2

נתונות שתי פונקציות:

$\displaystyle f(n)=n+c_{1}n\log ^{2}(n)$
$\displaystyle g(n)=n+c_{2}n^{2}$
כאשר $\displaystyle c_{1}>c_{2}>0$.

1. האם $\displaystyle f(n)=O(g(n))$?
2. האם $\displaystyle g(n)=O(f(n))$?

3

נתבונן בפסוודו-קוד הבא:

Foo(n)
1	Bar-1(n)
2	Bar-2(n)
3	Bar-3(n)

נתון:

1. זמן הריצה של Bar-1(n) הוא $\displaystyle \Omega (n^{2}\log(n))$.
2. זמן הריצה של Bar-2(n) הוא $\displaystyle \Theta (n^{2})$.
3. זמן הריצה של Bar-3(n) הוא $\displaystyle O(n)$.

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

1. זמן הריצה של Foo(n) הוא $\displaystyle \Omega (n)$.
2. זמן הריצה של Foo(n) הוא $\displaystyle \Omega (n^{3})$.
3. זמן הריצה של Foo(n) הוא $\displaystyle O(n^{3})$.

4

אנא כתוב מימוש יעיל לפונקציה Find-Num-In-Range(A, a, b), המקבלת:

1. מערך ממויין A של מספרים שלמים חיוביים
2. מספר שלם חיובי a
3. מספר שלם חיובי b גדול ממש מa

ומחזירה את מספר האיברים בA שכל אחד מהם נמצא בתחום $\displaystyle [a,b)$.

דוגמה: אם A = [1, 2, 4, 5, 99 , 11999], אז Find-Num-In-Range(A, 3, 99) תחזיר 2 (יש שני איברים בתחום).

• הערה: אנא מצא מימוש הפועל בזמן לוגריתמי באורך המערך.

5

להלן הפונקציה Merge המקבלת שני מערכים ממויינים:

# Merge. 
# Takes two sorted arrays (L, R).
# Returns a sorted array of L ∪ R.
Merge(L, R)
1	Merged = Make-Array( Length(L) + Length(R) )
	
2	l = r = m = 1
	
3	while l <= Length(L) or r <= Length(R)
4		if r > Length(R)
5			Merged[m++] = L[l++]
6		else if l > Length(L)
7			Merged[m++] = R[r++]
8		else if L[l] < R[r]
9			Merged[m++] = L[l++]
10		else
11			Merged[m++] = R[r++]

12	return Merged

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

6

אנא הוכח אחד מחסמי האינטגרלים הבאים (שתי ההוכחות דומות מאד זו לזו):

1. אם $\displaystyle f(n)$ מונוטונית לא יורדת, אז $\displaystyle \int _{m-1}^{n}f(x)dx\leq \sum _{i=m}^{n}[f(i)]\leq \int _{m}^{n+1}f(x)dx$
2. אם $\displaystyle f(n)$ מונוטונית לא עולה, אז $\displaystyle \int _{m}^{n+1}f(x)dx\leq \sum _{i=m}^{n}[f(i)]\leq \int _{m-1}^{n}f(x)dx$

7

$\displaystyle f(n)$ ו$\displaystyle g(n)$ הן פונקציות חיוביות ממש, והגבול $\displaystyle lim_{n\rightarrow \infty }[f(n)/g(n)]$ קיים ושווה ל$\displaystyle lim_{n\rightarrow \infty }[f(n)/g(n)]=c$. אנא הוכח או הפרך את הטענה הבאה: אם $\displaystyle c=0$ או $\displaystyle c=\infty$,‏ אז $\displaystyle f(n)\neq \Theta (g(n))$.

8

אנא הוכח או הפרך כ"א מהכללים הבאים:

1. $\displaystyle f(n)+g(n)=\Theta (\max\{f(n),g(n)\})$
2. $\displaystyle f(n)-g(n)=\Theta (\max\{f(n),g(n)\})$

9

$\displaystyle f(n)$ היא פונקציה חיובית ממש, מונוטונית עולה, ושואפת לאינסוף. אנא הוכח שקיימת פונקציה $\displaystyle g(n)$ כך שמתקיים $\displaystyle f(n)=\Theta (g(n))$ אבל הגבול $\displaystyle f(n)/g(n)$ אינו קיים.