# 資訊工程理論基礎

## Fall 2004

**Course webpage:**
http://www.csie.ntu.edu.tw/~cyy/m0520

**Meeting time and place:**
Room 110, 6:30pm-9:30pm Wednesday

**Instructor:**
莊永裕,
Room 527, cyy@csie.ntu.edu.tw

**Office hours:**
by appointment

**Textbooks:**
**Grading:**
- midterm exam. (30%) Nov. 10, 2004
- final exam. (30%) Jan. 12, 2005
- 4 homework (40%)

**Course overview:**

In this course, we will cover computation theory and algorithms.
For the first part of the course, we will talk about important topics
in theory of computing:
- automata and regular languages
- context-free grammars
- computation model and Turing machine
- decidability
- reducibility
- time Complexity

For the second part of the course, we will talk about some "real-world"
algorithms. The goal of this part is to help you gain a greater appreciation
of the beauty and elegance of algorithms as well as where they are used in
the real world. Hopefully, after this course, you will become better prepared
to tackle algorithm design for "real-world" problems. The possible algorithms
we will go over include
- divide and conquer
- dynamic programming
- linear programming
- greedy algorithms
- graph algorithms
- maximum flow
- numeric algorithms
- approximation algorithms

**Lectures:**

09/22: lecture02

09/29: lecture03

10/06: lecture04

10/13: lecture05

10/20: lecture06

10/27: lecture07

11/03: lecture08

11/10: midterm exam

11/17: lecture09

11/24: lecture10

12/01: lecture11

12/08: lecture12

12/15: lecture13

12/22: lecture14

12/29: lecture15

**Homework:**

Homework #1: due 10/13

Homework #2: due 11/03

Homework #3: due 12/22

Homework #4: due 1/05

Last Modified: