XYZ CODE

If you want to use algorithm to solve problems instead of doing research on algorithm itself, java probably should be your chosen language. Java collection framework has many data structures and algorithms encapsulated in classes, right there ready for use. Besides, third party java packages such as JGraphT further harnesses the power of algorithm, then handles the control to you in a set of easy to use interfaces. Being a mechanics is cool, being a driver is wise. Be both, my friend.

Understand the idea

Algorithms in a nut shell, boils down to sort and search. You drive down the entropy, then find the information hidden in the mess.

Java Examples

Union and Find

UnionFindDemo.java improved version

QuickUnion.java

memory usage of java objects

ConvexHull.java

CollisionSystem.java

IntersectionCounter.java

SparseMatrix.java

SparceMatrix.java brutal force version

Hell.java

DFS vs BFS for graph and digraph

BFSWebCrawler.java

Graph.java

Strongly Connected Components in simulated intranet

HelloJGraphT.java

Fitness check

Full understanding of the CS fundamentals such as algorithms, design patterns, data structures, recursions, binary search trees etc. are the keys to solve many different kinds of problems.

We have studied lots of classic data-structures and algorithms so far. Let's pick the most handy and effective ones to practice into instinct.

Algorithms:

Data Structures:

Typical Problems

Linked List

linked list data structure captured the cause-effect relationship between things, it is the building block of many data structures.

reverse linked list

detect loop in linked list

implement Stack

implement Queue

implement HashMap

Binary Search Tree

Besides cause-effect relationship, binary Search Tree introduced branches to capture decision. A parent node points to 2 children nodes. The left child is smaller and the right child is larger. Moving right-ward, the elements are larger, moving leftward the elements are smaller. However, the largest element (right-most) in the left branch is smaller than the smallest element (left-most) in the right branch. Recursive is the state of mind for binary search tree.

traversal a binary search tree

We have studied the traversal sequence of in-order, pre-order and post-order binary tree traversal. In philosophy level. They represent 3 kinds of knowledge for the collection of chaotic nodes.

Seeking for path information at leaf with pre-order traversal -- since the pre-order traversal visits root first, at any node, the traveller has the knowledge of all the nodes from root to the current node, the path information is completed at leaf node.
Seeking for global information at root with post-order traversal -- since the post-order traversal visits children first, at any node, the traveller has the knowledge of the entire sub-tree of the current node, the global information is completed at root node.
Seeking for trend information at root with in-order traversal -- since the in-order traversal visits left branch first, it will travel to right branch next, at any node, the traveller has the knowledge of the entire left branch and current branch, changes can be easily detected or applied at current node.

find paths in a binary search tree with nodes sum equal to K

find the maximum sum of all sub-trees in a binary search tree

find the first node with value above K in a binary search tree

Array and String

Indexed array allows random access. The reason for A to B is because you code it that way. Using index as a pointer to the data location, programmer got more flexibility. Details such as iterative, recursive, back-tracing and dynamic programming go a long way in this data structure. String is a char array. String class provided convenient methods such as substring(), charAt(), startWith(), endWith(), contains(), equal() etc.

Some small details could save you tons of time because they are used frequently:

endIndex = startIndex + length - 1 e.g. "a" 0 = ( 0 + 1 - 1)
length = endIndex - startIndex + 1 e.g. "a" length 1 = 0 - 0 + 1
substring(startIndex, endIndex+1) e.g. "a" substring(0, 1) index 1 is exclusive
"a".toCharArray
StrinbBuffer's reverse function
Character.isDigit
startIndex = middleIndex - (length - 1)/2 e.g. "a" 0 = 0 - (1 - 1)/2, "aa" 0 = 0 - (2 - 1)/2
endIndex = middleIndex + length/2 e.g. "a" 0 = 0 + 1/2, "aa" 1 = 0 + 2/2

Recursive should not be a stranger to us by now. Merge sort, quick sort, 3-way quick sort, 3-way string quick sort for example, use recursive calls to sort an array. Binary search, for another example, quickly find the rank of an item in an array. Many problems can be solved by applying these algorithms or slightly changing the code in the inner loop.

Besides the above array sorting problem, another typical problems is to find the extreme value among the possible subarray combinations.

Brutal force enumeration of size N arrays generally has big O(N^k), where k is the layer of for loops. Two special enumerations need to emphasis are:

Finding the extreme value can be facilitated by dynamic programming, where we store the middle value, using them to compute the value for later iterations.

There is a cluster of extreme value problems where the global minimum is achieved if local minimum is achieved at each step. Such kind of problem is plenty in natural science, for example, the lowest free energy is achieved for a surface, if and only if each deposited molecular is able to find the lowest energy site to form bond. In CS we use greedy algorithm to solve such kind of problem.

Optimum task distribution for shortest finish time

Even brutal force is not always easy to materialize with code, the most important part of the problem solving is to build the model creatively, which is case by case and won't fit into rigid categorizes.