Course title
L06945002
Data Structure and Algorithms 2

 igarashi harukazu Click to show questionnaire result at 2018
Course description
The main purpose of this course is to learn basic techniques for designing and analyzing computer algorithms by studying many kinds of data structures and algorithms to process the data. Furthermore, training abilities to apply the basic techniques to practical problems is an advanced goal of this course.
Purpose of class
To learn basic techniques for designing and analyzing computer algorithms.
Goals and objectives
  1. To understand basic graph algorithms.
  2. To understand basic solution algorithms for the string matching problem.
  3. To understand typical solution methods based on various approaches of algorithm design.
Language
Japanese
Class schedule

 Class schedule HW assignments (Including preparation and review of the class.) Amount of Time Required
1. Gragh algorithms (I) : Representation of a graph Read the syllabus and read pp.105-110 of the text. 100minutes
2. Gragh algorithms (II) : Breadth First Search (BFS) Read pp.111-113 of the text. 100minutes
3. Gragh algorithms (III) : Depth First Serach (DFS) Read pp.114-117 of the text. 100minutes
4. Gragh algorithms (IV) : Shortest path problem (Dijkstra’s algorithm) Read pp.118-120 of the text. 100minutes
5. Gragh algorithms (V) : Shortest path problem (time complexity of Dijkstra’s algorithm) Solve examples presented at the 4th lecture by yourself. Read pp.121-122 of the text. 200minutes
6. Gragh algorithms (VI) : Network flow and Maximum flow minimum cut theorem Read pp.123-127 of the text. 100minutes
7. Gragh algorithms (VII) : Maximum algorithm Read pp.128-129 of the text. 100minutes
8. String search algorithm (I) : Brute-force algorithm, Rabin-Karp algorithm and KMP algorithm Read pp.131-140 of the text. 100minutes
9. String search algorithm (II) : Boyer-Moore algorithm Read pp.141-145 of the text. 100minutes
10. Algorithm design (I) : Recursion, Mathematical induction and Euclidean algorithm Read pp.147-151 of the text. 100minutes
11. Algorithm design (II) : Divide and conquer, Maximum search problem and Satisfiability problem Read pp.152-155 of the text. 100minutes
12. Algorithm design (III) : Dynamic programming, Fibonacci sequence and Knapsack problem Read pp.156-161 of the text. 100minutes
13. Algorithm design (IV) : Greedy method, Coin change problem and Minimum spanning tree problem Read pp.162-165 of the text. 100minutes
14. Final exam, Q&A Review the contents of all the lectures so as to solve basic examples by using algorithms presented. 1250minutes
Total. - - 2650minutes
Relationship between 'Goals and Objectives' and 'Course Outcomes'

 Final exam Total.
1. 33% 33%
2. 33% 33%
3. 34% 34%
Total. 100% -
Evaluation method and criteria
Final exam (100%). Over 60% is acceptable.
Textbooks and reference materials
Textbook : T. Asano, K. Wada and T. Masuzawa, “Algorithm Theory,” IT Text, Ohmsha (in Japanese).
Prerequisites
Prerequisites : “Data Structure and Algorithms 1”(L0692900)
Office hours and How to contact professors for questions
  • 12:10 – 13:00 on Wednesdays at Room no. 4301.
Regionally-oriented
Non-regionally-oriented course
Development of social and professional independence
  • Course that cultivates a basic problem-solving skills
  • Course that cultivates an ability for utilizing knowledge
Active-learning course
N/A
Course by professor with work experience
Work experience Work experience and relevance to the course content if applicatable
N/A N/A
Education related SDGs:the Sustainable Development Goals
  • 9.INDUSTRY, INNOVATION AND INFRASTRUCTURE
  • 12.RESPONSIBLE CONSUMPTION & PRODUCTION
Last modified : Thu Aug 27 04:08:30 JST 2020