Course title
アルゴリズム論   [Algorithms]
Course category technology speciality courses,ets.  Requirement   Credit 2 
Department   Year 24  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