Algorithm

Algorithms Are The Building Blocks of Computation and fundamental program for AI.

The algorithm is a step-by-step procedure for solving a problem or accomplishing a task. It's like a recipe for a computer, providing a precise set of instructions to follow.

Characteristics of Algorithms:

• Definiteness: Each step must be precisely defined and unambiguous.
• Effectiveness: The algorithm should lead to a solution in a finite amount of time.
• Finiteness: The algorithm should terminate after a finite number of steps.
• Input: An algorithm takes input data to process.
• Output: An algorithm produces an output, which is the solution to the problem.

Examples of Algorithms in Everyday Life:

• Cooking a recipe: The recipe provides a sequence of steps to follow to create a dish.
• Following directions to a new location: The directions outline a specific route to follow.
• Solving a mathematical equation: The steps involved in solving the equation are an algorithm.

Types of Algorithms:

• Search algorithms: Used to find specific elements within a data structure.
• Sorting algorithms: Used to arrange elements in a specific order.
• Graph algorithms: Used to analyze and manipulate graphs (networks of nodes and edges).
• Numerical algorithms: Used to perform numerical computations, such as solving equations or approximating integrals.

Importance of Algorithms:

• Foundation of computer science: Algorithms are the fundamental building blocks of computer programs.
• Problem-solving: Algorithms provide a systematic approach to solving problems.
• Efficiency: Well-designed algorithms can significantly improve the performance of computer systems.

Bubble Sort Algorithm

    Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent pairs of elements, and swaps them if they are in the wrong order. This process is repeated until no swaps are needed, indicating that the list is sorted.  

function bubble sort(array)

  for i from 0 to array.length - 1

    for j from 0 to array.length - i - 1

      if array[j] > array[j+1]

        swap array[j] and array[j+1]

Explanation:

1. Outer loop: Iterates through the entire array, reducing the unsorted portion by one element in each pass.
2. Inner loop: Compares adjacent elements within the unsorted portion.
3. Comparison and swap: If the current element is greater than the next element, they are swapped.

Example: Sorting an array [64, 34, 25, 12, 22, 11, 90]

Pass 1:

• Compare 64 and 34: Swap
• Compare 34 and 25: Swap
• Compare 25 and 12: Swap
• Compare 12 and 22: No swap
• Compare 22 and 11: Swap
• Compare 11 and 90: No swap

Array after Pass 1: [34, 25, 12, 22, 11, 64, 90]

Continue with subsequent passes until the array is fully sorted.

    Bubble Sort is generally inefficient for large datasets due to its quadratic time complexity. More efficient sorting algorithms like Merge Sort or Quick Sort are often preferred in practice.

    In mathematics and computer science, an algorithm is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning), achieving automation eventually. Using human characteristics as descriptors of machines in metaphorical ways was already practised by Alan Turing with terms such as "memory", "search" and "stimulus".

    In contrast, a heuristic is an approach to problem-solving that may not be fully specified or may not guarantee correct or optimal results, especially in problem domains where there is no well-defined correct or optimal result. For example, social media recommender systems rely on heuristics in such a way that, although widely characterized as "algorithms" in 21st-century popular media, cannot deliver correct results due to the nature of the problem.

    As an effective method, an algorithm can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive states, eventually producing "output" and terminating at a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate random input.

 

Flowchart of using successive subtractions to find the greatest common divisor of numbers r and s

Ancient algorithms 

    Since antiquity, step-by-step procedures for solving mathematical problems have been recorded. This includes Babylonian mathematics (around 2500 BC), Egyptian mathematics (around 1550 BC), Indian mathematics (around 800 BC and later), the Ifa Oracle (around 500 BC), Greek mathematics (around 240 BC), and Arabic mathematics (around 800 AD).

    The earliest evidence of algorithms is found in the mathematics of ancient Mesopotamia (modern Iraq). A Sumerian clay tablet found in Shuruppak near Baghdad and dated to c. 2500 BC describes the earliest division algorithm. During the Hammurabi dynasty c. 1800 – c. 1600 BC, Babylonian clay tablets described algorithms for computing formulas. Algorithms were also used in Babylonian astronomy. Babylonian clay tablets describe and employ algorithmic procedures to compute the time and place of significant astronomical events.

    Algorithms for arithmetic are also found in ancient Egyptian mathematics, dating back to the Rhind Mathematical Papyrus c. 1550 BC. Algorithms were later used in ancient Hellenistic mathematics. Two examples are the Sieve of Eratosthenes, which was described in the Introduction to Arithmetic by Nicomachus,  and the Euclidean algorithm, which was first described in Euclid's Elements (c. 300 BC).  Examples of ancient Indian mathematics included the Shulba Sutras, the Kerala School, and the Brāhmasphuṭasiddhānta.

    The first cryptographic algorithm for deciphering encrypted code was developed by Al-Kindi, a 9th-century Arab mathematician, in A Manuscript On Deciphering Cryptographic Messages. He gave the first description of cryptanalysis by frequency analysis, the earliest codebreaking algorithm. 

Computers

Weight-driven clocks

    Bolter credits the invention of the weight-driven clock as "the key invention of Europe in the Middle Ages," specifically the verge escapement mechanism that provides the tick and tock of a mechanical clock. "The accurate automatic machine" led immediately to "mechanical automata" beginning in the 13th century and finally to "computational machines"—the difference and analytical engines of Charles Babbage and Ada Lovelace in the mid-19th century. Lovelace is credited with the first creation of an algorithm intended for processing on a computer, Babbage's analytical engine, which is the first device considered a real Turing-complete computer instead of just a calculator. Lovelace is sometimes called "history's first programmer" as a result, though full implementation of Babbage's second device would not be realized until decades after her lifetime.

Electromechanical relay 

    Bell and Newell (1971) write that the Jacquard loom, a precursor to Hollerith cards (punch cards), and "telephone switching technologies" led to the development of the first computers. By the mid-19th century, the telegraph, the precursor of the telephone, was in use throughout the world. By the late 19th century, the ticker tape (c. 1870s) was in use, as were Hollerith cards (c. 1890). Then came the teleprinter (c. 1910) with its punched-paper use of Baudot code on tape.

Telephone-switching networks of electromechanical relays were invented in 1835. These led to the invention of the digital adding device by George Stibitz in 1937. While working in Bell Laboratories, he observed the "burdensome" use of mechanical calculators with gears. "He went home one evening in 1937 intending to test his idea... When the tinkering was over, Stibitz had constructed a binary adding device".

Babylonian division algorithm. 

    This ancient method, dating back to around 2500 BC, provides a fascinating glimpse into the mathematical practices of early civilizations. Unlike our modern long division, the Babylonians used a technique based on successive doubling and halving.

Simplified explanation:

1. Convert to base 60: The Babylonians used a base 60 numeral system, so any given number would be represented in terms of 60s and 1s.
2. Set up the problem: The dividend would be placed on the left, and the divisor on the right.
3. Double and halve: The divisor would be repeatedly doubled until it exceeded the dividend. Simultaneously, the dividend would be repeatedly halved.
4. Subtract: Find the largest multiple of the doubled divisor that is less than or equal to the dividend. Subtract this multiple from the dividend.
5. Repeat: Continue doubling and halving, subtracting as needed, until the dividend is reduced to zero.
6. Sum the results: The sum of the halved dividends corresponding to the subtracted multiples would be the quotient.

Dividend: 120 Divisor: 15

                    60               30

                    30               60

                    15              120

                    7.5             240

                  3.75             480

                 1.875            960

               0.9375           1920

Example:

• Divide 120 by 15
• Babylonian representation: 120 = 260 + 0, 15 = 160 + 0

Shulba Sutra

    The Shulba Sutras are part of the larger corpus of texts called the Shrauta Sutras, considered to be appendices to the Vedas. They are the only sources of knowledge of Indian mathematics from the Vedic period. Unique Vedi (fire-altar) shapes were associated with unique gifts from the Gods. For instance, "he who desires heaven is to construct a fire-altar in the form of a falcon"; "a fire-altar in the form of a tortoise is to be constructed by one desiring to win the world of Brahman" and "those who wish to destroy existing and future enemies should construct a fire-altar in the form of a rhombus". 

* Note here that these sutras is rooted in ancient practices and beliefs so sorting the unwanted information from plain mathematics is critical works to be done. 

    The four major Shulba Sutras, which are mathematically the most significant, are those attributed to Baudhayana, Manava, Apastamba and Katyayana. Their language is late Vedic Sanskrit, pointing to a composition roughly during the 1st millennium BCE. The oldest is the sutra attributed to Baudhayana, possibly compiled around 800 BCE to 500 BCE. Pingree says that the Apastamba is likely the next oldest; he places the Katyayana and the Manava third and fourth chronologically, based on apparent borrowings. According to Plofker, the Katyayana was composed after "the great grammatical codification of Sanskrit by Pāṇini in probably the mid-fourth century BCE", but she places the Manava in the same period as the Baudhayana.

    The Vedic veneration of Sanskrit as a sacred speech, whose divinely revealed texts were meant to be recited, heard, and memorized rather than transmitted in writing, helped shape Sanskrit literature in general. Thus texts were composed in formats that could be easily memorized: either condensed prose aphorisms (sūtras, a word later applied to mean a rule or algorithm in general) or verse, particularly in the Classical period. Naturally, ease of memorization sometimes interfered with ease of comprehension. As a result, most treatises were supplemented by one or more prose commentaries"

    There are multiple commentaries for each of the Shulba Sutras, but these were written long after the original works. The commentary of Sundararāja on the Apastamba, for example, comes from the late 15th century CE and the commentary of Dvārakãnātha on the Baudhayana appears to borrow from Sundararāja. According to Staal, certain aspects of the tradition described in the Shulba Sutras would have been "transmitted orally", and he points to places in southern India where the fire-altar ritual is still practised and an oral tradition preserved. The fire-altar tradition largely died out in India, however, and Plofker warns that those pockets where the practice remains may reflect a later Vedic revival rather than an unbroken tradition. Archaeological evidence of the altar constructions described in the Shulba Sutras is sparse. A large falcon-shaped fire altar (śyenaciti), dating to the second century BCE, was found in the, 1957-59, excavations by G. R. Sharma at Kausambi, but this altar does not conform to the dimensions prescribed by the Shulba Sutras.

There is a claim we often hear that Sanskrit is well-suited for computer languages and here is why:

1. Precision and Formalism: Sanskrit is known for its highly structured grammar and precise rules. This can be seen as analogous to the formal syntax and rules of computer programming languages.
2. Clarity and Conciseness: Sanskrit's grammatical structure can be argued to promote clarity and conciseness in expression, which are desirable qualities in programming languages.
3. Rich Vocabulary: Sanskrit boasts a vast vocabulary, which could potentially provide a rich source of terms for programming concepts.

However, it's important to note a few counterarguments:

1. Readability: While Sanskrit's precision can be beneficial, it might also make the code more difficult for non-Sanskrit speakers to read and understand.
2. Practicality: Modern programming languages are designed with specific goals in mind, such as efficiency, portability, and ease of use. It's not clear if Sanskrit would necessarily provide a significant advantage over existing languages in these areas.
3. Cultural and Historical Context: The development of computer languages is largely influenced by Western culture and technological advancements. While Sanskrit has a rich history, it might not align perfectly with the specific needs and conventions of modern programming.

mathematical constant π

3.1415926535897932384626433...

    Baudhayana Shulba sutra gives the construction of geometric shapes such as squares and rectangles. It also gives, sometimes approximate, geometric area-preserving transformations from one geometric shape to another. These include transforming a square into a rectangle, an isosceles trapezium, an isosceles triangle, a rhombus, and a circle, and transforming a circle into a square. In these texts, approximations, such as the transformation of a circle into a square, appear side by side with more accurate statements. As an example, the statement of circling the square is given in Baudhayana as:

     If it is desired to transform a square into a circle, [a cord of length] half the diagonal [of the square] is stretched from the centre to the east [a part of it lying outside the eastern side of the square]; with one-third [of the part lying outside] added to the remainder [of the half diagonal], the [required] circle is drawn.

The statement of squaring the circle is given as:

 To transform a circle into a square, the diameter is divided into eight parts; one [such] part after being divided into twenty-nine parts is reduced by twenty-eight of them and further by the sixth [of the part left] less the eighth [of the sixth part] Alternatively, divide [the diameter] into fifteen parts and reduce it by two of them; this gives the approximate side of the square [desired].

The constructions in 2.9 and 2.10 give a value of π as 3.088, while the construction in 2.11 gives π as 3.004.

Square root

    Altar construction also led to an estimation of the square root of 2 as found in three of the sutras. In the Baudhayana sutra, it appears as:

    The measure is to be increased by its third and this [third] again by its own fourth less the thirty-fourth part [of that fourth]; this is [the value of] the diagonal of a square [whose side is the measure].

Which leads to the value of the square root of two as being:

    Indeed, an early method for calculating square roots can be found in some Sutras, the method involves the recursive formula:  for large values of x, which bases itself on the non-recursive identity for values of r extremely small relative to a. 

    It has also been suggested, for example by Bürk that this approximation of √2 implies knowledge that √2 is irrational. In his translation of Euclid's Elements, Heath outlines several milestones necessary for irrationality to be considered to have been discovered and points out the lack of evidence that Indian mathematics had achieved those milestones in the era of the Shulba Sutras.

 

Falcon-shaped vedi excavated from Purola, Uttarkashi; likely belonging to the Kuninda period (1st - 250 CE).

    The future of geometry plays a fundamental role in quantum computing by providing a framework for understanding and manipulating quantum information, designing robust quantum systems, and developing efficient quantum algorithms.