Course title
アルゴリズム論   [Algorithms]
Course category	technology speciality courses	Requirement		Credit	2
Department		Year	2～4	Semester	3rd
Course type	3rd	Course code	022673
Instructor(s)
金子 敬一   [KANEKO Keiichi]
Facility affiliation	Faculty of Engineering	Office	afjgxte/L1151	Email address

Course description

This course introduces representative algorithms and discusses guidelines to evaluate algorithm performance and to create good algorithms. [Class Code] 6goca4h

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

9/30/2021 2:52:58 PM