מערך A בגודל n נקרא "יוני-מודאלי" (Unimodal) אם הסדרה עולה עד לאיבר מקסימלי מסוים ("הפסגה") ואחריו יורדת. לדוגמה: {1,2,4,9,12,8,5} (הפסגה היא 12). מותר להניח שכל איברי המערך שונים זה מזה. הפסגה יכולה להיות גם בקצה (מקרה מונוטוני).
א. (10 נק') כתבו אלגוריתם המוצא את האינדקס של האיבר המקסימלי (הפסגה) במערך יוני-מודאלי בזמן O(logn). הסבירו בקצרה את נכונות האלגוריתם.
ב. (8 נק') נתון מערך יוני-מודאלי. תארו בקצרה אלגוריתם למיון המערך בזמן לינארי (O(n)). ניתן להשתמש במערך עזר. הסבירו בקצרה את נכונות האלגוריתם.
ג. (7 נק') נתון מערך כלשהו של n מספרים שונים (לאו דווקא יוני-מודאלי). הוכיחו שלא ניתן להפוך אותו ליוני-מודאלי (כלומר לשנות את סדר איבריו כך שהוא יהיה יוני-מודאלי) בזמן o(nlogn) (או קטנה של nlogn).
הערה: המספרים בכל הסעיפים לאו דווקא שלמים.