سوالات مدل ناآگاه از کش (داده‌های حجیم)

۱- برعکس کردن یک آرایه بدون حافظه‌ی اضافی (حافظه O(1))

جواب: از دو طرف scan می‌کنیم و به جای هم می‌نویسیم. (با توجه به اینکه LRU استفاده می‌شود این هم زمانش به اندازه‌ی scan می‌شود.)

۲-درخت بی در مدل ناآگاه از کش: از ترکیب چینش van Emde Boas و استفاده از اشاره‌گر در هر گره ساخته می‌شود. (مشابه فایل مرتب)

زمان حذف و درج در فایل مرتب lg^2 N /B می‌شود که برای درخت بی هم هست فقط زمان جستجوی این log_B N می‌شود. (سرشکن)

۳-هرم در مدل ناآگاه از کش

جواب: مثل روش لگاریتمی و مرتب‌سازی در مدل ناآگاه از کش عمل می‌کنیم. یک سری قیف و یک سری بافر نگه می‌داریم که از نظر سایز هر بار ۲ برابر می‌شوند (نزدیک خروجی کوچکترند) و برای حذف آن مشابه هرم در مدل I/O عمل می‌کنیم.

هزینه‌ی درج و حذف کوچکترین عنصر در آن O(1/B log_{M/B} N/B) است (سرشکن).

۴-لیست پیوندی: فکر کنم این است که لیست‌ها را به زیرلیست‌های r عنصری تقسیم می‌کند و مشابه فایل مرتب (پویا) با آن رفتار می‌کند.