Course title
L08461002
Fundamental Exercise on Computer and Information Engineering 2A

 igarashi harukazu Click to show questionnaire result at 2018
Course description
This class presents example problems that can be solved by solution algorithms explained in “Data Structure and Algorithms 2” (L0694500). Designing algorithms and programming for the examples help you understand the standard solution algorithms, evaluate computational complexity and apply the standard algorithms to more practical problems.
Purpose of class
To understand standarard solutin algorithms and apply them to problems in specefic cases through programming.
Goals and objectives
  1. To sort data by basic sorting algorithms.
  2. To solve graph search problems by basic graph search algorithms.
  3. To solve string match problems by typical string match algorithms.
  4. To solve some standard problems using typical designing methods of algorithms.
Language
Japanese
Class schedule

 Class schedule HW assignments (Including preparation and review of the class.) Amount of Time Required
1. Sorting (I) : Bubble sort, selection sort, insertion sort and shell sort Read the syllabus and Section 5.1-5.4 of the text. 90minutes
2. Sorting (II) : Heap sort and quick sort Read Section 5.5-5.6 of the text. 90minutes
3. Breadth first search Read Section 6.1-6.4.1 of the text. 90minutes
4. Depth first search Read Section 6.4.2-6.4.3 of the text. 90minutes
5. Shortest path problem (I) : Dijkstra’s algorithm Read Section 6.5 of the text. 90minutes
6. Shortest path problem (II) : Dijkstra’s algorithm (continued) Solve the example presented in Fig.6.10. 90minutes
7. Maximum flow problem (I) Read Section 6.6.1-6.6.2 of the text. 90minutes
8. Maximum flow problem (II) (continued) Read Section 6.6.3 and solve the example presented in Fig.6.13. 90minutes
9. String matching problem : Brute-force algorithm and Boyer-Moore algorithm Read Chaper 7 ofthe text. 90minutes
10. Recursion : Euclidean algorithm Read Section 8.1-8.2 of the text. 90minutes
11. Dynamic programming : Fibonacci sequence Read Section 8.3.1 of the text. 90minutes
12. Knapsack problem (I) Read Section 8.3.2 of the text. 90minutes
13. Greedy method : Coin change problem and Minimum spanning tree problem Read Section 8.4 of the text. 90minutes
14. Final exam, Q&A Review the contents of the specified lectures so as to solve basic examples by using algorithms presented. 90minutes
Total. - - 1260minutes
Relationship between 'Goals and Objectives' and 'Course Outcomes'

 Assignments Final exam Total.
1. 7% 0% 7%
2. 20% 40% 60%
3. 3% 0% 3%
4. 10% 20% 30%
Total. 40% 60% -
Evaluation method and criteria
Assignments 1-13 (60%), Final examination (40%). Over 60% of the total is acceptable.
Textbooks and reference materials
Required textbook : T. Asano, K. Wada and T. Masuzawa, “Algorithm Theory,” IT Text, Ohmsha (in Japanese).
Prerequisites
Prerequisites : Understand the contents of “Data Structure and Algorithms 1” (L0692900) and “Fundamental Exercise on Computer and Information Engineering 1A” (L0845300). You should take “Data Structure and Algorithms 2” (L0694500) in parallel.
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 an ability for utilizing knowledge
Active-learning course
Most classes are interactive
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:34 JST 2020