情報科学部Faculty of Computer and Information Sciences
PRI210KA-CS-161e（情報学基礎 / Principles of informatics 200）データ構造とアルゴリズム演習Data Structures and Algorithms Lab
黄 潤和
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 情報科学部Faculty of Computer and Information Sciences |
| 添付ファイル名Attached documents | |
| 年度Year | 2022 |
| 授業コードClass code | J0436 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 春学期授業/Spring |
| 曜日・時限Day/Period | 月2/Mon.2 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 / Koganei |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | |
| 単位数Credit(s) | 1 |
| 備考（履修条件等）Notes | |
| 他学部公開科目Open Program | |
| 他学部公開（履修条件等）Open Program (Notes) | |
| グローバル・オープン科目Global Open Program | |
| 成績優秀者の他学部科目履修制度対象Interdepartmental class taking system for Academic Achievers | |
| 成績優秀者の他学部科目履修（履修条件等）Interdepartmental class taking system for Academic Achievers (Notes) | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| SDGsCPSDGs CP | |
| アーバンデザインCPUrban Design CP | |
| ダイバーシティCPDiversity CP | |
| 未来教室CPLearning for the Future CP | |
| カーボンニュートラルCPCarbon Neutral CP | |
| 千代田コンソ単位互換提供（他大学向け）Chiyoda Campus Consortium | |
| 選択・必修Optional/Compulsory | |
| カテゴリー（2022年度以降入学者）Category (2022~) | |
| カテゴリー（2021年度以前入学者）Category (~2021) | |
| カテゴリーCategory |
専門教育科目 専門科目 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
This is an exercise course for further understanding of "data structures and algorithms". We aim that you understand more accurately and deeply what you have learned in the lecture course. Throughout this exercise, you should have a solid understanding of the data structures and algorithms.
The goal of this exercise course is to understand "fundamentals of data structures and algorithms" that is among minimum requirements to study information sciences, trace pseudo-codes step(line)wise, and be able to demonstrate data changes and branching behavior of algorithms. Another objective is to be able to think in an algorithmic manner.
Besides attending this exercise course, students are expected to read the materials beforehand to prepare for the exercises. After each class, students are expected to continue the incomplete exercises and assignments. Students will be studying four hours for a class.
The letter grades of this course are P (pass) and F (fail).
Grading will be decided based on final report (40%) and in class exercises (60%).
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
本授業は，「データ構造とアルゴリズム」の理解をより深めるための演習科目です．本科目を履修することによって，講義科目で学んだことを、より正確に，より深く理解することを目的としています．本演習を通して，データ構造と，そのアルゴリズムについての学びがしっかりとしたものになるはずです．
到達目標Goal
情報科学を学ぶ上で最低限必要な「アルゴリズムとデータ構造の基礎」を理解し，擬似コード (pseudo-code) を1ステップ (行) 毎に追いかけて，データの変化やアルゴリズムの分岐を示すことができる能力を身につけることを目標とします．また，アルゴリズムの考え方を身につけることももう一つの目標とします．
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち「DP1」と「DP2」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
講義科目でならった内容について確認をし，関連する演習問題を解くことで進めていきます。提出された演習問題の正誤に関するフィードバックを随時実施します。
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
なし / No
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
1[対面/face to face]：ガイダンス・疑似コード
アルゴリズムとは何か，データ構造とは何か，擬似コードの読み方
2[対面/face to face]：実行時間
高次関数，指数関数などの実行時間
3[対面/face to face]：帰納法・漸化式
漸化式，漸化式を用いたアルゴリズムの解析
4[対面/face to face]：挿入ソート
挿入ソートと，その擬似コードのトレース
5[対面/face to face]：マージソート
マージソートと，その擬似コードのトレース，分割統治法
6[対面/face to face]：基本的なデータ構造 (1)
スタック，キュー，リスト
7[対面/face to face]：基本的なデータ構造 (2)
リスト，木構造
8[対面/face to face]：ヒープソート
ヒープソートと，その擬似コードのトレース，ヒープ木
9[対面/face to face]：クイックソート
クイックソートと，その擬似コードのトレース，乱択アルゴリズム
10[対面/face to face]：中間まとめ
4つのソートの復習やその比較
11[対面/face to face]：ハッシュ表と二分探索木
ハッシュ関数，ハッシュの計算，二分探索木の擬似コードのトレース
12[対面/face to face]：アルゴリズムの復習
実行時間，ソートなどの復習
13[対面/face to face]：データ構造の復習
データ構造(スタック，キュー，リスト，ハッシュ，二分探索木)の復習
14[対面/face to face]：最終課題
学んだ知識やスキルの整理
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
予習としては、講義資料をよく読み、演習に備えてください。復習としては、授業時間内で終わらなかった演習に取り組むと共に、毎回の宿題に取り組む必要があります。
本授業の準備・復習等の授業時間外学習は、各週につき4時間を標準とします。
テキスト（教科書）Textbooks
書名: アルゴリズムイントロダクション 第3版 第1巻 (基礎・ソート・データ構造・数学)
著者: Thomas H. Cormen他
翻訳：浅野他
出版社: 近代科学社
出版年: 2012年
参考書References
書名: Introduction to Algorithms, Third Edition
著者: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
出版社: The MIT Press
出版年: 2009年
成績評価の方法と基準Grading criteria
本科目はP/F評価科目です。
授業内演習 (60%)、最終課題レポート (40%)で成績評価を行います。
学生の意見等からの気づきChanges following student comments
アルゴリズムの考え方が身につく演習を増やす。
学生が準備すべき機器他Equipment student needs to prepare
"データ構造とアルゴリズム"の講義資料、筆記用具。必要に応じて貸与ノートPCを用いる。