2025-Fall ST: Parameterized Algorithms (CSED701A-01) The course syllabus

1.Course Information

Course No. CSED701A Section 01 Credit 3.00
Category Major elective Course Type prerequisites
Postechian Core Competence
Hours TUE, THU / 14:00 ~ 15:15 / Science BldgⅡ[109]Lecture Room Grading Scale G

2. Instructor Information

Oh Eunjin Name Oh Eunjin Department Dept. of Computer Science & Eng.
Email address jin9082@postech.ac.kr Homepage https://sites.google.com/view/eunjinoh/
Office 알고리즘 연구실 Office Phone 054-279-2389
Office Hours

3. Course Objectives

매개변수 복잡도 이론 (parameterized complexity) 는 고전적인 알고리즘 분석법에서 벗어나 고전적인 방법보다 더 정밀하게 알고리즘의 수행 시간을 분석하기 위해 도입된 이론이다. 고전적인 분석법은 알고리즘의 수행 시간을 입력 값의 크기에 대한 함수로 표현한다. 반면에 매개변수 복잡도 이론에서는 새로운 하나 이상의 파라미터를 도입하여 알고리즘의 수행 시간을 이 파라미터와 입력 값의 크기의 함수로 표현한다. 이를 통해 고전적인 분석법보다 더 정교하게 알고리즘의 퍼포먼스를 분석할 수 있다.
본 과목에서는 효율적인 매개변수 알고리즘과 이를 설계하기 위한 몇가지 테크닉을 공부한다. 또한 W-hierarchy 등 매개변수 복잡도 이론 (parameterized complexity) 의 중요한 개념도 다룬다.

4. Prerequisites & require

(추천 선수) CSED 331알고리즘

5. Grading

중간고사(30%), 기말고사(20%), 과제(30%) 발표(20%)

6. Course Materials

Title Author Publisher Publication
Year/Edition		 ISBN
Parameterized Algorithms Marek Cygan, Fedor V.Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk Michal Pilipczuk, Saket Saurabh Springer Cham 2015 978-3-319-21274-6

7. Course References

8. Course Plan

1주차: Introduction to parameterized algorithms
2주차: Kernelization
3주차: Bounded search trees
4주차: Iterative compression
5주차: Randomized methods in parameterized algorithms
6주차: Graph minor theory
7주차: Treewidth I
8주차: 중간고사
9주차: Treewidth II
10주차: Treewidth III
11주차: W-hierarchy
12주차: Lower bounds based on ETH I
13주차: Lower bounds based on ETH II
14주차: Presentation
15주차: 기말고사

9. Course Operation

이론강의, 발표

10. How to Teach & Remark

11. Supports for Students with a Disability

- Taking Course: interpreting services (for hearing impairment), Mobility and preferential seating assistances (for developmental disability), Note taking(for all kinds of disabilities) and etc.

- Taking Exam: Extended exam period (for all kinds of disabilities, if needed), Magnified exam papers (for sight disability), and etc.

- Please contact Center for Students with Disabilities (279-2434) for additional assistance

Copy The course syllabus
No. Semester Name Course No. Section Course Name