Комментарий к опросу: в прошлые годы были задачи подсчёта и сложность в среднем, интерактивные доказательства и PCP будут в курсе допглав (в любом случае подробнее, чем за пару лекций), задачи поиска - на алгоритмической теории игр в магистратуре нашей кафедры, про дерандомизацию я раньше только на спецкурсе рассказывал.