MATHS ANEW

• Articles
• Programs with Proofs
• Inspirational
• Other Information

Articles

Sorting Algorithms

• Comparing Performance of Insertion Sort and Selection Sort [html] : counts the transfers and comparisons these algorithms do, and shows when can they outperform each other.
• Worst-Case Number of Comparisons in Sorting [html] : creates a model of comparison-based sorting algorithms, and finds a lower-bound on their worst-case number of comparisons.

Hash Tables

• Primes in Division Method of Hashing [html] : discusses why it is recommended to use modulo prime for division method of hashing.
• Universal Classes of Hash Functions [html] : using the very definition of universal-classes, we can count their functions having certain properties.
• Perfect Hashing: FKS Method [html] : a method to hash a fixed (static) set of keys without collisions (by Fredman, Komlós and Szemerédi), and an implementation of it.

Detecting Cycle in a Sequence

• Cycle Detection: Floyd’s Algorithm [html] : Floyd's Algorithm to solve the generic cycle-detection problem, its mathematical basis and implementation.
• Cycle Detection: Brent’s Algorithm [html] : Brent's Algorithm to solve the generic cycle-detection problem, its mathematical basis and implementation (continuation of the above article).

Fibonacci Numbers

• Some Proofs About Fibonacci Numbers [html] : some basic relations among the Fibonacci Numbers with their proofs.
• Calculating Fibonacci Numbers [html] : two algorithms for computation of Fibonacci Numbers.

Binary Trees

• Successor in Binary Search Trees [html] : method to relate the locations of a node and its successor during Inorder Tree Walk.
• Traversing Binary Trees Iteratively [html] : iterative methods for Preorder, Inorder and Postorder traversals of Binary Trees.

Permutation Generation Algorithms

• Generating Permutations Lexicographically [html] : an algorithm for generating permutations in lexicographical order.
• Generating Permutations with Recursion [html] : four recursive algorithms for permutation generation, all of which fit into a common recursive structure.
• Generating Permutations without Recursion [html] : non-recursive variants of the four recursive algorithms from the above article, all of which fit into a common non-recursive structure.

Euclid's GCD Algorithm

• Euclid’s Algorithm for GCD [html] : discusses the algorithm with its proof, and adds a generic loop-invariant to help prove relations like Bézout's Identity.
• Extended Euclid’s Algorithm [html] : to solve for the integers in Bézout's Identity, the Euclid's Algorithm is extended with new variables and invariants.

Implementing Large Integers

• Implementing Basic Arithmetic for Large Integers: Introduction [html] : discusses how arbitrarily large integers along with basic arithmetic operations can be implemented.
• Implementing Basic Arithmetic for Large Integers: Multiplication [html] : continues the discussion of the above article for multiplication, using Schoolbook and Karatsuba Algorithm.
• Implementing Basic Arithmetic for Large Integers: Division [html] : continues the discussion of the above article for division, using Schoolbook (Long-Division) Algorithm.

Algorithms for Exponentiation and Logarithm

• Some Algorithms for Exponentiation [html] : discusses Binary (Left-to-Right and Right-to-Left) and 2^k-ary Exponentiation algorithms with their implementation.
• Computing Logarithm Bit-by-Bit [html] : a simple algorithm to compute logarithm bit-by-bit, which can also be arrived at by reversing an exponentiation algorithm.

General Concepts in Algorithms

• Maintaining the Stack for Recursion [html] : creating variant of a recursive method by using our own stack.
• Why Some Algorithms Divide Problems Equally [html] : we try to find out why some algorithms, which divide a problem into two subproblems, divide equally.

Miscellaneous Algorithms

• Array Rotation: Dolphin Algorithm [html] : describes the algorithm (also called Juggling Algorithm) along with its mathematical basis, and modifies it for better spatial locality.
• Tower of Hanoi: Transforming the Recursion [html] : the famous recursive algorithm for Tower of Hanoi problem can be transformed into equivalents including non-recursive ones.
• Solving 8-Queens Problem by Generating Permutations [html] : starting with two algorithms for permutation generation, we add a few steps to them to solve the 8-Queens Problem.
• A Simple Algorithm for Generating Combinations [html] : a simple recursive algorithm for generating combinations (subsets of a set) and a non-recursive equivalent of that.

Software

• Software: the Information Machine [html] : a very basic perspective of what is a software.

Basic Mathematics

• A Useful Bound from the Average [html] : given the average of n unknown numbers, what do we know about the proportion of numbers exceeding some threshold?
• Symmetry in the Roots of a Quadratic Equation [html] : we can re-arrange the quadratic equation in two different ways and see symmetry in its roots.

Modular Arithmetic

• Multiples of an Integer Modulo Another Integer [html] : some derivations about multiples of an integer a when taken mod n.

Coq Proofs

• Some Coq Proofs about Natural Numbers : we define natural numbers and some of their operations in Coq, and prove a few useful theorems about them.

Three Distance Theorem, Golden Ratio

• Three Distance Theorem [html] : discusses the theorem and some of its details, considering both rational and irrational numbers.
• Three Distance Theorem: Liang’s Proof [html] : elaborates the elegant proof of Three Distance Theorem given by F. M. Liang.
• Multiples of Golden-Ratio "Modulo" 1 [html] : multiples of golden-ratio, taken "modulo 1" (fractional parts), are studied with the help of Three Distance Theorem.

Programs with Proofs

With Automated Proofs

1. A Sorting-Network
2. Finding Maximum in an Array
3. Array Copy with Overlap
4. Counting Occurrences in an Array
5. Binary Search
6. Computing Fibonacci Numbers
7. Euclid's GCD Algorithm
8. Integer to Base-b Numeral
9. Selection Sort
10. Quick Sort
11. Model-Checking Example with Spin

With Manual Proofs

1. Finding if an Integer is Prime

Inspirational

Simplicity is a great virtue but it requires hard work to achieve it and education to appreciate it. And to make matters worse: complexity sells better.
— Edsger W. Dijkstra

Quotes Archive

Interesting Resources

Other Information

Discussion Group

About Me

For any question or suggestion, please feel free to write to me at [mathsanew@gmail.com].

Copyright © 2020-2022 Nitin Verma. All rights reserved.