eqlz/mit-intro-to-algorithms

JavaScript implementation of algorithms in classic Introduction to Algorithms by CLRS

This repo is my attempt to implement algorithms in Introduction to Algorithms by CLRS while I'm following MIT's Introduction to Algorithms course via their open course ware.

The purpose of writing notes, is to makes notes unnecessary. In the process of orginazing notes, I have understood the material.

Notes

Chapter 2.2 Analyzing algorithms

What is analyzing an algorithm?

Analyzing an algorithm is to predict the resources that the algorithm requires.

• most often, it's computational time we want to measure

Analysis of insertion sort

It's traditional to describle the running time of a program as a function of the size of its input.

The running time of an algorithm on a particular input is the number of primitive operations or "steps" executed.

How to derive big O notation for insertsion sort?

1. For now, we assume that to execute each line of our pseudocode (refers to the pseudocode in textbook, JS implementation here is a better reference), a constant amount of time is required.

2. Assume that each execution of the i th line takes time c_i, where c_i is a constant.

3. Calculate how many times the for loop and while loop will run.

4. The running time of the alogrithm is the sum of running time for each statement executed. A statement takes c_i steps to execute and execute n times will contribute c_in to the total running time.

   • the goal of this step is to derive a function of n to express running time.
   • this is the most importat step to find big O. Steps before this one is just a preparation for me to get the f(n). Everthing after this step relies on f(n) to do analysis.

5. Figure out the worst-case scenario - to sort an array in reverse sorted order.

6. Calculate the running time for worst-case scenario: a quadratic function of n.

7. It's rate of growth or order of growth, of the running time that really interests us. We drop the coefficient of leading term, and drop the non-leading terms of the formula. For large input n, these are relatively insignificant. Thus, Θ(n²).

Chapter 2.3 Designing algorithms

What is divide-and-conquer?

Break the problem into several smaller subproblems that are similar to original problems, solve the problem recursively, then combine these solutions into a solution to the original problem.

Example of divide-and-conquer: merge sort

My implementation follows the pseudocode in the textbook. console.log() has been put into places that helps visually understand how the algorithm works.

Insertion sort

The gist if insertion sort: While going through each item in the array, starting from the second item, compare current item's value to the previous item's value.

If previous item has larger value than current item, swap values. If not, do nothing.

Binary Search Tree

BST deletion

For the case where the node to be deleted has both left and right child, we need to find a replacement node first.

This replacement node has these attributes:

• in the right sub-tree of the node to be deleted
• is the smallest node in the right sub-tree of the node to be deleted

Why does the replacement node need to have these attributes?

In order to maintain the BST structure:

• the replacement node has to be bigger or equal to any node in left sub-tree of node to be deleted,
• and smaller or equal to any node in right sub-tree of the node to be deleted.

Any node in the right sub-tree of NTBD(node to be deleted) is bigger or equal to any node in left sub-tree of NTBD. Now, we just need to find the smallest node in right sub-tree in NTBD.

BST successor

What is a succssor of a given node? It the node has 1) smallest key, 2) greater than the given node.