Generally AI - Season 2 - Episode 2: Fantastic Algorithms and Where to Find Them

Dijkstra's Algorithm and Early Computing

• Edsger W. Dijkstra invented his shortest path algorithm in 20 minutes on a cafe terrace in the Netherlands, without using a pencil and paper, which helped him avoid unnecessary complexities (10s).
• Dijkstra initially published his algorithms without using a machine, relying on researchers to manually verify the correctness of the algorithms by examining them for a long time (51s).
• A mathematician or logician once said, "I have not tested this code, I've merely proved it correct," highlighting the early lack of a notion of proof of correctness for algorithms (1m13s).

Origins of the Shortest Spanning Tree Algorithm

• The shortest spanning tree algorithm was initially invented to save copper wire on a large electric panel by finding the shortest path to ground all points (1m55s).

Mathematical Habits and Algorithm Origins

• Mathematicians from different specialties, algebra and analysis, tend to eat corn on the cob in different patterns, with algebraists using a raster pattern and analysts using a spiral pattern (2m25s).

The Origin of Algorithms in Khwarizm

• The discussion is about favorite algorithms, and the host, Roland, is curious about where algorithms come from, which leads to the revelation that algorithms originated from Uzbekistan, specifically from the region of Khwarizm (4m6s).
• Muhammad ibn Musa, a mathematician from Khwarizm, is mentioned as a key figure in the origin of algorithms (4m23s).

Alisi and the Hindu Numeral System

• Alisi, an astronomer and head of the House of Wisdom in Baghdad, was born around 780 and appointed to his position in approximately 820, during a cultural Golden Age where scholars were translating ancient Greek texts and doing original work (4m39s).
• Alisi wrote a book in Arabic about calculations using the Hindu numerals, which introduced the place value number system that is used today, as opposed to ancient systems like Roman numerals that used letters for numbers (5m19s).
• The modern numeral system was invented in India between the first and fourth centuries and spread to the Islamic world, eventually reaching Alisi, who wrote a very influential book on how to use these numerals and the positional system to do arithmetic (6m11s).
• Alisi's original text is lost, but it was translated into Latin, and his name was latinized to Algorism, Algarismos, Algorithm, and the translation of his book was called "Alisi on the Hindu Art of Reckoning" (6m33s).
• The word "algorithm" comes from Alisi's name, and it refers to a finite sequence of mathematically rigorous instructions used to solve specific problems or perform a computation (7m17s).

The Spread and Adoption of the Hindu Numeral System

• The first algorithms learned by most students are those for basic arithmetic, such as addition and subtraction, which is what Alisi's book originally covered (7m33s).
• Alisi's work was translated into Latin and introduced to the West in the 12th century, but it didn't gain popularity until the 13th century with the help of a book called "Liber abachi" written by Leonardo of Pisa, also known as Fibonacci (8m22s).
• Fibonacci's surname is a patronymic surname, meaning "son of Bonacci," and is not directly related to the famous sequence that bears his name (8m57s).
• Leonardo Fibonacci's book, "Liber abachi," describes methods of calculation without an abacus using the Hindu numeral system, which is also known as the Arabic number system (9m29s).
• The book introduced the Arabic number system to the West and started its adoption due to the easy algorithms for addition and subtraction (10m5s).
• For centuries after the book, people who followed Fibonacci's methods were called "algorists," while those who continued to use the traditional abacus were called "abacists" (10m17s).
• The use of the abacus did not disappear immediately, and there were still people who preferred to use it even after the introduction of the Arabic number system (10m23s).

Fibonacci and the Fibonacci Sequence

• Fibonacci is also famous for the sequence that bears his name, where each number is the sum of the two preceding numbers (11m50s).
• Calculating the nth number in the Fibonacci sequence is often used as an example of recursion in programming, and it is a popular software interview question (12m14s).
• The recursive implementation of the Fibonacci sequence has a high complexity, which can be used to discuss the complexity of algorithms (12m47s).
• The Fibonacci sequence can be approached numerically, and its complexity is exponential, with a time complexity equivalent to the Fibonacci number itself (13m1s).
• To speed up the calculation of the Fibonacci sequence, memorization can be used, and non-recursive implementations such as iterative calculation are also available (13m18s).
• The golden ratio can be used to approximate the nth Fibonacci number, with a formula involving the golden ratio (approximately 1.618) raised to the nth power and divided by the square root of five (13m31s).
• The error in this approximation is very small, less than 0.1, once past the fourth or fifth Fibonacci number (14m29s).

Al-Khwarizmi and the Origin of Algebra

• Al-Khwarizmi, also known as Algorithmus, wrote a book that introduced systematic methods for solving linear and quadratic equations, which is where the word "algebra" originates (14m49s).
• Al-Khwarizmi's approach involved standard operations, which can be considered as algorithms for doing algebra, and he is also credited with algorithms for the decimal system (15m34s).
• The AI connection to Al-Khwarizmi's work is linear algebra, which is the foundation of neural networks (15m43s).

Favorite Algorithms and the AI Connection

• The Fibonacci sequence and Al-Khwarizmi's work are two favorite algorithms, with the approximate Fibonacci formula being a particularly interesting one (16m3s).

Probabilistic Counting and the HyperLogLog Algorithm

• Probabilistic counting is a method used to estimate the number of unique elements in a set, which can be useful when an exact count is not necessary, such as estimating the number of unique visitors to a website or listeners to a podcast (17m39s).
• The problem of counting unique visitors arises when the same person may visit a website or listen to a podcast multiple times, and simply counting the total number of visits or listens would result in an overcount (18m29s).
• A naive approach to solving this problem would be to add each visitor's name to a list, remove duplicates, and then count the number of unique names, but this method would require a lot of memory and computation (19m15s).
• The HyperLogLog algorithm is a probabilistic counting method that uses hash functions to estimate the number of unique elements in a set, and is more memory-efficient than the naive approach (19m50s).
• The HyperLogLog algorithm works by taking the hash of each unique ID, viewing it as a binary number, and using the resulting bits to estimate the number of unique elements in the set (21m13s).
• The name "HyperLogLog" comes from the fact that it is an improvement over an earlier algorithm called "HyperLog", and there is also a further improvement called "HyperLogLog Plus+" (20m10s).
• The HyperLogLog algorithm is used by websites such as Reddit to estimate the number of unique visitors to their site (20m38s).
• The algorithm is useful for estimating the size of a set when an exact count is not necessary, and can be used in a variety of applications, such as estimating the number of unique listeners to a podcast (19m10s).
• A good hash function can be used to estimate the number of unique visitors to a website, with the assumption that the binary representation of the hash is equally likely to have a one or a zero in each spot (21m36s).
• The hash can be treated as a dice roll or consecutive coin flips, allowing for the counting of leading zeros to estimate the number of unique visitors (21m50s).
• The probability of a hash starting with a certain number of leading zeros decreases exponentially, with one in 256 chance of having eight leading zeros and one in 65,536 chance of having 16 leading zeros (22m25s).
• By keeping track of the maximum number of leading zeros seen, a website can estimate the number of unique visitors, with a mathematical expectation of 256 people for eight leading zeros and 65,536 people for 16 leading zeros (23m0s).
• This method requires minimal memory, with only 32 bits needed to count an estimate of the number of people (23m30s).
• The error band of this method can be improved by using multiple hash functions and counting the number of leading zeros at different places in the hash (23m44s).
• Techniques such as using buckets and taking the harmonic mean of the numbers can also improve the accuracy of the estimate (24m17s).
• This method is not extremely accurate but can provide a quick estimate of how well a post is doing, and the error band decreases as more buckets are added (24m52s).

Estimating the Number of People at a Conference

• To implement this method, a unique identifier for each person and one or more balanced hash functions are needed (25m15s).
• Bloom filters can also be used to check whether an element is in a dataset using multiple hash functions (25m35s).
• Hash functions can be used to estimate the number of people at a conference by remembering the alphabetically lowest name and looking up the probability of someone having that name or a lower one in a dataset of names (25m45s).
• The probability of someone having a name lower than "Keith" is around 50%, while the probability of someone having a name lower than "Divian" is around 25% (27m40s).
• A dataset of baby names from 1996 to 2021 can be used to estimate the number of people at a conference, with the name "Bubblecar" having a 12.5% chance of being the lowest name (27m59s).
• Remembering the alphabetically lowest name for each letter and taking the harmonic mean can improve the estimate of the number of people at a conference (28m31s).
• The stable matching algorithm is a way of making pairs of people using preferences, where both people want to go for a different preference (26m47s).
• The algorithm for estimating the number of people at a conference can be used in other situations, such as estimating the cardinality of a party (28m59s).

Stable Matching Algorithm and Cardinality Estimation

• The stable matching algorithm is a way of making pairs of people using preferences, where both people want to go for a different preference (26m47s).
• The algorithm for estimating the number of people at a conference can be used in other situations, such as estimating the cardinality of a party (28m59s).
• Using a turnstile at the door or having people dip their finger in paint can provide ground truth for estimating the number of people at a party (29m10s).

Additional Notes on the House of Wisdom and Alaris's Contributions

• The House of Wisdom has produced many famous works, including Alaris' contributions to astronomy, such as cataloging stars (29m55s).
• Alaris may have also worked on using celestial bodies as clocks, but it is unclear if he specifically used Jupiter for this purpose (30m10s).
• Historically, people used various methods to keep track of time, including using Jupiter as a clock, which is becoming a more widely accepted fact (30m22s).

Measuring Eagle Eyesight

• The eyesight of an eagle is four to eight times better than that of a human, but the method of measuring this is not immediately clear (30m45s).
• Researchers measure an eagle's eyesight by teaching it to fly through a tunnel and land on a screen with a specific pattern, rewarding it with food when it chooses the correct screen (31m31s).
• The size of the pattern on the screen is varied, and the distance at which the eagle can correctly identify the pattern is used to determine its eyesight (32m10s).
• This method is different from human eye tests, which typically involve reading letters off an eye chart (32m23s).
• The process of conducting an eye test for eagles is not readily available on YouTube, and listeners are encouraged to share any videos they may know of (32m51s).
• The show notes will include a link to the webpage where the information on eagle eye tests was found (33m26s).

Conclusion and Call to Action

• A request is made to find a video, with the finder asked to share their discovery, particularly if it involves conducting an eye test on different animals (33m33s).
• The episode is concluded with appreciation for the listeners and an invitation to share the podcast with others (33m44s).
• Anthony is thanked for joining the episode, which was described as fun and educational (33m53s).