# Tag Archives: computer science

## Polynomial Multiplication, Karatsuba and Fast Fourier Transform

Let’s say you want to write a short program to multiply two linear functions f(x) = ax+b and g(x) = cx+d and compute the coefficients of the resulting product: You might think it’ll take 4 multiplications (for ac, ad, bc and bd) and 1 addition (for ad+bc), but there’s … Continue reading

## Combinatorial Game Theory Quiz 3

The quiz lasts 75 minutes and covers everything from lessons 1-12. For each of the following Nim games, find one good move for the first player, if any. (10 points) [ Note : exactly one of the games is a … Continue reading

## Combinatorial Game Theory XII

Lesson 12 Recall the following Domineering configuration in lesson 10: The above game has a nice theory behind it. Definition : For any game G, the game –G (called miny–G) is defined to be:   The game +G (called tiny–G) is defined … Continue reading

Posted in Notes | | 1 Comment

## Combinatorial Game Theory XI

Lesson 11 In this lesson, we will cover more on canonical forms. First recall that for m↑ + (*n) with m > 0, this game is positive except when (m, n) = (1, 1). Let’s consider the canonical forms of … Continue reading

## Combinatorial Game Theory X

Lesson 10 In lesson 7, we learnt that if A, B are Left’s options in a game with A ≥ B, then we can drop B from the list of options and the game remains equal. In this lesson, we will … Continue reading

## Combinatorial Game Theory Quiz 2

This quiz lasts 70 minutes and covers materials from lessons 1-9. Use the simplicity rule to compute the values of the following games. (10 points) {1/2 | } {-1/4 | } {1/8 | 3/8} {0 | 7/8} {1/8 | 9/16} … Continue reading

## Combinatorial Game Theory IX

Lesson 9 Typically, at the end of a Domineering game, the board is divided into disjoint components, so the overall game is the (game) sum of the individual components. Suppose we have the following 6 components: How should the next … Continue reading

## Combinatorial Game Theory VIII

Lesson 8 In this lesson, we will further familiarise ourselves with games involving numbers. At the end of the lesson, we will encounter our first positive infinitesimal: the “up” ↑. Here, an infinitesimal is a value which is strictly between –r and r … Continue reading

## Combinatorial Game Theory VII

Lesson 7 [ Warning: another long post ahead. One of the proofs will also require mathematical induction. ] In this lesson, we will see how some games can be represented by numbers (which can be integers or fractions). We will also … Continue reading