Murderous Maths, Milestones, Notes on everyday life, Simon teaching, Simon's sketch book, Logic, Set the beautiful mind free, Computer Science

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:

Simon drew this illustration later the same evening, when he presented his proof in Russian to his grandma via FaceTime

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.

Coding, Computer Science, Crafty, Geography, Murderous Maths, Notes on everyday life, Simon's sketch book

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).

this was an example of how an algorithm can send you the wrong way if it has data of the “right” way being weighted more (due to traffic jams, for example)
Coding, Community Projects, Computer Science, Contributing, Geometry Joys, Group, Milestones, Murderous Maths, Notes on everyday life

More examples of Simon’s chat contributions on math and coding

Simon is always extremely active in the discussions about the current projects made by/ lectures given by NYU’s Asdociate Professor Daniel Shiffman during his live sessions on the Coding Train channel. He also enjoys “initiating discussions” among the channel’s patrons (grown-up programmers) and Daniel. “Mom, the discussion I initiated is still going on!” I couldn’t possibly post all the coding and math comments/ suggestions that Simon makes in the chats on YouTube, Slack and GitHub (and I don’t believe I should either), but every now and then, I like collecting samples of Simon’s contributing to the discussion:

Simon contributing to a discussion prior to a live session on ray tracing
Simon contributing to Daniel Shiffman’s tutorial on the computational geometry “minimum spanning tree” problem

The small font above says:

Correction: The MST problem does not allow any loops (like A->B, B->C, C->D, D->A again.) So the solution at 2:30 is wrong! In fact, _no wonder it does that_, because Prim’s Algorithm will never find a loop. Here’s why:

Let’s suppose that it could find a loop (let’s say, a loop of 4, so A->B, B->C, C->D, D->A again, but this argument would work the same each way.) Ok, so it will start from A, and mark it as reached. It will check A against B, C and D, find B, and mark B as reached. Then, it will check A against C and D, and B against C and D. and it will find that it should connect B and C, and mark C as reached. Then, it will check A, B and C all against D, and find that it should connect C and D, and mark D as reached. But now, we reach a problem. It will not connect D and A, because both are already reached!

Why was it designed like that? Because that’s what the problem says! It’s a Minimum Spanning _Tree_, so it can’t have any loops.

So there you go, that’s why Prim’s algorithm will not find a loop.

Coding, Computer Science, Contributing, Group, Milestones

Simon’s Computer Science Algorithm Suggestions

Simon’s suggestion for the Coding Train on GitHub:

Because I like computer science these days, here are some computer science algorithm suggestions:

  • Data Structures
    • Array
    • Linked List
    • Hash Table
    • Stack
    • Queue
    • Priority Queue (Binary heap)
    • Suffix Array
    • Graph Theory
      • Graph (general)
      • Tree
      • Binary Tree
        • Full vs. Complete
        • BST
        • Binary Heap
        • AVL Tree
        • Red-Black Tree
        • Segment Tree
        • DFA
      • Biparite
      • UFDS
      • Fenwick Tree
      • Min Spanning Tree
      • Suffix Tree
    • Computational Geometry
      • Polygon, etc.
  • Algorithms
    • Shuffling
      • Fisher-Yates Algorithm
    • Sorting
      • Bubble Sort
      • Selection Sort
      • Insertion Sort
      • Merge Sort
      • Quicksort
      • Counting Sort
      • Radix Sort
      • More?
      • Even More? (Scroll down to see a GIANT table)
    • Traversal / Pathfinding / SSSP
      • Basic
        • Pre-order
        • In-order
        • Post-order
        • Depth-first
        • Breadth-first
        • More?
      • Shortest Pathfinding
        • Dijkstra’s Shortest Path
        • A*
      • More?
      • Even More?
    • Substring Finding
    • Min Spanning Tree
      • Brute-force
      • Kruskal’s Algorithm
      • Prim’s Algorithm(s)
    • Max-flow
    • Graph Matching
    • Cycle Finding
    • Convex Hull
      • Gift Wrapping
      • Graham Scan
      • Quickhull
      • “The Ultimate Planar Convex Hull Algorithm”
      • More?
    • Min Vertex Cover
      • Brute-force
      • MVC
      • Approximation
    • Traveling Salesman
      • Brute-force
      • Dynamic Programming
      • Approximation
    • Steiner Tree

If you’re brave, Do you want more even after all of this?
One last note: you’re not going to do all of them (probably!).

Coding, Computer Science, Crafty, Geography, Geometry Joys, Murderous Maths, Simon's sketch book

Dijkstra’s pathfinding algorithm

“I have first built a maze, then I turned it into a graph and applied Dijkstra’s pathfinding algorithm!”

a maze to which Dijkstra’s pathfinding algorithm is applied

Simon learned this from the Computerphile channel. He later also attempted to solve the same maze using another pathfinding algorithm (A-Star).

Coding, Computer Science, Milestones, Murderous Maths, Python, RaspberryPi, Simon teaching, Simon's Own Code, Simon's sketch book

More Sorting Algorithms!

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

Part 7: Heapsort

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

Part 6: Shellsort

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.

Coding, Coding Everywhere, Computer Science, Milestones, Murderous Maths, Python, RaspberryPi, Simon's Own Code, Simon's sketch book

Simon creates a playlist with Sorting Algorithms tutorials in Python

Simon’s chart of sorting algorithms ranked by efficiency

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].

the quicksort video

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):

the bubble sort video
the selection sort video
the insertion sort video (took Simon two days to make)
the merge sort video (was the most painful one)

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.


Coding, Computer Science, Good Reads, Logic, Milestones, Murderous Maths, Notes on everyday life, Python, Set the beautiful mind free

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 working the answer out again to show me the way he solved it

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!