Advanced Communication Engineering and Informatics IV(Computer Algorithms)

Go to the google classroom: puxjodsu

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] General approach to minimum spanning problem
[3] Correctness of Prim's and Kruskal's algorithm
[4] Greedy algorithms for other problems
[5] DP Method (1) --- Approximate String Matching Problem
[6] DP Method (2) --- Longest Increasing Subsequence Problem
[7] DP Method (3) --- Shortest path problem
[8] DP Method (4) --- Transform DFAs to regular expressions
[9] DP Method (5) --- Context-free grammar and its recognition problem
[10] DP Method (6) --- Bottom up understanding of CKY algorithm for CFG recognition
[11] DP Method (7) --- Top down understanding of CKY algorithm
[12] DP Method (8) --- Hidden Markov Models (HMM)
[13] DP Method (9) --- Recognition problem of HMM
[14] DP Method (10) --- HMM recognition algorithm
[15] Other algorithms and Summary

(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