Algorithms and Data Structures in Java – Part II

This course is about data structures and algorithms. We are going to implement the problems in Java, but I try to do it as generic as possible: so the core of the algorithms can be used in C++ or Python. The course takes approximately 7 hours to complete. I highly recommend typing out these data structures several times on your own in order to get a good grasp of it.

Section 1:

what are prefix trees (tries)

basics operations: insertion, sorting and autocomplete

longest common prefix problem

prefix trees applications in networking

Section 2:

what are ternary search trees

basic operations: insertion and retrieval

Section 3:

substring search algorithms

brute–force substring search

Boyer–Moore substring search

Rabin–Karp algorithm

Section 4:

strings in programming

prefixes and suffixes

longest common prefix and longest repeated substring problem

Section 5:

basic sorting algorithms

bubble sort and selection sort

insertion sort and shell sort

quicksort and merge sort

Section 6:

what is data compression

run length encoding

Huffman–encoding

LZW compression and decompression

First, we are going to discuss prefix trees: modern search engines for example use these data structures quite often. When you make a google search there is an autocomplete feature because of the underlying trie data structure. It is also good for sorting: hashtables do not support sort operation but on the other hand, tries do support.