Abstract

Consider the popular game Coins in a Row, where n coins with different denominations (or values) are arranged in a row. Two players alternatively take coins from either end of the row, and the player who picks the larger sum wins. If both players play optimally, then we are interested in calculating the maximum profit (or minimum loss) obtainable by the first player. An O(n^2) solution is very well-known, and is commonly used to illustrate the dynamic programming technique. In this talk, I will present a very elegant O(n) solution, and a fast solution to a harder variation of the problem in which we are given k rows and stacks of coins, where players alternatively pick from the two ends of any row, or from a single end of any stack. This problem appeared in the Polish Olympiad for Informatics, a programming contest for high schoolers, and the solution uses some very interesting techniques. The seminar audience is encouraged to find a fast solution before the talk.

About the Speaker

I am an assistant professor (teaching track) of computer science at Florida Institute of Technology. I received my Ph.D. from Clemson University under the supervision of Dr. Brian Dean in December 2016. I am fascinated by everything that involves algorithms. My research interests broadly include competitive programming, theoretical algorithms and data structures, graph theory, and computer science education. Lately, I am also venturing on projects that involve writing simple artificial intelligence agents to two player adversarial games.