Algorithms
Instructor: HyungSeok Kim, Room 1202/New Millennium Hall, hyuskim@konkuk.ac.kr
Credit: 3
Lecture: 13:30 – 15:00, Tuesday, Thursday
Visiting hour: 15:00 – 17:00, Wednesday
Course web page: http://vr.konkuk.ac.kr (Notices, etc)
Course objective:
1.
Learn
methods to design algorithms
2.
Be
able to prove correctness of algorithms
3.
Analysis
cost of algorithms
Text:

T.
Cormen, et al, Introduction to Algorithms, MIT Press (2009, 3^{rd}
edition)

(2^{nd}
edition can be also usable)
Grading:

Attendance:
10% (2 late appearances are equal to 1 absent. 25%(8) absents will give no
grade)

Assignments:
10%

Midterm
exam: 35%

Final
exam: 45%
Note: Copy of
assignments/exam will give penalty equal to the maximum score to be given.
Prerequisites:

Data
Structures (mandatory)
Schedule:
Week 
Tuesday 
Thursday 
Notes 
Phase 1: Fundamentals  
Week1 
C01 – Introduction 
(휴강1회) 

Week2 
C02 – Fundamentals (Chapter 1 & 2) 
C02 – Solving Recurrences (Chapter 3) 

Week3 
C03  Divide and Conquer (Chapter 4) 
(추석 휴강 1회) 

Week4 
C04  Heap Sort (Chapter 6) 
C05  Quick Sort (Chapter 7) C06 – Sorting in Linear Time (Chapter 9) 

Phase 2: Dynamic Programming  
Week5 
C06  Sorting in Linear Time (Chapter 8) 
C07  Order Statistics (Chapter 9) 

Week6 
C08 – Binary Search Tree and RedBlack Tree (Chapter 1213.1) 
C09 – RedBlack Tree (Chapter 13)  Homework #2. RBDelete (13.4 절)을 읽고, 1. RB_DELETE_FIXUP 이 불리는 경우를 설명하고 2. RB_DELETE_FIXUP의 4가지 경우를 설명하시오 
Week7 
C11 – Dynamic Programming I (Chapter (15.3  15.4) 
C12 – Dynamic Programming II (16.1) 

Week8 
Midterm Exam (보강 – C13 – Greedy
Algorithms (16.2)) 중간고사 성적: 평균 30점대 70점이상 1명 60점이상 6명 50점이상 12명 40점이상 12명 30점이상 13명 20점이상 12명 20점이사 4명  
Phase 3: Graph Algorithms  
Week9/10 
C14 – Elementary Graph Algorithms (Chapter 22) 
C15 – Minimum Spanning Tree (Chapter 23) 

Week11 
C16 – SingleSource Shortest path (Chapter 24) 
C17 – Problem Solving 

Week12 
C18 – Disjoint Sets and Amortized Analysis (Chapter 24.5, Chapter 17) 
C19 – AllPairs Shortest Paths (Chapter 25) 

Week13 
C20 – AllPairs Shortest Paths (Chapter 25) 
C21 – 대체수업 

Phase 4: Advanced
Algorithms  
Week14 
C22 – BTree (Chapter 17) C23  Fibonacci Heap (Chapter 18) 
C24 – Multithreaded Algorithms 

Week15 
C25 – Linear Programming 
C26 – NPCompleteness 

 



Week1 
Final term Exam 결과: 평균 33점 (기본점수 10점) 010 : 6 1120: 9 2130: 17 3140: 7 4150: 13 5160: 7 61 : 3 