Introduction to Algorithms and Data Structures

Course goal

To understand the meaning and importance of algorithms.

Course content

A formal procedure for solving a problem is called an ``algorithm'' and a way of storing data in a computer is called a data structure. There may be a number of combinations of algorithms and data structures for a problem, in general. It is important to evaluate them by computation time and space requirement to choose the best combination. It is not sufficient to understand conventional algorithms, but it is more meaningful to master how to design algorithms. In this lecture, a general but basic scheme for algorithm design through validation of correctness of algorithms and investigation of improvement of algorithm efficiency is explained.

References

• Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, MIT Press, 2009.
• First Course in Algorithms through Puzzles, Ryuhei Uehara, in printing, 2019.

Tentative Schedule

January 7: 10:00-12:00 and 13:00-15:00

0. Intruduction to Introduction to Algorithms
1. Foundation of Algorithms (1): Basic model and simple basic algorithms
2. Foundation of Algorithms (2): Simple basic algorithms
3. Searching (1): Sequential search
4. Searching (2): Block search
5. Searching (3): Binary Search and Hash method

January 8: 10:00-12:00 and 13:00-15:00

5. 5. Data Structure (0): Array and linked list
6. Data Structure (1): Stack, Queue, and Heap
7. Data Structure (2): Binary search tree and its balancing
8. Sorting (1): Bubble sort, Insertion sort, and Heap sort

January 9: 10:00-12:00 and 13:00-15:00

9. Sorting (2): Merge Sort, Quick sort, complexity of sort algorithms, and counting sort
10. Data Structure (3): Data structure for graphs
11. Graph Algorithms: Breadth-first search and depth-first search
12. Advanced Algorithm: Dynamic Programming

January 10: Special lectures on recent algorithms by the following professors

Unfortunately, the talk by Prof. Nandy is canceled.

Prof. Muhammad Kaykobad, Bangladesh University of Engineering and Technology

Title: Spanning trees and Cotrees in Digraphs

Prof. Md. Saidur Rahman, Bangladesh University of Engineering and Technology

Title: Graph Drawing

Prof. Shin-ichi Nakano, Gunma University

Title: Dispersion Problems

Prof. Ryuhei Uehara, Japan Advanced Institute of Science and Technology

Title: Computational Origami

The handout distributed on the first day.

Reports:

• Small reports on each day are in the slides.
• Big report will be distributed on Thursday. But it is available also here.
• You also submit a report that is a survey of one of lectures on January 10.

Last modified: Thu Jan 25 15:10:24 JST 2018 by Ryuhei Uehara (uehara@jaist.ac.jp)