Tag Archives: programming

Schreier-Sims Algorithm

Introduction Throughout this article, we let G be a subgroup of generated by a subset  We wish to consider the following questions. Given A, how do we compute the order of G? How do we determine if an element lies in G? Assuming , how … Continue reading

Posted in Uncategorized | Tagged , , , , , , | Leave a comment

Primality Tests III

Solovay-Strassen Test This is an enhancement of the Euler test. Be forewarned that it is in fact weaker than the Rabin-Miller test so it may not be of much practical interest. Nevertheless, it’s included here for completeness. Recall that to … Continue reading

Posted in Uncategorized | Tagged , , , , , , , | Leave a comment

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

Posted in Notes | Tagged , , , , , | Leave a comment

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

Posted in Homework | Tagged , , , , , , | Leave a comment

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

Posted in Notes | Tagged , , , , , , , , | Leave a comment

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

Posted in Notes | Tagged , , , , , , , , | Leave a comment

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

Posted in Notes | Tagged , , , , , , , | Leave a comment

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

Posted in Notes | Tagged , , , , , , | Leave a comment

Combinatorial Game Theory VI

Lesson 6 General Combinatorial Game Theory [ Warning: the following lesson is significantly longer than the previous ones. ] Starting from this lesson, we will look at a more rigourous, complete and general theory. Prior to this, in any game configuration both … Continue reading

Posted in Notes | Tagged , , , , , , , , | Leave a comment

Combinatorial Game Theory V

Lesson 5 We did mention in the first lesson that CGT covers games without draws. Here, we’ll break this rule and look at loopy games, i.e. games with possible draws. [ To be specific, loopy games are those where it’s … Continue reading

Posted in Notes | Tagged , , , , , , | 5 Comments