Datastructures and Algorithms

This section demonstrates a strong understanding of datastructures and algorithm analysis. First, I showcase my Conway's Game of Life demo in OpenGL, discussing emergent properties. Then, I explore various algorithms and datastructures, leading up to big-O notation and "P=NP".

Conway's Game of Life is a cellular automata where a cell survives only if exactly 2 or 3 adjacent cells are alive. Though chaotic, different initial conditions can produce fascinating patterns.

I also wrote a paper exploring the idea of combining emergent patterns. The main takeaway is my underlying understanding of Turing machines.

I wanted to discuss at least one datastructure, so I've elected to mention the red-black tree, a self-balancing binary search tree.

This next algorithm discusses a solid understanding of recursion and inductive proofs.

Given a 2^n by 2^n grid, you can select any square to remove, and tessellate L-shaped trimino blocks around it recursively to fill the grid.

This exercize has been left for the students to solve.

You can view a more rigorous proof here!

Next, I showcase my "Minimal Bump Lexicographic Linear Extension of Partially Ordered Sets" project to demonstrate advanced C++ vector datastructures. This project takes a partially ordered set of elements and arranges them in order while making the fewest changes possible.

We now explore advanced algorithm analysis and dynamic programming, focusing on the chain matrix association problem.

Matrix multiplication order impacts computational complexity. My implementation runs in O(n³), meaning complexity grows cubically as the number of matrices increases.

Dekai's notes provide further insight.

Need a video explanation? Watch this!

By modeling matrices as edges in a convex polygon, chain matrix association reduces to polygon dissection, which runs in O(n log n).

This paper by T.C. Hu and M.T. Shing reveals a faster O(n log n) solution.

This kind of algorithmic comparison helps refine our understanding of "P=NP" by determining different runtime efficiency classes of algorithms and whether or not they are computible by Turing machines.

Return to the Portfolio landing page.