algorithm

A graph-searching algorithm can discover much about the structure of a graph. The graph algorithm is essential in social network searching, artificial intelligence, etc. This chapter mainly discusses about the representation of graphs, BFS and DFS.

Representation of Graphs

We have two kinds of graph: directed and undirected graphs. In either way, we can represent the graph in adjacency-list representation or adjacency-matrix representation.

In amortized analysis, we can show that the average cost of an operation. An amortized analysis guarantees the average performance of each operation in the worst case.

Greedy Algorithm always makes the choice that looks best at the moment, which can solve many optimal problems effectively. However, local optimum does not necessarily result in the global optimum, and we need to take care of it.

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.