|
Simplex
Twophase
Dijkstra
Prim
Kruskal
Ford-Fulkerson
FAQ
Japanese/English
|
Instructor:
- Kenji Ikeda
- Room : C403
- Office Hours : Mon. 14:00--17:00
Lectures:
- Time : Mon. & Fri. 17:55--19:25
- Room : C20
Course Materials
- Textbook: No required text
- Reference book:
- C. H. Papadimitriou and K. Steiglitz : Combinatorial Optimization
-- Algorithms and Complexity, Prentice-Hall (1982)
- Vasek Chvatal : Linear Programming, W.H.Freeman, New York (1983)
- Notes: course notes(Sorry! Only in Japanese)
- Java applets: click on the left margin.
Announcement
Syllabus
| 1st |
Linear Programming (LP) Problem |
an LP problem
|
| 2nd |
from Geometric solution to Algebraic solution |
demo1 |
|
A brief review of linear algebra. |
|
Basic Solutions. |
demo2 |
| 3rd |
Fundamental Theorem |
|
Simplex Method |
demo3- 1 ,
2 |
| 4th |
Two Phase Method |
demo4- 1 ,
2
|
| 5th |
Revised Simplex Algorithm |
| 6th |
Duality |
|
- Duality Theorem
- Complementary Slackness
- Farkas' Lemma
|
| 7th |
A brief review of Graphs and Networks |
| 8th |
Shortest Path Problem (Dijkstra's Algorithm ) |
demo8- 1 ,
2,
3,
4
|
| 9th |
MST Problem (Krukal's Algorithm) |
demo9- 1 ,
2,
3,
4
|
| |
MST Problem (Prim's Algorithm) |
demo10- 1 ,
2,
3,
4
|
| 10th |
Maximum Flow-Minimum Cut Problem |
demo11- 1 ,
2,
3,
4
|
| 11th |
Maximum Matching - Minimum Cover Problem |
demo12- 1 ,
2,
3,
4
|
| 12th |
|
|
|
| 13th |
|
|
|
| 14th |
Trial exam |
|
| 15th |
Final Exam |
|
Grading and Exams:
|