| Course title | |||||
| アルゴリズム論 [Algorithms] | |||||
| Course category | technology speciality courses,ets. | Requirement | Credit | 2 | |
| Department | Year | 2～4 | Semester | 3rd | |
| Course type | 3rd | Course code | 022817 | ||
| Instructor(s) | |||||
| 金子 敬一 [KANEKO Keiichi] | |||||
| Facility affiliation | Faculty of Engineering | Office | Email address | ||
| Course description |
| This course introduces representative algorithms and discusses guidelines to evaluate algorithm performance and to create good algorithms. |
| Expected Learning |
|
Students are expected to acquire ability to design rough sketches of algorithms and to estimate their time complexities as preliminaries of programming. See the Curriculum maps. |
| Course schedule |
|
Lesson 1 Chapter 1 Data and complexities 1.1 Data representations 1.2 Recursive calls 1.3 Algorithms and complexities Lesson 2 Chapter 2 Search 2.1 Binary trees 2.2 Balanced trees Lesson 3 2.3 Heaps 2.4 Hash methods Lesson 4 Chapter 3 Sorting 3.1 Sorting and orders 3.2 Bubble sort 3.3 Insertion sort Lesson 5 3.4 Merge sort 3.5 Heap sort 3.6 Quick sort Lesson 6 Summary and midterm examination Lesson 7 Commentary for the midterm examination Lesson 8 Chapter 4 Graphs and networks 4.1 Terminologies 4.2 Graph search Lesson 9 4.3 Strongly-connected components 4.4 Dijkstra method Lesson 10 4.5 Warshall-Floyd method 4.6 Maximum-flow problem Lesson 11 Chapter 5 String matching 5.1 Brute method 5.2 KMP method Lesson 12 Chapter 6 NP-complete problems and approximation algorithms 6.1 NP-complete problems 6.2 Approximation algorithms Lesson 13 Chapter 7 Recent selected topics Lesson 14 Summary and final examination Lesson 14 Commentary for the final examination |
| Prerequisites |
| Preliminary knowledge of programming is prerequisite. Learning mathematical programming is recommended. In addition to 30 hours that students spend in the class, students are recommended to prepare for and revise the lectures, spending the standard amount of time as specified by the University and using the lecture handouts as well as the references specified below. |
| Required Text(s) and Materials |
| none |
| References |
| Books related to 'algorithms', 'data structures', or 'theory of computation' would be helpful. |
| Assessment/Grading |
| Grading is based on the three examinations. |
| Message from instructor(s) |
| The students who will attend this course must be favorite of programming, especially machine-language programming. |
| Course keywords |
| Algorithms, Data structures, complexities, graphs, and computational geometry |
| Office hours |
| As needed. E-mail communication is welcome. k1kaneko@cc.tuat.ac.jp |
| Remarks 1 |
| Remarks 2 |
| Related URL |
| Lecture Language |
| Japanese |
| Language Subject |
| Last update |
| 3/14/2019 6:40:13 PM |