Advanced Communication Engineering and Informatics IV(Computer Algorithms)

Go to the google classroom:6a6xvqj

The purpose of this lecture is provide the theory and technique to design
efficient algorithms for various fundamental problems.
The goals of the students are to achieve the following points:
(1) to understand the behavior, correctness, and time complexity analysis
of the algorithms discussed in the lecture,
(2) to understand the principles of design methodologies of algorithms, such as
dynamic programming, greedy method, etc.

Registered students should have ability to write C programs. Furthermore,
the knowledge about some basic data structures (list, binary tree, heap, etc.) and
basic algorithms (sorting, etc.) are required.

None

Some handouts are provided at the lecture.

(a) Contents of the lecture

[1] Minimum spanning tree problem and greedy algorithms
[2] Correctness of Prim's and Kruskal's algorithm
[3] Greedy algorithms for other problems
[4] Shortest path problem and Dynamic Programming (DP)
[5] DP Method (1) --- Transform DFAs to regular expressions
[6] DP Method (2) --- Context-free grammar and its recognition problem
[7] DP Method (3) --- CYK algorithm for CFG recognition
[8] DP Method (4) --- Hidden Markov Models (HMM)
[9] DP Method (5) --- Recognition problem of HMM
[10] DP Method (6) --- HMM recognition algorithm
[11] DP Method (7) --- Approximate string matching algorithms
[12] String matching problem
[13] Computing failure functions in KMP algorithm
[14] Correctness and time complecity of KMP algorithm
[15] Summary and conclusion of this lecture

(b) How does this lecture proceed?

For each problem, we first discuss on its background and motivation, and then
give an algorithm for the problem. The correctness and time complexity
analysis of the given algorithm will be discussed in details.
Example runs will be used to enrich the understanding.

Implement algorithms given in the the lecture, if possible.

Academic performance is evaluated by problems given to the students on the google classroom.
The lowest standard is 60%.

Any time, but appointments by e-mails are necessary.

None

None