2025 (Current Year) Faculty Courses School of Computing Undergraduate major in Mathematical and Computing Science
Introduction to Algorithms and Data Structures
- Academic unit or major
- Undergraduate major in Mathematical and Computing Science
- Instructor(s)
- Kenji Yasunaga / Yusuke Yoshida
- Class Format
- Lecture/Exercise (Face-to-face)
- Media-enhanced courses
- -
- Day of week/Period
(Classrooms) - 5-8 Tue / 5-6 Fri
- Class
- -
- Course Code
- MCS.T213
- Number of credits
- 210
- Course offered
- 2025
- Offered quarter
- 2Q
- Syllabus updated
- Mar 27, 2025
- Language
- Japanese
Syllabus
Course overview and goals
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.
Course description and aims
(1) Able to explain algorithms based on modulo arithmetic, divide and conquer, dynamic programming, etc., and evaluate their computational complexity.
(2) Able to explain data structures such as heaps, binary search trees, etc., along with their implementation methods and evaluate the computational complexity of each operation.
(3) Implement the above algorithms and data structures using the C language.
Keywords
Modulo Arithmetic, Heaps, Binary Search Trees, Fast Fourier Transform, Graph Algorithms, Dynamic Programming
Competencies
- Specialist skills
- Intercultural skills
- Communication skills
- Critical thinking skills
- Practical and/or problem-solving skills
Class flow
Lectures are held on Tuesdays and Fridays 5-6 periods
Exercises are held on Tuesdays 7-8 periods at the computer laboratory
Course schedule/Objectives
| Course schedule | Objectives | |
|---|---|---|
| Class 1 | Algorithm and Computational Complexity: Fibonacci Numbers, Computational Complexity, Big O Notation, Introduction to C Language | Understand the computational complexity of algorithms and the big O notation. |
| Class 2 | [Exercise 1]: Introduction to C Language, Fibonacci Numbers | Become able to write basic C language code. |
| Class 3 | Modular Arithmetic 1: Computational Complexity of Arithmetic Operations, Modular Arithmetic, Modular Exponentiation (Repeated Squaring), Euclidean Algorithm, Primality Testing, Loop Invariants | Understand modulo arithmetics and their computational complexity, the Euclidean algorithm, and loop invariants. |
| Class 4 | Data Structures 1: Operations on Dynamic Sets, Priority Queues, Heaps | Understand operations on dynamic sets, priority queues, and heaps. |
| Class 5 | [Exercise] Modular Arithmetic | Become able to write modulo arithmetic algorithms in the C programming language. |
| Class 6 | Data Structures 2: Binary Search, Linked Lists, Stacks, Queues | Understand binary search and data structures such as linked lists. |
| Class 7 | Data Structures 3: Binary Search Trees, Balanced Search Trees, Hashing | Understand binary search trees, balanced search trees, and hashing methods. |
| Class 8 | [Exercise 3]: Heaps | Become able to write heaps in the C programming language. |
| Class 9 | Divide and Conquer 1: Karatsuba Algorithm, Master Theorem, Merge Sort, Lower Bounds on Sorting Algorithms | Understand divide and conquer algorithms such as the Karatsuba algorithm and be able to evaluate their computational complexity. |
| Class 10 | Divide and Conquer 2: Median Finding, Matrix Multiplication (Strassen's Algorithm) | Understand algorithms such as median finding and matrix multiplication using divide and conquer techniques. |
| Class 11 | [Exercise 4]: Data Structure, Divide and Conquer | Implement algorithms such as divide and conquer based on data structures in the C programming language. |
| Class 12 | Fast Fourier Transform 1: Polynomial Coefficient Representation and Value Representation, Polynomial Evaluation and Interpolation, Vandermonde Matrix | Understand polynomial coefficient representation, value representation, polynomial evaluation, and polynomial interpolation. |
| Class 13 | Fast Fourier Transform 2: Fast Fourier Transform (FFT), Applications of FFT | Understand the Fast Fourier Transform. |
| Class 14 | [Exercise 5]: Fast Fourier Transform | Implement the Fast Fourier Transform in the C programming language. |
| Class 15 | Graph Algorithms 1: Graph Representation, Depth-First Search, Reachability, Connected Components | Understand depth-first search, reachability, and connected components for graphs. |
| Class 16 | Graph Algorithms 2: Breadth-First Search, Shortest Paths, Dijkstra's Algorithm | Understand breadth-first search, shortest path, and Dijkstra's algorithm for graphs. |
| Class 17 | [Exercise 6]: Graph Algorithms | Implement graph algorithms in C language. |
| Class 18 | Dynamic Programming: Shortest Paths, Longest Increasing Subsequence, Edit Distance | Understand dynamic programming. |
| Class 19 | Dynamic Programming: Knapsack Problem, Memoization, Matrix Chain Multiplication | Understand dynamic programming for various problems. |
| Class 20 | [Exercise 7]: Dynamic Programming | Implement dynamic programming in C. |
| Class 21 | Advanced Topics (e.g., Quantum Algorithms, Disjoint Set Data Structure) | Understand advanced topics related to algorithms and data structures. |
Study advice (preparation and review)
To enhance effective learning, students are encouraged to spend a certain length of time outside of class on preparation and review (including for assignments). They should do so by referring to textbooks and other course material.
Textbook(s)
None required
Reference books, course materials, etc.
T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, 4th edition, MIT Press, 2022
S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms, McGraw-Hill, 2006
Evaluation methods and criteria
In-class quizzes: 30%
Homework-style reports: 30%
Programming exercises: 40%
Related courses
- LAS.I121 ： Computer Science I
- LAS.I122 ： Computer Science II
- MCS.T204 ： Introduction to Computer Science
Prerequisites
The computer lab is available only to students in the Department of Mathematical and Computational Sciences.
Prerequisites include completion of related courses or equivalent knowledge.