Community Projects, Computer Science, Group, Milestones, Murderous Maths, Notes on everyday life

Simon introducing himself for the World Science Scholars program

This is Simon’s introductory video for the World Science Scholars program (initiative of The World Science Festival). In May this year, Simon has been chosen as one of the 30 young students worldwide, joining the 2019 cohort for exceptional talents in mathematics. Most of the other students are 14 to 17 years old, age was not a factor in the selection process. To help the students and their future mentors to get to know one another, every World Science Scholar was asked to record an introductory video, no longer than 3 minutes, answering a few questions such as what is the biggest misconception about math, what your favourite branches of math and science are and who among the living mathematicians you’d like to meet.

Throughout the program, the students are given access to over a dozen unique interdisciplinary online courses and have the option to complete an applied math project, alone or as a team, consulting real experts in the field of their project. Simon has already started the first course module, on Special Relativity by Professor Brian Greene. The course has been specifically recorded for the World Science Scholars and reflects the program’s ethos: it’s self-paced, no grades, it relies on beautiful animations and visualizations, it’s full of subtle humour, is dynamic, thought-provoking and quite advanced (exactly in The Goldilocks Zone for Simon, as far as I could judge), yet broken up into easy-to-digest pieces. It’s difficult to predict how Simon’s path as a World Science Scholar will unfold (I’m afraid of making any predictions as he is extremely autodidact), but so far we have been very pleased with the nature of this program and it seems to match our non-coercive, self-directed learning style. I have especially liked one of the course’s main postulates: “Simultaneity is in the eye of the beholder”.

Simon watching Brian Greene’s Special Relativity course
Studying light clocks
Light clocks. Does the moving light clock tick slower?
Simon thinking about the question: Does the moving light clock tick slower?
Coding, Computer Science, JavaScript, Simon teaching, Simon's Own Code, Simon's sketch book

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

Link to the project:
Made my Beadsort step-by-step with a generator function! (Scroll down to see the “Next” button!) Code:
The video also contains a bonus tutorial about what a generator function is!
Computer Science, Logic, Milestones, Murderous Maths, Notes on everyday life, Set the beautiful mind free, Simon teaching, Simon's sketch book

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:

Part 6: Shellsort

The code of the sorting algorithms discussed in the previous videos (parts 1 – 5) is available here:

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.