Hiroshima University Syllabus

Back to syllabus main page
Japanese
Academic Year 2022Year School/Graduate School School of Informatics and Data Science
Lecture Code KA110001 Subject Classification Specialized Education
Subject Name アルゴリズムとデータ構造
Subject Name
(Katakana)
アルゴリズムトデータコウゾウ
Subject Name in
English
Algorithms and Data Structures
Instructor FUJITA SATOSHI
Instructor
(Katakana)
フジタ サトシ
Campus Higashi-Hiroshima Semester/Term 2nd-Year,  Second Semester,  3Term
Days, Periods, and Classrooms (3T) Thur1-4:ENG 107
Lesson Style Lecture Lesson Style
(More Details)
 
Lecture 
Credits 2.0 Class Hours/Week   Language of Instruction B : Japanese/English
Course Level 2 : Undergraduate Low-Intermediate
Course Area(Area) 25 : Science and Technology
Course Area(Discipline) 02 : Information Science
Eligible Students
Keywords Algorithms, data structure, analysis of algorithms, divide-and-conquer 
Special Subject for Teacher Education   Special Subject  
Class Status
within Educational
Program
 
Criterion referenced
Evaluation
Program of Electrical,Systems and Information Engineering
(Abilities and Skills)
・Concepts, knowledge and methods which are the basis for studies related to electrical,  systems, and information engineering.
・Concepts, knowledge and methods which are the basis for studies related to electrical, systems, and information engineering.

Program of Electronic Devices and Systems
(Abilities and Skills)
・Concepts, knowledge and methods which are the basis for studies related to electronic engineering.
・Ability to apply basic concepts, knowledge, and methods of electronics engineering to concrete/technical problems.

Informatics and Data Science Program
(Abilities and Skills)
・A. Skills related to the development of an information infrastructure,information processing techniques, and technology for producing new added value through data analysis.

・ B. Ability to identify and solve new problems on their own by quantitative and logical thinking based on data, diverse perspectives, and advanced skills for information processing and analysis.

(Comprehensive Abilities)
・I2. Ability to provide the most appropriate system solution to a cross-sectional problem in the diversified and complicated information society based on the many forms of cutting edge information technology.
 
Class Objectives
/Class Outline
The goal of this class is understand the basic concept and techniques used in the design and analysis of algorithms and data structures. 
Class Schedule 1. Introduction. What is algorithm ? Preliminaries
2. String matching (1); Naive algorithm and KMP algorithm
3. String matching (2); How to make partial match table for KMP algorithm; BM algorithm
4. Sorting algorithm (1); Compare-and-exchange algorithm
5. Sorting algorithm (2); Sorting algorithms based on divide-and-conquer; quick sort and merge sort
6. Sorting algorithm (3) Radix sort and bucket sort
7. Data structure (1); Stack, queue, and binary search tree
8. Data structure (2); Heap; binary heap, binomial heap and more
9. Data structure (3); Disjoint sets, union-and-find
10. Shortest path algorithm (1); Dijkstra's algorithm
11. Shortest path algorithm (2); Bellman-Ford algorithm
12. Shortest path algorithm (3); dynamic programming, A* algorithm
13. Minimum spanning tree algorithm (1); Depth-first search and breadth-first search
14. Minimum spanning tree algorithm (2); Kruscal's algorithm
15. Minimum spanning tree algorithm (3); Prim's algorithm

Quiz of about 15 min for every class; five reports; and final exam. 
Text/Reference
Books,etc.
S. Fujita, Algorithms and data structures, Suuri-Kougaku-sha, 2013 (in Japanese). 
PC or AV used in
Class,etc.
 
(More Details) Lecture (video projector) 
Learning techniques to be incorporated  
Suggestions on
Preparation and
Review
This class consists of the following topics:
1) fundamentals of algorithms (correctness of algorithms; analysis of the execution time of algorithms; big-O notation);
2) string matching algorithm (I will explain how the keyword search in a text can be done very quickly; KMP algorithm)
3) sorting algorithms (I will explain the basic idea used in sorting many algorithms, such as quick sort, merge sort, and radix sort)
4) examples of algorithms using sophisticated data structure (e.g., shortest path algorithm and minimum spanning tree algorithm)

Please refer to other textbooks concerned with such related topics, if necessary. 
Requirements  
Grading Method Exercise + report (50%)
Final exam (50%) 
Practical Experience  
Summary of Practical Experience and Class Contents based on it  
Message  
Other   
Please fill in the class improvement questionnaire which is carried out on all classes.
Instructors will reflect on your feedback and utilize the information for improving their teaching. 
Back to syllabus main page