DCRC

Algorithms

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, 3rd edition)

-      (2nd 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%

-      Mid-term 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 Red-Black Tree (Chapter 12-13.1)

C09 – Red-Black Tree (Chapter 13)

Homework #2.

RB-Delete (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

Mid-term 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 – Single-Source Shortest path

(Chapter 24)

C17 – Problem Solving

출석 확인 링크

 

Week12

 

C18 – Disjoint Sets and Amortized Analysis (Chapter 24.5, Chapter 17) 

C19 – All-Pairs Shortest Paths

(Chapter 25)

 

Week13

 

C20 – All-Pairs Shortest Paths

(Chapter 25)

C21 – 대체수업

 

Phase 4:  Advanced Algorithms

Week14

C22 – B-Tree (Chapter 17)

C23 - Fibonacci Heap (Chapter 18)

C24 – Multithreaded Algorithms

 

Week15

 

C25 – Linear Programming

C26 – NP-Completeness

 

-



 

Week1


Final term Exam

결과: 평균 33점 (기본점수 10점)


0-10 : 6

11-20: 9

21-30: 17

31-40: 7

41-50: 13

51-60: 7

61- : 3