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

שימו לב: *נא להגיש רק את שאלות 1-5. שאר השאלות הן לצורך חזרה למבחן בלבד. אין צורך להגיש את התשובות להן.

1

הגדרה: נתונה סידרה $\displaystyle X=[x_{1}...x_{n}]$ של מספרים שונים זה מזה. $\displaystyle Y=[y_{1}...y_{m}]$ היא תת-סידרה עולה של $\displaystyle X$ אם: קיימת סדרה עולה ממש של אינדקסים $\displaystyle [i_{1},...,i_{m}]$ כך ש$\displaystyle x_{i_{j}}=y_{j}$ לכל $\displaystyle j$. $\displaystyle Y$ היא סידרה עולה.

דוגמה: נניח ש$\displaystyle X=[1,5,2,3]$. אם נקבע $\displaystyle Z=[1,2,3]$, אז $\displaystyle Z$ היא תת-סידרה עולה של $\displaystyle X$. גם אם נקבע $\displaystyle Z=[2,3]$ תהיה $\displaystyle Z$ תת-סידרה עולה של $\displaystyle X$.

הגדרה: אם $\displaystyle X$ היא סידרה, אז $\displaystyle Y$ היא הLIS (או longest increasing subsequence), אם היא הארוכה ביותר מבין תתי-הסדרות העולות של $\displaystyle X$.

הנח שX הוא מערך גלובלי המתאר את הסדרה $\displaystyle X$, בעלת האורך $\displaystyle n$. בשאלה זו עליך למצוא אלגוריתם יעיל למציאת אורך הLIS.

2

אנא הוכח ש$\displaystyle \sum _{j=1}^{h}[2^{-j}\Theta (j)]=\Theta (1)$.

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

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

3

בכיתה למדנו כבר על עצי חיפוש בינריים. שאלה זו עוסקת בווריאציה. עץ Foo-Bar מוגדר כך:

1. כל צומת הוא אחד משני סוגים: צומת Foo או צומת Bar.
   1. צומת Bar מחזיק מפתח אחד ו(עד ל)2 ילדים (כמו הצמתים הרגילים שראינו).
   2. צומת Foo מחזיק 2 מפתחות ו(עד ל3 ילדים.
2. העץ מקיים את את תכונת הFoo-Bar - לכל צומת x:
   1. כל מפתח בתת-עץ שמאלי של מפתח כלשהו, קטן או שווה לו.
   2. כל מפתח בתת-עץ ימני של מפתח כלשהו, גדול או שווה לו.
3. כל המסלולים משורש העץ לעלה ריק (Nil) בעל אותו אורך בדיוק.

דוגמה: צומת Bar צומת Bar.

דוגמה: צומת Foo צומת Foo.

דוגמה: עץ Foo-Bar להלן דוגמה לעץ Foo-Bar תקין. בעץ זה 3 צמתים (2 מסוג Bar, ו1 מסוג Foo). יש לו 4 מפתחות, וגבהו 2. עץ Foo-Bar.

אנא הוכח שעץ Foo-Bar הוא לוגריתמי: אם יש בו $\displaystyle n$ מפתחות וגבהו הוא $\displaystyle h$, אז $\displaystyle h=O(\log(n))$.

שימו לב: אל תתייחס לשאלה כיצד ליצור עץ כזה, או כיצד להכניס ולהוציא מפתחות ממנו - זה לא רלוונטי.

4

הגדרה: החציון של קבוצת מספרים $\displaystyle A$ מוגדר כך: נגדיר $\displaystyle A'='\{a_{1},...,a_{n}\}$ כסדרה ממוינת המורכבת מאיברי $\displaystyle A$; אם $\displaystyle n$ אי זוגי, החציון הוא האיבר האמצעי, ואם $\displaystyle n$זוגי, אז החציון הוא ממוצע שני האיברים האמצעיים.

דוגמה: החציון של $\displaystyle \{1,2,9\}$ הוא 2 (2 הוא האיבר האמצעי של איבריה הממויינים). החציון של $\displaystyle \{1,9,2\}$ הוא 2 (2 הוא האיבר האמצעי של איבריה הממויינים). החציון של $\displaystyle \{1,2,3,100\}$ הוא 2.5 (2 ו3 הם איבריה האמצעיים של איבריה הממויינים). החציון של $\displaystyle \{1,2,2,2,2,2,2,2,2,2,2,2,2,3,100\}$ הוא 2 (2 הוא האיבר האמצעי של איבריה הממויינים).

רוצים לממש ביעילות מבנה נתונים Median בעל הממשק הבא:

# Makes a Median data-structure.
Make-Median()

# Adds another value (v) to a Median data-structure (m).
Insert(m, v)

# Returns the median of all the values in
#	a Median data-structure (m).
Med(m)

להלן דוגמה לשימוש במבנה הנתונים:

# Makes a median data-structure.
m = Make-Median()

# Inserts 1.
Insert(m, 1)
# Inserts 9.
Insert(m, 9)
# Inserts 2.
Insert(m, 2)

# Prints 2 (the median of {1, 9, 2}).
Print( Med(m) )

# Inserts 100.
Insert(m, 100)

# Prints 4.5 (the median of {1, 9, 2, 100}).
Print( Med(m) )

אנא הסבר כיצד לממש את מבנה הנתונים ביעילות.

5

הסטודנט העיראקי איפ חמיס תברא מתבונן בקטע הקוד הבא:

# Makes a binary heap from an array (Values).
Build-Heap(Values)
1	bh = Make-Priority-Queue()
	
2	bh.size = Length(Values)	
	
3	for i in [1, ..., Length(Values)]
4		bh.Values[i] = Values[i]
		
5	Arrange(bh)
	
6	return bh

קטע קוד זה מקבל מערך, ומחזיר ערימה בינרית . איפ חוכך בדעתו כיצד מומשה הפונקציה Arrange. (אנו למעשה כבר ראינו את המימוש הבא:

Arrange(bh)
1	for i in [Length(bh.Values), ..., 1]
2		Bubble-Down(bh, i)

אך הוא אינו יודע זאת).

מספר אפשרויות עולות על דעתו:

Arrange(bh)
1	for i in [⌊Length(bh.Values) / 2⌋, ..., 1]
2		Bubble-Down(bh, i)

Arrange(bh)
1	Merge-Sort(bh.Values)

Arrange(bh)
1	for i in [1, ..., Length(bh.Values)]
2		Bubble-Down(bh, i)

Arrange(bh)
1	for i in [1, ..., Length(bh.Values)]
2		Bubble-Up(bh, i)

Arrange(bh)
1	for i in [Length(bh.Values), ..., 1]
2		Bubble-Up(bh, i)

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

6

נניח שנתנה לך פונקציה יעילה LCS(X, Y) הפותרת את בעיית תת-המחרוזת המשותפת הארוכה ביותר. אנא הצע אלגוריתם יעיל Convert(X) המקבל מחרוזת, ומחזיר מחרוזת שתקיים תמיד שLCS(X, Convert(X)) הוא אורך תת-המחרוזת העולה הארוכה ביותר של X.

אנא הוכח את נכונות תשובתך, ונתח את סיבוכיות הפונקציה Convert במונחי ארכו של X.

7

בשאלה זו עליך להוכיח חסם תחתון על $\displaystyle T(n)$, מספר עצי החיפוש הבינריים השונים בעלי $\displaystyle n$ מפתחות שונים זה מזה.

דוגמה: נניח שעץ החיפוש מכיל את המפתחות $\displaystyle 1,2$. יש 2 עצים מתאימים: עצי חיפוש בינריים בעלי המפתחות 1 ו2. נניח שעץ החיפוש מכיל את המפתחות $\displaystyle 1,2,3$. יש 5 עצים מתאימים: עצי חיפוש בינריים בעלי המפתחות 1, 2, ו3.

מהדוגמה נוכל להסיק כי

$\displaystyle T(0)=T(1)=1$, $\displaystyle T(2)=2$, $\displaystyle T(3)=5$.

אנא הוכח ש$\displaystyle T(n)=\Omega (2^{n})$, כלומר שמספר עצי החיפוש הבינריים גדל בצורה אקספוננציאלית.