Course title
アルゴリズム論   [Algorithms]
Course category technology speciality courses  Requirement   Credit 2 
Department   Year 24  Semester 3rd 
Course type 3rd  Course code 022673
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.
[Class Code] qsmxjkf
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 a couple of examinations, which check the ability to design rough sketches of algorithms and to estimate their time complexities. In case of the online classes, the grade evaluation premises all attendances, and the attitude to learn, the reports, the mid-term exam (or the report), and the end-term exam (or the report) are comprehensively evaluated. Standard study time set by the our university is required to get the grade.
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
1/27/2022 10:16:52 AM