Birkhoff Tech Blog

We typically apply dynamic programming to optimization problems.

When developing a DP algorithm, we could follow a sequence of three steps:

1. identify if it is a DP problem
2. determine the recursive relationship
3. Adding memorization or tabulation

What is a binary search tree?

Binary-search-tree property:

Let \(x\) be a node in a binary search tree. If \(y\) is a node in the left subtree of \(x\), then \(y.key \le x.key\). If \(y\) is a node in the right subtree of \(x\), then \(y.key\geqslant x.key\).

Two steps in Hash Table

1. Compute the hash function
2. Fix the collision resolution (algorithms and data to handle two keys that hash to the same index)

Minimum and Maximum

Given an array \(\[1...n\]\), find the maximum and minimum number in this array.

Naive Approach

It should take \[2(n-1)\] comparison to find the maximum and minimum number in the array by iterating the array twice. It seems to exist a "smarter" way to find both min and max in one pass.

Although all comparision sorting algorithm requires at least \(\Omega(n\lg n)\) comparisons, in certain conditions, we are able to sort an array in \(O(n)\) complexity.

Quick sort is a widely applied sorting algorithm in the industry. It is a simple but very powerful algorithm that we should definetely understand. An interesting graph shown below can illustrate the process of this algorithm.

This blog is my first post of the course note of the classical textbook, Introduction to Algorithm. Many graphs and formulas might be directed retrieved from this book. Some other blogs might utilize the book Algorithms, 4th and other open source online with proper citation.

This series of blog is only for the learning purpose. Please inform me if violating any copyright issue.