Knuth-Yao Optimization in DP
Knuth-Yao Optimization in DP. More or less an excuse to try out Typst.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
math notes
Sheila Liming: Writing is the act of trying to create a record of your understanding of something. (from the Ezra Klein Show Podcast, Episode ‘The Quiet Catastrophe’)
Collection of math/cs notes and problems written up over the years for my own amusement. Topics are at the undergraduate college level. Normally notes like these would be written with a pencil in a notebook. LaTeX makes it very easy to produce publishing quality typesetting of mathematical texts, so blame LaTeX for this collection. Hopefully others will find some of these useful. Also available is the whole collection as one book and the Github repo with all the LaTeX sources.
Errors and misunderstandings in these notes are solely my fault. Nothing here is original. I tried to be complete about attributions and citations but if I missed something, I apologize.
Also caveat emptor: Nobody has done any proofreading on these notes.
n-th root
Existence of n-th root.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
Sequences and Series
Select exercises on sequences and series.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
Two algebraic delights
Finding a correspondence between mathematical objects and algebraic expressions.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
Burnside Polya counting
Counting number of ways to color some objects under the action of a group.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
Enigma
Enigma Machines and how the internal wiring of their rotors was reverse-engineered is the topic of this note.
I pieced this together from several sources, so it is a little convoluted but it mainly follows chapter 3.8 from the book Abstract Algebra by Lawrence and Zorzitto, albeit in a perhaps simplified, less rigorous way.
Rejewski and his team of code breakers did a lot more than what is described in this note. For example, they designed and prototyped electro-mechanical computers to take over some of the tedious manual labor that was still needed to sift through possible permutations. Later, at Bletchley Park, Alan Turing and his team scaled up those prototypes and made the Bombe.
Prison cells
A prison has $n$ cells with all cell doors shut initially.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
Trailing zeros in factorial
How many trailing zeros are in $n!$.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
Points on circle
Points on circle.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
Fibolucci
Exercise ‘Fibolucci’ from ‘Kaldewaij. Programming, The Derivation of Algorithms . Prentice Hall, 1990’.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
Sequences
Counting inversions is the topic of the problem in this note.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
No consecutive ints
Integer equations and multisets are the topics of the problem.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
Three plus sqrt of five
Recurrence relations and modulo arithmetic are the topics of the problem in this note.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
Bridge
Four people begin on the same side of a bridge. You must send them across to the other side in the fastest time possible. It is night. There is one flashlight. A maximum of two people can cross at a time. Any party who crosses, either one or two people, must have the flashlight to see.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
Dutch National Flag
The Dutch National Flag Problem from ‘Kaldewaij. Programming, The Derivation of Algorithms . Prentice Hall, 1990’.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
Minkowski Sum
Fast Fourier Transform and using it to speed up polynomial multiplication is the topic of the two problems in this note taken from Algorithms — Extended Dance Remix: Fast Fourier Transforms.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
While A
Loop invariants is the topic of the problem in this note.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
Bernstein
Cool proof of the Schröder-Bernstein Theorem.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
Maximum subsequence
Maximum subsequence problem.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.
Airplane Seating
A line of $n$ airline passengers is waiting to board a plane.
open full screen ↗ Your browser can't display this PDF inline. Open it directly.