#### 2020 Spring Course

##### CSED331-01 Algorithms

###### 1. Course Information

Instructor : Prof. Hee-Kap Ahn

TA : Seungjun Lee / Byeonguk Kang / Hyunjun Kim / Hwi Kim

Lecture room : POSTECH Library(Tae-Joon Park Digital Library) Seminar room [502]

Lecture hours : Monday & Wednesday 09:30~10:45

## Course Syllabus

###### 2. Course Objectives

Algorithms are procedures or methods that solve problems arising across the full range of computing applications. Algorithmic problems from those areas, however, are rarely mathematically well-formed and they often come with application-specific details, most of which are extraneous. The goal of this course is to understand how to formulate problems, and from this, how to design efficient algorithms for the resulting problems. The course starts with an introduction to algorithms. Then we study four essential algorithm design techniques: greedy algorithms, divide and conquer, dynamic programming, and network flow. We will also spend a few weeks on computational intractability and approximation algorithm, a technique for dealing with computational intractable problems.

###### 3. Prerequisites & require

CSED101 Programming and Problem Solving

CSED233 Data structure

###### 4. Grading

Midterm exam : 30%, Final exam : 30%, Homework : 20%,

Problem solving (programming, project) : 20%

###### 5. Course Materials

Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, 2008, McGraw-Hill International Edition.

###### 6. Course References

Algorithm Design by Jon Kleinberg and Éva Tardos, 2006, Addison Wesley.

###### 7. Course Plan

# Week 1 : Introduction

# Week 2 : Divide-and-Conquer

# Week 3-4 : Graph algorithms

# Week 5-6 : Greedy algorithms

# Week 6-7 : Dynamic programming

# Week 8 : Midterm exam.

# Week 9-10 : Linear programming and reductions

# Week 11-12 : Computational intractability

# Week 13-14 : Approximation algorithms

# Week 15 : Randomized algorithms

# Week 16 : Final exam.

###### 8. Course Operation

Lecture

Programming Assignment

Hand writing HW

###### 9. About POSTECHx(POSTECH Online Lecture Site)

1. Login POSTECHx

2. Search “알고리즘 (Algorithms)”

3. Press “신청”

###### 10. About Handwrite Homework

Choose one submit way.

1. Submit Algorithms Lab(B2-208).

2. Scan or take a picture your HW and submit by e-mail to TA.

3. We also receive tablet handwriting.

* You cannot use word processor.

###### 11. About Domjudge Assignment

Our Domjudge Site : https://domjudge.postech.ac.kr

Please read “Intro” before using Domjudge

##### CSED536-01 Advanced Algorithms

###### 1. Course Information

Instructor : Prof. Eunjin Oh

TA : Taehoon Ahn

Lecture room : 2B-108

Lecture hours : Monday & Wednesday 11:00~12:15

## Course Syllabus

###### 2. Course Objectives

This course covers advanced topics of algorithms including graph algorithms, geometric algorithms, approximation algorithms, and randomized algorithms. We study how to design efficient algorithms using essential design and analysis methods.

###### 3. Prerequisites & require

CSED331 Algorithms

###### 4. Grading

Midterm exam : 40%, Final exam : 40%, Homework : 20%

###### 5. Course Materials

Computational Geometry: Algorithms and Applications by Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars, 2008, Springer.

###### 6. Course References

https://en.wikipedia.org/wiki/Book:Graph_Algorithms

###### 7. Course Plan

Graph Theory and Algorithms

(1) Introduction: Paths, Cycles, Shortest paths

(2) Graph Traversal and Tour

(3) Planar graphs

(4) Interval graphs, Chordal graphs, Perfect graphs

(5) Bipartite Graphs

(6) Cliques, Coloring, Matchings

(7) Disjoint Sets, Heaps

(8) Dominating Set, Independent Set, Vertex Cover

(9) Graph Isomorphism

Geometric Algorithms

(1) Convex Hulls

(2) Line Segment Intersection

(3) Polygon Triangulation

(4) Linear Programming

(5) Orthogonal Range Searching

(6) Point Location

(7) Voronoi Diagrams

(8) Arrangements and Duality

(9) Delaunay Triangulations

(10) Geometric Data Structures

###### 8. Course Operation

Lecture

Hand writing HW

###### 9. About POSTECHx(POSTECH Online Lecture Site)

1. Login POSTECHx

2. Search “고급 알고리즘”

3. Press “신청”

###### 10. About Handwrite Homework

Choose one submit way.

1. Submit Algorithms Lab(B2-208).

2. Scan or take a picture your HW and submit by e-mail to TA.

3. We also receive tablet handwriting.

* You cannot use word processor.