1. גרפים
1.1. הגדררות: גשר, G_BI , רכיב דו קשירות, קודקודים דו קשורים,
1.2. מציאת רכיבי דו קשירות. מאפיינים את הגשרים (ואז אפשר להוריד אותם ומצוא רכיבי קשירות בG_BI מריצים DFS עם קשתו וקשתות אחוריות שמים ערך L גובה וערך K שהוא המקום הכי גבוה שאני או הבני שלי משורשים עליו. אם K שווה או קטן מL אז הצלע שאני הסוך שלה היא גשר.
1.3. חתך מינימלי: אלגוריתם הסתברותי מורידים צלע ומחבירים בין הקודקודים.מחזירים את מספר הצלעות בין השניים האחרונים שנשארו . הסתברותי נחזור מספיק פעמים ונחזיר את המינימום זה יצא קרוב
2. מנוע החיפוש
2.1. בניית SA - מערך סייפות ממויין. באופן רקורסיבי ממינים את אינדקסים אחד ושתים מוד 3 ואז ממזגים את הערך השלישי. המיון הוא לעשות מחרוזת ומחרוזת מוזזת באחד. מיון ספירה לכמה קטנים ממני. שרשרור של הערכים
2.2. בנתיית LCPA מערך בין כל זוג שכנים ב SA
2.3. בניית LCP מינימום בין ערכים של ה LCPA
2.4. שאילתא היא חיפש בינארי בSA בעזרת ה LCP
2.5. טענות עזר
3. תרגילי בית
3.1. בונוס 1- נקודות וערכים
3.2. בונוס 2 פאקמן
3.3. בונוס 3 גשרים
4. רשימת דילוגים
4.1. רגילה
4.2. הסתברותית
5. RMQ + LCA
5.1. RMQ
5.1.1. 1. לא מכינים כלום (1,n,n)
5.1.2. 2. בודקים הכל לפני (n^2,1,n^2)
5.1.3. 3 בודקים בלוקים בגודל שורש (n,n^0.5,n)
5.1.4. 4. בודקים מכל איבר חזקות של 2 (nlogn,1,nlogn)
5.1.5. * עבור מערך שההפרשים הם רק אחד. בלוקים חצי לוג, בלוק שמור לתוצאות ומכל בלוק עושים קנוני על כולם עיבוד מקדים של 4. מספר הבלוקים הקנונים חסום (n,1,n)
5.2. LCA
5.2.1. 1 בודקים מהנמוך לשורש ואז מהשני (n,n,n(
5.2.2. 2. עולים עד שמשווים רמות ואז עולים ביחד (n,n,n(
5.2.3. 3. מחלקים לקבוצת של שורש הגובה. שומרים לכל קודקוד חיבור לתחתון בקבוצה מעליו. עולים קפיצות כגולות עד לאב משותף חוזרים אחורה ועולים במקביל. (n,n^0.6 ,n)
5.2.4. 4. מכל קודקוד מוצאים את כל החקות של 2. נשוואה גבהים ואז נקפוץ עד לאב משותף כל פעם מהחזקה הגבוה עד לנמוכה עושים רק אם מתאים (nlogn,nlogn,nlogn)
5.2.5. 5. סריקה של DFS של העץ הופכת למערך עם הפרשים של 1 ואז נפעיל RMQ *
6. זמן ריצה שורש
6.1. טבלת אותיות
6.1.1. למצוא זוג הכי קרוב. שילוב של לבדוק את כל הזוגות של אותה אות והרצת BFS במקביל מכל המופעים. כשיש יותר משורש N אז עושים את השני. אן שורש אן
6.2. MO
6.2.1. שאילתות על מקטעים מהמערך ידועות מראש. מיון השאילתות קודם לפי הבלוק בגודל שורש N של ההתחלה ואז לפי המיקום של הסוף. עונים לפי הסדר הממויון ומחזיקים לפי הסדר הרגיל. זמן של אנ שורש אנ הפאנץ הוא בהוחכת זמן ריצה - מסתכלים על התזוזות של הקצה השמאלי והימני.
6.3. סכומים אפשריים
6.3.1. יש סדרה של טבעיים (עם כפילויות) רוצים את כל הסכומים שאפשר להגיע איתם. תכנון דינאמי- ראשון כל המספרים כל הסכומים. שני עושים רק איברים יחידים וחוסכים זמן ריצה כי מספר האיברים השונים חסום בשורש הסכום