סעיף א':
נתון מערך A המכיל n מילים באנגלית. כל מילה היא באורך של 10 אותיות לכל היותר. הציעו אלגוריתם הקובע האם במערך A קיימות שתי מילים שהן בלבול אותיות (אנגרמות) זו של זו. על האלגוריתם לרוץ בזמן \(O(n)\) במקרה הגרוע.
לדוגמה, המילים "TEAR" ו-"RATE" הן בלבול אותיות זו של זו.
נתחו את סיבוכיות ונכונות האלגוריתם שהצעתם בקצרה.
ניתן להניח שהמערך מכיל מילים ייחודיות (ללא חזרות) וכי באלפבית האנגלי יש 26 אותיות.

סעיף ב':
נתונה רשימה מקושרת חד-כיוונית וממוינת L, המכילה n מספרים.

1. מהו זמן הריצה במקרה הגרוע עבור חיפוש איבר ברשימה L?

כדי לשפר את זמן החיפוש, הוצעה שיטה חדשה: בניית רשימה נוספת, L', שתכיל מצביעים לכ-\(\sqrt{n}\) איברים מתוך L, החל מהאיבר הראשון ועד לאחרון, בקפיצות של כ-\(\sqrt{n}\) איברים.
לדוגמה, אם L מכילה 100 איברים, L' תכיל כ-10 איברים: מצביעים לאיבר הראשון, העשירי, העשרים, וכן הלאה, עד לאיבר האחרון.

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

3. הציעו דרך לייעל את החיפוש על ידי הוספת רמה נוספת של רשימה, L''. הסבירו מה תכיל כל רמה (L, L', L''), כיצד יתבצע החיפוש, ומה תהיה סיבוכיות זמן הריצה במקרה הגרוע. אין צורך לכתוב קוד, אלא רק לתאר את האלגוריתם באופן מילולי, ברור ומדויק.