Course syllabus
The syllabuses on both this page and the NTU online course information are synchronized.
Course Information
| Item | Content |
| Course title | Combinatorics (Ⅱ) |
| Semester | 114-2 |
| Designated for | GRADUATE INSTITUTE OF MATHEMATICS |
| Instructor | SHAGNIK DAS |
| Curriculum No. | MATH 7702 |
| Curriculum Id No. | 221 U3300 |
| Class | |
| Credit | 3 |
| Full/Half Yr. | Half |
| Required/Elective | Elective |
| Time | Tuesday 8,9(15:30~17:20)Friday 5(12:20~13:10) |
| Place | 天數202 |
| Remarks | The course is conducted in English。Academic Fields in Graduate Students :A,B,D,E,F Target Students :M,D |
Course Syllabus
| Item | Content |
| Course Description | In this course, we will study the use of algorithms in combinatorics. We will begin by analysing some important algorithms on graphs, introducing the basics of complexity theory in the process. The main part of the course, though, will concern the use of algorithmic thinking to prove theoretical results. For example, we will see how one can use network flows and the Ford-Fulkerson algorithm to prove results about graph connectivity, or how linear programming can be applied to several problems in the field. Finally, we will discuss probabilistic algorithms, and to what extent they can be derandomized for applications. |
| Course Objective | • Cover important graph algorithms for spanning trees, matchings, and more • Use algorithms to prove theoretical results about connectivity, colouring, etc. • Learn how to analyse randomized algorithms, and how to make them deterministic |
| Course Requirement | Successful completion of Combinatorics I or Graph Theory I, or an equivalent course Knowledge of linear algebra, calculus and probability |
| Expected weekly study hours before and/or after class | |
| References | Some course notes will be made available, but students are encouraged to take their own notes from lectures The following texts are useful references • Lovász, Pelikán and Vesztergombi: Discrete Mathematics • Matoušek and Gärtner: Understanding and Using Linear Programming • Hefetz, Krivelevich, Stojaković and Szabó: Positional Games |
| Designated Reading |
Progress
| Week | Date | Topic |
Makeup Class Information
| NO | Date | Start Time | End Time | Location or Method |
Grading
| NO | Item | Pc | Explanations for the conditions |
| 1 | Homework | 30% | Regular homework assignments covering topics from recent lectures |
| 2 | Midterm | 30% | Midterm exam, to be held in Week 8, covering the material to date |
| 3 | Final | 40% | Final exam, to be held in Week 16, covering the entire course |
Adjustment methods for students
| Adjustment method | |
| Teaching methods | |
| Assignment submission methods | |
| Exam methods | |
| Others |
Office Hour
| Remarks | Office hours available upon request |