حل تمرین گسترگراف

من یک حل که برای سوال ۱ تمرین ۲ پیدا کردم خیلی طولانی بود:
http://math.mit.edu/~jorloff/suppnotes/suppnotes03/ls3.pdf
برای سوال ۲ تمرین ۲ هم تعداد تکرارهایی که برای همگرا شدن لازم داشت لگاریتمی بود (چون با احتمال ثابت موفقیت‌آمیز بود) ولی الگوریتم اصلی (که در سوال آمده) ضریبش نسبت مقدار ویژه‌های اول و دوم است (به ترتیب از بزرگ به کوچک).
https://en.wikipedia.org/wiki/Power_iteration#Analysis

جوک در مورد گسترگراف!

ارتباطش با گسترگراف: اون شکلی که به فیزیکدانه نشون میده. جوابش توی مبحث قدم‌زدن تصادفی هست.

کامل‌ترین جزوه‌ی تراویسان (گسترگراف)

https://people.eecs.berkeley.edu/~luca/expanders2016/index.html

اثبات قضیه‌ی آخر فصل ۳ گسترگراف تراویسان (نسخه برکلی!)

دریافت

از روی اینترنت:

https://people.eecs.berkeley.edu/~luca/expanders2016/lecture05.pdf

درس گسترگراف شایان اویس قرن

http://homes.cs.washington.edu/~shayan/courses/cse599/

درس گسترگراف در استنفورد (تراویسان)

علاوه بر درسی که در برکلی داده در استنفورد هم این را ارائه کرده است.
http://theory.stanford.edu/~trevisan/expander-online/lecture02.pdf

رمز موفقیت استادها

هیچ وقت از آن چیزی که درس می‌دهند سوال نمی‌دهند.

مسخره است، آدم یک درس را می‌خواند سوالها از یک درس دیگر هستند و کسی که سر کلاس نمی‌آید و فقط آن را می‌خواند بهترین نمره را می‌گیرد ولی هیچی یاد نمی‌گیرد.

spectral graph theory

https://ocw.mit.edu/courses/mathematics/18-409-topics-in-theoretical-computer-science-an-algorithmists-toolkit-fall-2009/lecture-notes/

تمرین 1 نظریه طیفی گراف (ام آی تی)

https://ocw.mit.edu/courses/mathematics/18-409-topics-in-theoretical-computer-science-an-algorithmists-toolkit-fall-2009/assignments/MIT18_409F09_ps1.pdf

حراج ژاپنی

اگر در حراج ژاپنی آخرین نفرات همزمان با هم بشینند چه کسی برنده می‌شود؟

حتی اگر نوع دیگری هم باشد این مشکل پیش می‌آید..

گفته احتمالش صفر است! :))