| Schedule | Homework | Final Project | Grading |

Algorithm 2015

Classroom:

Instructor:

  • Ming-Te Chi (紀明德), Assistant Professor
  • email: mtchi AT cs.nccu.edu.tw
  • Office hour: am 10:10~12:00, Monday

TA:

  • 胡臻騏、郭士傑( 100703009 AT nccu.edu.tw )。大仁樓 200304
Week Topic Chapter Slides Resource
01 02/27 補假



02 03/06 Introduction

Getting Started
1

2
Syllabus

slide-intro

Ch2
pdf

MIT course video 2005
MIT course video 2011

ITSA
UVa online judge
03 03/13 Growth of Functions 3
Ch3
pdf


CPE
3/20報名截止
3/24考試
04 03/20
quiz1
Growth of Functions

Divide and Conquer
3

4

Ch4
  pdf

05 03/27

Divide and Conquer


4




06 04/03

春 季學習假


07 04/10
quiz2
hw1
Sorting I - Heapsort

Sorting II
Quicksort
6

7
Ch6
pdf

Ch7
pdf
heapsort vs quicksort

visualgo

08 04/17
分組抽順序
Sorting in linear time
8
Ch8
pdf

09 04/24 Midterm Exam
10:10~12:00

Ch1, 2, 3, 4, 6, 7, 8.1





10 05/01

Sorting in linear time

8
Ch8
pdf


11 05/08

makeup exam
Elementary Data Structure

Binary Search Tree
10

12
Ch10
pdf

Ch12
pdf

12 05/15
quiz3

Dynamic Programming
 

project demo A
15
Ch15
pdf

13 05/22 Greedy Algorithm

project demo B
16
Ch16
pdf

CPE
5/22報名截止
5/26考試
14 05/29

Greedy Algorithm


Amortized Analysis

project demo C
16

17

Ch17
pdf

15 06/05

Elementary Graph Algorithm

project demo D
22

Ch22
pdf

程 式達人 (ITSA 月賽 )
6/10 pm6:00~9:00
16 06/12
hw2
 NP-Completeness

project demo E
34 Ch34
pdf
未 來數學家的挑戰:
計算量問題

17 06/19
端午節補假




18 06/26 Final term Exam
10:10~12:00
Ch 8.2~, 10, 12, 15, 16, 17, 34



homework / quiz
date
content
resource
1
quiz1
03/20


2
hw1 04/10 pdf

Problem 2-4 a,b,c
Exercise 4.4-1,
Exercise 4.5-1

3
quiz2 04/10


4

quiz3

05/15




5

hw2

06/12
pdf

Problem 16-1 a, c

6

hw3



CPE / ITSA


Final Project
Team
members
Topics
Order
resource
1
102703039
102703017
102703042
102703045

11284 Shopping Trip
A
slide

我們可以用Greedy Algorithm去尋求一個問題的
可能最佳解或近似於最佳解的結果,對於TSP問
題用Greedy Algorithm的主要概念為何?
2
102703028
102703002
102703038
102703014

163 - City Directions
10003 - Cutting Sticks

E
slide

假設切木頭所需的花費為木頭當前長度(cm),
現在我們有一條長度為100cm的木頭,
需要在10cm,20cm,50cm處將木頭切開,
請問如何切最省錢?所需金額為多少?
3
102703006
102703003
102703041

12090 - Counting Zeroes
B

slide


寫出解Counting Zeroes所使用的Sieve Eratosthenes的演算法複雜度。
4
102703036
102703037
102703040
102703044

112 Tree Summing
D
slide



5
102306014
100306012
104753019

681 - Convex Hull Finding
E
slide

請簡單比較用gift wrapping algorithm, Graham's scan algorithm及quick hull algorithm解決凸包問題的優缺點
6
102703023
102703048
102703004

432-Modern Art
E
slide

在題目限制下(p,q <= 10),時間複雜度為O(n) 。
第一題:若是p,q沒有限制範圍,請問p >> n 時,時間複雜度是多少?

第二題:若是p,q沒有限制範圍,請問p ~= n 時,時間複雜度是多少?
7
102703019
102703016
102703035
102703043

1449 - Dominating Patterns
E

slide
以KMP演算法來進行以下字串搜尋
abcabcdababcdabcdad
abcdad
請以圖表示比對的所有case,須標示出比對的開頭(須比對的第一個元素)與結尾(比對結束或比對錯誤的元素)

8
102703012
102703018
102703020
102703025

156 - Ananagrams
D
slide

請簡要說明如何把下列字串中的ananagrams挑出來?
ladder came tape  acme RIDE lone peat noel dire

9
101701012
101207420
1125 - Sherlock Holmes
B
slide

請問一般而言背包問題有哪幾種?(寫出名字而不是只回答幾種就好)
並且請問通常大家都用什麼方式解決背包問題?
10
102703029
102703015
102703013
102703022

10034 - Freckles
C
slide

請簡要說明Prim演算法的實作

11
102703005
102703034
102703033
101703050
10011 - Where Can You Hide?
C
slide

假如給兩條不一樣通過原點外切到圓的切線方程式
和圓心的座標還有點(房子)的座標這四項資訊,解釋
怎麼判斷點(房子)在兩條切線之間並且跟圓同側?
12
100205040
101703046
102703030

601 - The PATH
534 - Frogger
B
slide

若有一組測資如下:
4
0 0
4 6
4 0
0 3
0

答案顯示為
Scenario #1 Frog Distance = X
請問X的值為何?

13
102703026
102703007
101703047

10026 - Shoemaker's Problem
C
slide

在shoemaker problem中,若今天其中一個測資如下,
shoemaker會優先做哪一項工作?
5           (5項工作)
2    5     (第一項工作需要花2天完成&每延遲一天的罰金)
8    3     (第二項工作……)
7    4     (第三項工作……)
1    2     (第四項工作……)
3    3     (第五項工作……)
14
102703021
102703046
111 - History Grading
D
slide

我們稱一個序列(sequence)為某兩個序列的最長共同子序列 (Longest Common Subsequence,LCS)要符合以下條件:
1.其元素皆出現於兩個序列中
2.序列中的順序需和兩個序列中的出現順序相同
3.為所有共同序列中最長的那一個
請寫出下列兩個序列的LCS,並以Dynamic Programming的方式(畫出二維陣列圖)證明你的答案是正確的。
s1:{1,3,2,4}
s2:{1,4,2,3}
15
101703051
105 - The Skyline Problem

E
slide

為何在掃描線法中輸入資料要排序?

Grading:

Texturebook:

Reference book: