פיתוח כלים למימוש אלגוריתמים מטריים
הפרויקט הזה נועד להקים סביבה שתאפשר פיתוח מהיר יחסית של אלגוריתמים מודרניים הפועלים על מרחבים מטריים. על הסטודנט לבחור סביבת תכנות (שפת תכנות וספריות) ולפתח בסביבה זאת חבילת תוכנה שתכיל כלים אלגוריתמים בסיסיים למרחבים מטריים. בפרט על החבילה לטפל באלמנטים והפעולות הבאות ביעילות:
1. יצוג גרפים לא מכוונים ממושקלים, ופעולות מרחקים בסיסיות עליהן.
2. יצוג מרחבים אולטרמטריים בעזרת עצים.
3. יצוג תתי קבוצות סופיות במרחבים נורמיים שונים, ובפרט מרחבי ℓp .
4. מימוש של פרוקים הסתברותיים של מרחבים מטריים (CKR, Bartal, KPR ועוד).
5. מימוש של LSH.
6. מימושים של הורדת מימד JL.
7. מימוש WSPD למרחבי ממימד נמוך.
8. ועוד.
על הסטודנט יהיה להדגים את גמישות החבילה שפיתח על-ידי יישום מספר אלגוריתמים מטריים בעזרת החבילה.
הערה: פרויקט כזה יכול להוות פרויקט למספר סטודנטים, כיוון שיש הרבה כלים לפתח.