大学院
過去（2023年度）の授業の情報です
学内のオンライン授業の情報漏洩防止のため，URLやアカウント、教室の記載は削除しております。
最終更新日：2024年4月22日
授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。
最終更新日：2024年4月22日
授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。
情報理工学英語特別講義Ⅵ
Special Lecture in Information Science and Technology Ⅵ
Advanced data structures
Data structures are ubiquitous (think of "google search" and/or "google map"), and the goal of this course is to give a broad overview of various fundamental and recent developments in this field. We will cover various techniques/principles of efficient data structure design along with applications of these techniques in optimizing problems in graphs, strings, arrays, etc. Students will also have the opportunity to work on the frontier of research
problems.
problems.
時間割／共通科目コード
コース名
教員
学期
時限
4893-1006
GIF-CO5026L3
情報理工学英語特別講義Ⅵ
定兼 邦彦
水曜4限
マイリストに追加
マイリストから削除
講義使用言語
英語
単位
2
実務経験のある教員による授業科目
NO
他学部履修
不可
開講所属
情報理工学系研究科
授業計画
1. Introduction and overview of the course.
2. Compact data structures including classical implicit data structures
3. Succinct data structures
4. Applications of compact structures in graph algorithms
5. Range minimum queries, lowest common ancestor queries, and their applications
6. Set intersection data structures and their applications in hardness proofs
7. Range search data structures
8. Predecessor search data structure
9. Suffix array and suffix tree
10. Hashing
11. Dynamic data structures
12. Data structure lower bounds
授業の方法
The lectures are given in English.
成績評価方法
The grade is evaluated by a report submitted at the end of the course.
教科書
There will not be any textbook for the course, but I will mention relevant literature at the end of each class.
参考書
None.
履修上の注意
The lectures are given in English.
