KA110001 Algorithms and Data Structures

Hiroshima University Syllabus

Japanese

Academic Year 2024Year 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
(Applicable only to targeted subjects for undergraduate students)
Criterion referenced
Evaluation
(Applicable only to targeted subjects for undergraduate students) 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.

Computer Science Program
（Abilities and Skills）
・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value.
・B. Ability to identify new problems independently and solve them through quantitative and logical thinking based on data, multifaceted perspectives, and advanced information processing and analysis.
（Comprehensive Abilities）
・D2. Ability to derive optimal system solutions based on abundant cutting-edge information technologies for cross-sectoral issues in a diversified and complicated information society.

Data Science Program
（Abilities and Skills）
・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value.
・B. Ability to identify new problems independently and solve them through quantitative and logical thinking based on data, multifaceted perspectives, and advanced information processing and analysis.

Intelligence Science Program
（Abilities and Skills）
・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value.
・B. Ability to identify new problems independently and solve them through quantitative and logical thinking based on data, multifaceted perspectives, and advanced information processing and analysis.
（Comprehensive Abilities）
・D3. Ability to grasp complexly intertwined social needs and issues from a bird's-eye view and solve issues with a multifaceted perspective and analytical ability based on a wide range of knowledge in intelligent science.

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.

Academic Year	2024Year	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 (Applicable only to targeted subjects for undergraduate students)
Criterion referenced Evaluation (Applicable only to targeted subjects for undergraduate students)	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. Computer Science Program （Abilities and Skills）・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value. ・B. Ability to identify new problems independently and solve them through quantitative and logical thinking based on data, multifaceted perspectives, and advanced information processing and analysis. （Comprehensive Abilities）・D2. Ability to derive optimal system solutions based on abundant cutting-edge information technologies for cross-sectoral issues in a diversified and complicated information society. Data Science Program （Abilities and Skills）・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value. ・B. Ability to identify new problems independently and solve them through quantitative and logical thinking based on data, multifaceted perspectives, and advanced information processing and analysis. Intelligence Science Program （Abilities and Skills）・A. Information infrastructure development technology, information processing technology, technology that analyzes data and creates new added value. ・B. Ability to identify new problems independently and solve them through quantitative and logical thinking based on data, multifaceted perspectives, and advanced information processing and analysis. （Comprehensive Abilities）・D3. Ability to grasp complexly intertwined social needs and issues from a bird's-eye view and solve issues with a multifaceted perspective and analytical ability based on a wide range of knowledge in intelligent science.
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