Larry's Blog 🌊

Pumping Lemma

Posted: September 2, 2022 #Algorithms
Pumping lemma is a theorem that states that all regular languages have a special property: all strings in the language can be “pumped” if they are at least as long as a certain special value, called the pumping length. Pumping lemma is saying Regular Language must have 3 properties. We can use i...

Master Theorem

Posted: September 2, 2022 #Algorithms
For analyzing the time complexity of a recursion algorithm, we can use a recursion tree to help. By rough calculation, we can divide the computing work into two parts, those at the leaves (bottom level) and those at branches including the root (uppper levels). Depending on the asymptotical positi...

Stable Marriage Problem

Posted: September 1, 2022 #Algorithms
Table of Contents: Introduction Algorithm explained Pseudocode Code example The variables we need: helper functions Key function to execute the algorithm Final kick An test result Proof of the algorithm Time complexity In...

Recursion

Posted: September 1, 2022 #Algorithms
As mentioned in other posts before, recursion is just a coding technique, not fancy as it sounds at all. Let’s take a look at a recursion example: // find GCD (greatest common dividor) // using recursive coding method const gcdFind = function (a, b) { // roll back condition if (a === b) re...

Quicksort

Posted: September 1, 2022 #Algorithms
History According to wikipedia, quicksort is an in-place sorting algorithm. Developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. Algorithm explained Quicksort is a divide-and-conquer algorithm. It works by selectin...

Mergesort

Posted: September 1, 2022 #Algorithms
History According to wikipedia, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output. Merge sort is a ...

Heap Sort

Posted: August 31, 2022 #Algorithms
Table of Contents: Definition and categories of heaps index and height of a heap Max and min heaps Insert an element to a heap Algorithem in normal language Code example Time complexity of heap insertion Create a heap Time...

Binary Search

Posted: August 31, 2022 #Algorithms
**Comment:** I made the post date at Sept. 01, 2022 at first. It cost me the whole morning trying to make this post show up on the blog but failed. It turns out that you cannot pre-date post, otherwise it cannot be rendered by github. An 3-hour expensive lesson!~ If you are given an array of un...

Insertion Sort

Posted: August 30, 2022 #Algorithms
Insertion sort is among the first models we learn about algorithms. It sorts an array of numbers from left to right, make comparison with all sorted numbers to the left, and act on one move when it finds its place in the left sub-array: inserting into the right place. Insertion Sort Illustratio...

Bubble Sort

Posted: August 30, 2022 #Algorithms
Bubble sort is always discussed along side insertion sort. Contrary to sorting from left to right by insertion sort, Bubble sort works from right (last) to left (first). Furthermore, Bubble sort uses swap rather than shift to order numbers. It’s working as a compare and swap model. Bubble Sort ...