This seminar gives graduate students the opportunity to hear and present talks on discrete mathematics, either on topics beyond a standard combinatorics class or on original research. GCS is meant to be a friendly, slightly informal speaking environment where questions are encouraged at all points throughout the talk. We only assume a basic general knowledge of combinatorics (at most, basic combinatorics one might learn in a single semester introductory course), so students in any area are welcome to attend.
Speakers for the GCS are welcome (from the math department, other departments, and elsewhere). Please email Corrine Yap at
Generously sponsored by DIMACS.
Click here for information about the seminar and the archive.
|Date:||December 4th, 2019|
|Place:||Graduate Student Lounge, 7th Floor, Hill Center|
|Title:||Dynamic Programming and Combinatorial Game Theory|
|Abstract:||In this talk we will talk about dynamic programming and combinatorial game theory. Dynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions using a memory-based data structure. We will see some problems that can be solved by dynamic programming. Then we will discuss impartial games, especially Nim and how we can use dynamic programming to find Sprague–Grundy function values so that we know where are winning positions and where are losing positions. A winning strategy follows. Sprague–Grundy theorem will also be mentioned.|