| 授業科目名 | 年度 | 学期 | 開講曜日・時限 | 学部・研究科 | 全担当教員 | 単位数 |
|---|---|---|---|---|---|---|
| 34616:データ構造とアルゴリズム(G1) | 2019 | 春セメスター | 金3 | 情報理工学部 | 白 楊 | 2 |
キャンパス
授業施設
授業で利用する言語
授業の概要と方法
受講生の到達目標
* understand and be able to explain the basics of problem solving using computer's algorithms
* understand and be able to explain the basics of algorithm complexity analysis.
* be able to select and apply the most appropriate data structures and algorithms to solve a given problem.
* understand and be able to effectively implement various data structures and algorithms for problem solving.
事前に履修しておくことが望まれる科目
'Programming Language'
'Programming Practice I'
'Computing Mathematics'
'Mathematical Foundations for Computer Science'
授業スケジュール
| 授業回数/ 担当教員（複数担当の場合） |
テーマ |
|---|---|
| キーワード・文献・補足事項等 | |
| w01 | Algorithm Analysis (Chapter 3) |
asymptotic analysis, big-oh notation, comparative analysis |
|
| w02 | Recursion (Chapter 4) |
examples, analysis, tail recursion, linear/binary/multiple recursion |
|
| w03 | Array-Based Sequences (Chapter 5) |
python sequence types, low-level arrays, dynamic arrays, multi-dimensional data sets, examples |
|
| w04 | Stacks, Queues, and Deques (Chapter 6) |
definitions, implementations, reversing data using stacks, circular arrays |
|
| w05 | Linked Lists (Chapter 7) |
singly/doubly/circularly linked lists, positional lists, sorting positional lists, link-based vs array-based sequences |
|
| w06 | Trees (Chapter 8) |
definition, depth and height, binary trees, tree traversals algortihms |
|
| w07 | Priority Queues (Chapter 9) |
definition, heaps, sorting with a priority queue |
|
| w08 | Mid-term Review and Quiz |
w01-w08 review and short test |
|
| w09 | Maps, Hash Tables, and Skip Lists (Chapter 10) |
maps and dictionaries, hash functions, sorted maps, skip list, sets, multisets and multimaps |
|
| w10 | Search Trees (Chapter 11) |
binary/balanced search trees, AVL/Splay/(2,4)/Red-Black Trees |
|
| w11 | Sorting and Selection (Chapter 12) |
merge sort, quick sort, selection prune-and-search |
|
| w12 | Text Processing (Chapter 13) |
Knuth-Morris-Pratt pattern matching algorithm, dynamic programming, text compression, tries |
|
| w13 | Graph Algorithms (Chapter 14) |
definition, data structures for graphs, graph traversals, shortest paths, dijkstra's algortitm, minimum spanning trees |
|
| w14 | Memory Management and B-Trees (Chapter 15) |
memory allocation, garbage collection, memory hierachies and caching, external searching and B-trees, external memory sorting |
|
| w15 | Main algorithms and data structures review |
review and applications (examples) of the algorithms and data structures covered in the course |
授業実施形態
授業外学習の指示
成績評価方法
| 種別 | 割合(%) | 評価基準等 |
|---|---|---|
| 定期試験（筆記） | 50 | Ability to solve the questions provided in the final exam |
| レポート試験 （統一締切日を締切とするレポート） |
||
| 上記以外の試験・レポート、平常点評価 （日常的な授業における取組状況の評価） |
50 | Attendance, assignments and the mid-term exam |
成績評価方法(備考)
受講および研究に関するアドバイス
教科書
| 書名 | 著者 | 出版社 | ISBNコード | 備考 |
|---|---|---|---|---|
| Data Structures and Algorithms in Python Paperback – 2016 | Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser | Wiley india Pvt. Ltd; 1st edition (2016) | ISBN-10: 812656217X |
教科書(使用頻度、その他補足)
参考書
| 書名 | 著者 | 出版社 | ISBNコード | 備考 |
|---|---|---|---|---|
| Introduction to Algorithms, 3rd Edition (MIT Press) 3rd Edition | Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein | The MIT Press; 3rd edition (July 31, 2009) | ISBN-10: 0262033844 | |
| Data Structures and Algorithms in Java 6th Edition | Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser | Wiley; 6 edition (January 28, 2014) | ISBN-10: 1118771338 | |
| Problem Solving with Algorithms and Data Structures Using Python (2nd Ed) (online!) | Bradley N. Miller, David L. Ranum | Franklin, Beedle & Associates; 2nd edition (August 22, 2011) | ISBN-10: 1590282574 | http://interactivepython.org/runestone/static/pythonds/index.html |
| Python Algorithms: Mastering Basic Algorithms in the Python Language 2nd ed. Edition | Magnus Lie Hetland | Apress; 2nd ed. edition (September 4, 2014) | ISBN-10: 148420056X | |
| Data Structures and Algorithms with Python 2015th Edition | Kent D. Lee, Steve Hubbard | Springer; 2015 edition (January 13, 2015) | ISBN-10: 3319130714 |