A procedure for solving a given problem is called "Algorithm". Efficient algorithms often require well-designed data structure. In this course, we deal with typical algorithms and data structures, their computational complexity and their implementation by C programming language.
Since algorithm is a concrete procedure for solving problems, algorithm is foundation of all information processing, and used everywhere in real world. Learning algorithm is quite important, and could affects our thoughts.
(1) Ability of explaining algorithms based on binary search, divide-and-conquer, dynamic programming, and evaluating their computational complexity.
(2) Ability of explaining data structures, e.g., heap, binary search tree, etc, and their functionality, and evaluating their computational complexity.
(3) Ability of implementing algorithms and data structures by using C programming language.
(4) Ability of designing efficient algorithms for given problem.
binary search, divide-and-conquer, dynamic programming, heap, binary search tree, graph algorithms
|✔ Specialist skills||Intercultural skills||Communication skills||Critical thinking skills||✔ Practical and/or problem-solving skills|
Videos lectures are uploaded to YouTube. All documents used in the lectures are uploaded to GitHub. Students can communicate with lecturer on Slack. Assignments using C language are given every week. Assignments are uploaded and evaluated on GitHub.
|Course schedule||Required learning|
|Class 1||Algorithm and recurrence formula: Euclidean algorithm, binary search||Ability of explaining Euclidean algorithm and binary search.|
|Class 2||Introduction to C programming language (Exercise): Euclidean algorithm, binary search||Ability of writing basic program codes in C programming language. Ability of implementing Euclidean algorithm and binary search by C programming language.|
|Class 3||Order of computational complexity: Euclidean algorithm and binary search||Ability of evaluating computational complexity of Euclidean algorithm and binary search. Ability of using big-O notation, etc.|
|Class 4||Divide-and-conquer: Selection sort, insertion sort, merge sort, computational complexity||Ability of explaining sorting algorithms including selection sort, insertion sort, merge sort, and evaluating their computational complexity.|
|Class 5||Divide-and-conquer (Exercise): quickselect, quicksort||Ability of implementing quickselect and quicksort by using C programming language.|
|Class 6||Divide-and-conquer: Matrix multiplication, polynomial multiplication Formal power series for counting problems||Ability of explaining other divide-and-conquer algorithms including matrix multiplication and polynomial multiplication. Ability of explaining generating function of some simple series of numbers.|
|Class 7||Dynamic programming: Fibonacci number, partition number||Ability of explaining dynamic programming algorithm for partition number.|
|Class 8||Dynamic programming: Memoization, bottom-up method, computational complexity||Ability of implementing dynamic programming algorithm for partition number using memoization and bottom-up method.|
|Class 9||Dynamic programming: Knapsack problem, longest increasing subsequence||Ability of explaining typical dynamic programming algorithms such as knapsack problem, longest increasing subsequence.|
|Class 10||Dynamic programming (Exercise): Knapsack problem||Ability of implementing dynamic programming algorithm for knapsack problem using C programming language.|
|Class 11||Dynamic programming (Exercise): Knapsack problem||Ability of implementing dynamic programming algorithm for knapsack problem using C programming language.|
|Class 12||Data structure: Heap, heap sort||Ability of explaining heap and its functionality.|
|Class 13||Data structure (Exercise): Heap, heap sort||Ability of implementing heap and heap sort by using C programming language.|
|Class 14||Data structure: Balanced binary search tree||Ability of explaining balanced binary search tree and its functionality.|
|Class 15||Data structure (Exercise): Malloc, pointer, balanced binary tree||Ability of implementing balanced binary tree using malloc and pointer.|
|Class 16||Data structure (Exercise): Malloc, pointer, balanced binary tree||Ability of implementing balanced binary tree using malloc and pointer.|
|Class 17||Graph algorithms: Breadth-first search, depth-first, search||Ability of explaining Breadth-first search, depth-first search and Dijkstra algorithm.|
|Class 18||High-level algorithm: Convolution problem, discrete Fourier transform, fast Fourier transform.||Ability of explaining relationship between convolution problem and discrete Fourier transform. Ability of explaining fast Fourier transform.|
|Class 19||High-level algorithm: Fast Fourier transform.||Ability of implementing fast Fourier transform by C programming language.|
|Class 20||Randomized algorithm: Universal hash function, hash table||Ability of explaining universal hash function and hash table.|
|Class 21||Quantum algorithm: Grover algorithm, Shor algorithm||Ability of explaining abstract of quantum mechanics, quantum computation, Grover's algorithm and Shor's algorithm.|
All materials used in this course are provided on web page which will be informed in a class.
T. Cormen, et al., Introduction to Algorithms, 3rd edition ,MIT Press, 2013, ISBN-13 978-0262033848.
No prerequisities are necessary, but enrollment in the related courses is desirable.
Ryuhei Mori, mori[at]c.titech.ac.jp
There is no Office Hour. Students can use Slack for questions on lectures and assignments.