23-misc-math

Unit 23: Miscellaneous math

This unit covers some specific, more mathematical concepts that did not fit into other units:

• Fast pow (logarithmic computation of powers)
• Matrix product
• Fibonacci numbers (and their computation with matrix powers)
• Powers of an adjacency matrix
• The "tortoise and hare" method for cycle detection

Prerequisites

• Unit 1: Complexity
• Unit 4: Graph basics (for adjacency matrix)

Practice problems

Easy

• UVa 10229 - Modular Fibonacci
• UVa 350 - Pseudo-Random Numbers

Less easy

• UVa 12470 - Tribonacci
• UVa 11486 - Finding Paths in Grid

Not easy unless you know the solution in advance

• UVa 10655 - Contemplation! Algebra