This is Simon explaining Diffe-Hellman key exchange (also called DiffeHellman protocol). He first explained the algorithm mixing watercolours (a color representing a key/ number) and then mathematically. The algorithm allows two parties (marked “you” and “your friend” in Simon’s diagram) with no prior knowledge of each other to establish a shared secret key over an insecure channel (a public area or an “eavesdropper”). This key can then be used to encrypt subsequent communications using a symmetric keycipher. Simon calls it “a neat algorithm”). Later the same night, he also gave me a lecture on a similar but more complicated algorithm called the RSA. Simon first learned about this on Computerphile and then also saw a video about the topic on MajorPrep. And here is another MajorPrep video on modular arithmetic.

# Tag Archives: algorithms

# Back to the sorting algorithms: Beadsort (and a short lecture about the generator function)

# Why mathematics may become computer science

Walking home from the swimming pool (where he and Neva had been jumping into the water exactly 24 times, calling out all the permutations of 1,2,3 and 4), Simon suddenly stopped to tell me that some day, mathematics may become engulfed by computer science. Apparently, this was what he was thinking about the whole time he kept silent on the way. Once we got home I sat down to listen to the elaborate proof he had coined for his hypothesis. Here is comes, in his own words:

Someday mathematics may become computer science because most of mathematics uses simple equations and stuff like that, but computer science uses algorithms instead. And of course, algorithms are more powerful than equations. Let me just give you an example.

There’s this set of numbers called algebraic numbers, and there’s this set of numbers called computable numbers. The algebraic numbers are everything you can make with simple equations (finite polynomials), so not like trig numbers, which are actually infinite polynomials, just simple finite equations with arithmetic and power. Computable numbers, however, are a set of numbers that you can actually make with a finite algorithm. It may not represent a finite equation, but the rules for the equation have to be finite. So the algorithm that generates that equation has to be finite. It’s pretty easy to see that every algebraic number is by definition computable. Because the algorithm would just basically be the equation itself.

Is every computable number algebraic? Well, we can easily disprove that. It took very long to prove that Pi is not algebraic, that it is transcendental, as it’s called. But Pi is computable, of course, because, well, that’s how we know what Pi is, to 26 trillion decimal places. So there you go. That’s a number that is computable but not algebraic. So the Euler diagram now looks like this:

Now we look back at the beginning and we see that algebraic numbers have to do with equations and computable numbers have to do with algorithms. And because the set of all algebraic numbers is in the set of all computable numbers as we’ve just proved, the set of computable numbers will have more numbers than algebraic numbers. We have given just one example of how algorithms are more powerful than equations.

What about the mathematics that deals with numbers that are incomputable? – I asked.

Well, that’s set theory, a different branch of mathematics. I meant applied mathematics, the mathematics that has application.

# Simon’s new “giant project”: Sorting Visualizations

Simon writes: I’ve built a giant project; a website / community project / platform for making algorithms! I’ve built in this video Bubble Sort, Selection Sort, Insertion Sort, Mergesort, Quicksort, Heapsort, Shell Sort and Radix Sort. So I’m done with the sorting part of the project. In the next video I’ll show you the making of the Pathfinding part of the project, and then, I’m going to put it on GitHub, and pass it on to the community, to put more algorithms on there, and even new types of algorithms!

Play with Simon’s visualizations on Repl.it at: https://repl.it/@simontiger/SortingImproved

Simon has already recorded a series of video tutorials about sorting algorithms earlier this spring. In the videos, he codes on his RaspberryPi, but here are the links to the Python code available on his GitHub page: Parts 1 – 5; Parts 6 – 7.

# Pathfinding algorithms: Dijkstra’s and Breadth-first search

The photos below show Simon playing with Breadth-first search and Dijkstra’s algorithms to find the most efficient path from S to E on a set of graphs. The two more complex graphs are weighed and undirected. To make it more fun, I suggest we pretend we travel from, say, Stockholm to Eindhoven and name all the intermediate stops as well, depending on their first letters. And the weights become ticket prices. Just to make it clear, it was I who needed to add this fun bit with the pretend play, Simon was perfectly happy with the abstract graphs (although he did enjoy my company doing this and my cranking up a joke every now and then regarding taking a detour to Eindhoven via South Africa).

# More Sorting Algorithms!

An update to Simon’s new project: a series of video tutorials on sorting algorithms! See the full playlist here.

Finally, parts 6 and 7 of Simon’s exciting series of video tutorials about sorting algorithms are done! In the videos, Simon codes on his RaspberryPi, but here is the link to the Python code (parts 6 – 7) available on his GitHub page:

https://gist.github.com/simon-tiger/be3864b36f6d89fecd06f150063a6321

The code of the sorting algorithms discussed in the previous videos (parts 1 – 5) is available here: https://gist.github.com/simon-tiger/5be70247a066f69c2578be5bb8e41e59

Simon wrote the Shellsort code himself. He tried to run his own code for Heapsort as well, but didn’t get the list fully sorted, so in the end he implemented the heapsort code that he learned from Brilliant.

“Then, with VERY much relief, I MASSIVELY condensed the code (to just 3 lines!), using Zax Rosenberg’s blog“, Simon adds.

# Bubble Sort in Wolfram Mathematica

# Unconvinced on a Brilliant puzzle

Simon writes (this is a copy of the question he has published in Coding Train’s Slack chat):

Hi! I was unconvinced on a Brilliant puzzle:

The problem (at https://brilliant.org/practice/treaps/?p=4):

Me working on it…

The solution on Brilliant was different:

However, only 1 page earlier, the explanation said:

…Contradiction?

# Simon creates a playlist with Sorting Algorithms tutorials in Python

Simon has started a huge new project: a series of video tutorials about sorting algorithms. In the videos, he codes on his RaspberryPi, but here is the link to the Python code available on his GitHub page (that he continuously updates): https://gist.github.com/simon-tiger/5be70247a066f69c2578be5bb8e41e59

Today, Simon has recorded the fifth part of the series, in which he explains and applies the Quicksort algorithm. [The coding part goes very smoothly and much *quicker* (hehe) than in the previous sorting videos we have made so far. Simon also came up with his own code, he didn’t look the code up].

And here come the previous parts of Simon’s sorting algorithms series, also available via this link to a playlist on his YouTube channel (there will be more videos coming):

Simon is also fascinated by more exotic sorting algorithms, such as a sorting network:

Simon used the following resources: Daniel Shiffman’s tutorial on Quicksort, Timo Bingmann’s sort algorithms visualization, Must Know Sorting Algorithms in Python, a medium blog on sorting algorithms, Brilliant.org’s computer science courses, Wikipedia.

# Fun with Brilliant’s Computer Courses

“Mom, how long would it take a supercomputer running at 10^15 additions per second to calculate the 1000th Fibonacci number?”

Simon has learned this problem from the new course he is following on Brilliant.org: Computer Science Algorithms. Simon worked it out on an A3 sketch book sheet and got the answer correct: it would take longer than the age of the Universe!

Simon has already finished the Computer Science Fundamentals course! It has been Simon’s idea to take up the courses on Brilliant.org again and he has been working independently, driven entirely by his intrinsic motivation.

The course has also inspired Simon to work on a very large scale project: record a series of tutorials where he explains all the best known sorting algorithms and comes up with the Python code for them on his RaspberryPi!