[1] Learn techniques for the complexity analysis of algorithms.
[2] Understand basic data structures and operations for them.
[3] Learn basic algorithm design techniques.
[4] Understand basic sorting algorithms and their time complexity.
Outline:
In this course, students will learn about typical data structures, basic knowledge of algorithms, and algorithm design techniques. A data structure represents a collection of data and the relationship between the data. An algorithm is a calculation procedure that solves a problem, and always gives an answer and complete the calculation within a finite amount of time as long as you follow the procedure Data structures and algorithms, in other words, are ingredients for a program and are essential knowledge in creating an efficient program.
Style:
Classes will be held in a lecture style.
Notice:
This course's content will amount to 90 hours of study in total. These hours include the learning time guaranteed in classes and the standard self-study time required for pre-study / review, and completing assignment reports. Students are required to develop abilities to think. Quizzes and programming assignments for the week will be done on the e-learning system. As it's a learning-credit subject, it's essential that students score at least two-thirds in the quizzes and assignments and submit them by the due date.
Students who miss 1/3 or more of classes will not be eligible for evaluation.
|
|
|
Theme |
Goals |
| 2nd Semester |
| 3rd Quarter |
| 1st |
Algorithms and computational complexity
|
Can describe the difference between a problem and an example problem, and can explain what are algorithms that solve the problem. Can analyze the complexity of an algorithm using the order notation.
|
| 2nd |
Data structure that represents the column 1/2
|
Can explain how arrays and lists are implemented in a program. Can analyze the time complexity required for basic operations for each data structure.
|
| 3rd |
Data structure that represents the column 2/2
|
Can explain how stacks and queues are implemented in a program Can analyze the nature of each data structure and the time complexity required for basic operations.
|
| 4th |
Graphs and trees
|
Can explain how graphs and trees are implemented in a program and space complexity. Can explain time complexity for operations to examine the adjacency of the vertices of a graph (tree) for each method.
|
| 5th |
Heap
|
The heap is a one-dimensional array of partially ordered trees. Can write an algorithm that makes up the heap and algorithm that inserts and deletes data. Also, can analyze their time complexity.
|
| 6th |
Recursive method and recursive equations
|
Can write an algorithm by using the recursive method. Can solve the recursive equation obtained by analysis of the time complexity of the recursive procedure.
|
| 7th |
Divide-and-conquer method
|
Can write an algorithm with the divide-and-conquer method used in combination with the recursive method.
|
| 8th |
Midterm examination
|
|
| 4th Quarter |
| 9th |
Dynamic planning method
|
Can explain the dynamic planning method used extensively in optimization problems and its calculation process.
|
| 10th |
Simple sorting algorithms and decision tree |
Can write algorithms for methods such as simple insertion, simple selection, and bubble sort, and can analyze their time complexity. Can analyze the number of comparisons in sorting by comparison by using decision trees.
|
| 11th |
Optimal sorting algorithm
|
Can write an algorithm for merge sort and heap sort, and analyze their time complexity. They have optimal worst-case time complexity.
|
| 12th |
Quicksort and bucket sort
|
Can write quicksort algorithm and analyze its time complexity. It has optimal average-case time complexity. Aslo, can write bucket sort algorithm and analyze its time complexity.
|
| 13th |
Binary search method and binary search tree
|
Can explain the binary search method that allows fast data search when the data is sorted by the size of the search key. Can write an algorithm for a binary search tree, using concept of binary search that allows data insertion or deletion, and can analyze its time complexity.
|
| 14th |
AVL tree, B tree, hashing method
|
Binary search trees do not necessarily improve the balance of the trees. Can explain the AVL and B trees, typical equilibrium trees. In addition, can explain a hash method that represents a set without comparing data.
|
| 15th |
Greedy algorithm
|
Can explain the algorithms of Kruskal and Prim that make up the minimum spanning tree of a graph. Also, can analyze their time complexity.
|
| 16th |
Final examination
|
|