| Course title | |||||
| アルゴリズム論 [Algorithms] | |||||
| Course category | technology speciality courses,ets. | Requirement | Credit | 2 | |
| Department | Year | 2～4 | Semester | Fall | |
| Course type | Fall | 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. |
| Course schedule |
|
Lesson 1 Chapter 1 Data and complexities 1.1 Data representations 1.2 Recursive calls 1.3 Algorithms and complexities Lessons 2 and 3 Chapter 2 Search 2.1 Binary trees 2.2 Balanced trees 2.3 Heaps 2.4 Hash methods Lessons 4 and 5 Chapter 3 Sorting 3.1 Sorting and orders 3.2 Bubble sort 3.3 Insertion sort 3.4 Merge sort 3.5 Heap sort 3.6 Quick sort Lessons 6 and 7 Midterm examination and commentary for it Lessons 8 to 10 Chapter 4 Graphs and networks 4.1 Terminologies 4.2 Graph search 4.3 Strongly-connected components 4.4 Dijkstra method 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 Lessons 14 and 15 Final examination and commentary for it |
| Prerequisites |
| Preliminary knowledge of programming is prerequisite. Learning mathematical programming is recommended. |
| 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 |
| 10/4/2017 10:56:51 AM |