a
a
algo-en
english
Search
K

# What's the Best Algo Book

Translator: natsunoyoru97
My previous articles are mainly about hardcore algorithms, but I'll no more talk about them today. I have highly recommended Algorithms, 4th Edition (alias algs4) before in my previous articles but without explanation in details, so I'll introduce it to you.
I prefer to combine with applications rather than to throw out a pile of bibliography. I'll show you something fun and useful so you could learn something no matter you will read the book or not.
Algorithms, the 4th Edition IS FRIENDLY WITH NEWBIES. There are so many readers asking questions like can they read algs4 with only C programming basics, and what is the best programming language to learn algorithms.
Algorithms are patterns of thinking and it is nothing about what programming language you use. My codes in the articles are not in only one programming language, and it is more about by what programming language is easier for you to understand. Plus, you can get a digital copy (say, a PDF file) and then you will know it is suitable for you or not.
algs4 is thick but the first chapter is about Java basics, practices and mathematical proofs are also take up lots of pages. All the things left are basic knowledge and answers for things hard to understand, which are of great value. If you write up the codes of basic knowledge, you will be good in algorithms.
I think this book is highly rated because of its in-detail explanation and combination between algorithms and applications in life. Not only do you know how to construct algorithms, but also you know how you can apply them to solve other problems in real life. Then I'll introduce two simple applications of graph algorithms:

## 1. Applications of Bipartite Graph

The first example is bipartite Graph. In brief, the bipartite graph is a special kind of graph: you can paint all nodes with two colors, and the colors are different between ANY two nodes in one edge.
As we know what is a bipartite graph, what practical problems can it deal with? In algorithms, it is usual to check a graph is a bipartite graph or not. For example, here is a practice in LeetCode: If we regard every person as a node and use the edges represent if two persons hate with each other, we can make a graph. Thus, according to the definition of the bipartite graph mentioned before, if the graph is bipartite, these persons can be split into two groups.
This is one application of algorithms in determining a bipartite graph, and bipartite graph can do more of this. bipartite graph, as a kind of data structure, also has its special application.
For example, we need a kind of data structure to store the relations between movies and actors: a movie has many actors, and an actor is possible to star in many movies. What kind of data structure do you apply to store the relation?
As what we do is to store the mapping, the most simple way is to apply a hash table, so we could use the `HashMap<String, List<String>>` to store the mapping from movies to the actor list. Given the name of a movie, we will get all the actors starred in this movie quickly.
But what do we do if we would like to get all the movies an actor stars in given his or her name? We need to apply inverted index, make some modification of the hash table, to build another hash table using the actors as the key and movie list as the value.
For this example, we can apply the bipartite graph instead of the hash table. Relation between movies and actors is like a bipartite graph: we regard movies and actors as nodes in the graph, relation of acting the role as edges, thus there is only connections between actors and movies, and there is no case that an actor node connects to another actor node or a movie node connects to another movie node.
By the definition of the bipartite graph, if we paint actor nodes and movie nodes, there must be a bipartite graph:
If the graph is constructed, there is no need to do an inverted index. One actor node only connects to a movie node, and a movie node only connects to an actor node.
algs4 also mentioned some other fun applications, such as degrees of separation in the social network (maybe you have heard about Six Degrees of Separation), it is a problem of applying BFS searching to find the shortest path, I just skip the code here.

## 2. Arbitrage with Bellman-Ford Algorithm

Given the exchange rate from a currency A to another currency B is 10, which means 1 unit of currency A can exchange 10 units of currency B. If we regard every currency as a node of the graph and the exchange rate between two currencies is weighted directed edge, the whole foreign exchange rate market is a complete weighted directed graph.
Once we abstract scenarios in real life to a graph, it is possible to solve some problems using algorithms. For example, such a situation may exist in the graph: