2025 (Current Year) Faculty Courses School of Engineering Undergraduate major in Information and Communications Engineering

Discrete Structures and Algorithms

Academic unit or major: Undergraduate major in Information and Communications Engineering
Instructor(s): Atsushi Takahashi
Class Format: Lecture/Exercise (Face-to-face)
Media-enhanced courses: -
Day of week/Period (Classrooms): 5-8 Mon (SL-101(S011)) / 7-8 Thu (SL-101(S011))
Class: -
Course Code: ICT.M215
Number of credits: 210
Course offered: 2025
Offered quarter: 4Q
Syllabus updated: Mar 27, 2025
Language: Japanese

Syllabus

Course overview and goals

The purpose of this course is to understand basic philosophies used in handling discrete information and/or discrete structure which are essential in computer and information processing, and to acquire basic methods for handling discrete information and/or discrete structure.

Course description and aims

Students will be able to understand the basic concepts of graph theory, and will be able to acquire basic methods for design and analysis of algorithms. Also, students will be able to understand the principle of algorithms and the relation between the property of a discrete structure and the efficiency of an algorithm, and to apply basic methods in the field of information and communications engineering.

Keywords

graph, algorithm, computational complexity

Competencies

Specialist skills
Intercultural skills
Communication skills
Critical thinking skills
Practical and/or problem-solving skills

Class flow

It is essential to handle discrete information and/or discrete structure in computer and information processing. This course discusses basic properties of graphs from an algorithmic point of view, and provides the basic concepts for the analysis of algorithms and basic algorithms for graphs. Also, an overview of the design methodologies for algorithm and an overview of the theory of NP-completeness are introduced. In principle, one exercise session corresponds to the previous two lectures. An exercise session includes concrete problems related to the contents of the previous two lectures and students will be able to apply the knowledge and methods acquired during the lectures to practical problems.

Course schedule/Objectives

	Course schedule	Objectives
Class 1	Graph and its representation	Explain the overview of concept of graph and its representation
Class 2	Tree and forest	Explain the overview of concept of tree and forest
Class 3	Exercise	Review the course contents. Use the exercise problems to better understand the topics covered, and evaluate one's own progress.
Class 4	Bipartite graph, graph coloring, Eulerian graph, and Hamiltonian graph	Explain the overview of concept of bipartite graph, graph coloring, Eulerian graph, and Hamiltonian graph
Class 5	Asymptotic evaluation of function	Explain the overview of concept asymptotic evaluation of function
Class 6	Exercise	Review the course contents. Use the exercise problems to better understand the topics covered, and evaluate one's own progress.
Class 7	Analysis of algorithm	Explain the overview of concept analysis of algorithm
Class 8	Sorting algorithm	Explain the concept of efficient sorting algorithm
Class 9	Exercise	Review the course contents. Use the exercise problems to better understand the topics covered, and evaluate one's own progress.
Class 10	Midterm exam and the summary of the first part of the course	Test the level of understanding and evaluate the achievement for the first part of the course
Class 11	Search algorithm	Explain the overview of depth-first-search and breath-first-search
Class 12	Shortest path algorithm	Explain the overview of Dijkstra's shortest path algorithm
Class 13	Exercise	Review the course contents. Use the exercise problems to better understand the topics covered, and evaluate one's own progress.
Class 14	Maximum spanning tree algorithm	Explain the overview of Kruskal's maximum spanning tree algorithm
Class 15	Design methodologies of algorithm	Explain the overview of design methodologies of algorithm
Class 16	Greedy algorithm	Explain the overview of concept of greedy algorithm
Class 17	Exercise	Review the course contents. Use the exercise problems to better understand the topics covered, and evaluate one's own progress.
Class 18	Complexity of computation (P and NP)	Explain the overview of concept of complexity of computation (P and NP)
Class 19	Approximate algorithm	Explain the overview of concept of approximate algorithm
Class 20	Exercise	Review the course contents. Use the exercise problems to better understand the topics covered, and evaluate one's own progress.
Class 21	Final exam and the summary of the second part of the course	Test the level of understanding and evaluate the achievement for the second part of the course

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), as specified by the Tokyo Institute of Technology Rules on Undergraduate Learning (東京工業大学学修規程) and the Tokyo Institute of Technology Rules on Graduate Learning (東京工業大学大学院学修規程), for each class.
They should do so by referring to textbooks and other course material.

Textbook(s)

Information and Algorithm, Ueno and Takahashi, Morikita 2005 (in Japanese)

Reference books, course materials, etc.

None

Evaluation methods and criteria

Studnets' level of understanding on the basic concepts of graph theory and basic methods for design and analysis of algorithm will be assessed. Midterm and final exams (94%), exercise problems (6%)

Related courses

ICT.M202 ： Probability and Statistics (ICT)
ICT.M306 ： Concrete Mathematics
ICT.M310 ： Mathematical Programming
ICT.M316 ： Numerical Analysis (ICT)

Prerequisites

No prerequisites