Algorithms Data Structures in Java #2 (+INTERVIEW QUESTIONS)

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 12 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 - Trieswhat are prefix trees (tries)basics operations: insertion, sorting and autocompletelongest common prefix problemprefix trees applications in networking (IP routing)Section 2 - Ternary Search Treeswhat is the problem with tries. what are ternary search treesbasic operations: insertion and retrievalapplications of tries (IP routing and Boggle Game)Section 3 - Substring Search Algorithmssubstring search algorithmsbrute-force substring searchZ substring search algorithmRabin-Karp algorithm and hashingKnuth-Morris-Pratt (KMP) substring search algorithmSection 4 - Stringsstrings in Java programmingwhat is the String Constant Pool.

prefixes and suffixeslongest common prefix problemlongest repeated substring problemsuffix tries and suffix arraysSection 5 - Sorting Algorithmsbasic sorting algorithmsbubble sort and selection sortinsertion sort and shell sortquicksort and merge sortcomparison based and non-comparison based approachesstring sorting algorithmsbucket sort and radix sortSection 6 - Data Compression Algorithmswhat is data compressionrun length encodingHuffman-encodingLZW compression and decompressionSection 7 - Algorithms Analysishow to measure the running time of algorithmsrunning time analysis with big O (ordo), big Ω (omega) and big θ (theta) notationscomplexity classespolynomial (P) and non-deterministic polynomial (NP) algorithmsO(1), O(logN), O(N) and several other running time complexitiesFirst, 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.

Substring search is another important field of computer science. You will learn about Z algorithm and we will discuss brute-force approach as well as Rabin-Karp method. The next chapter is about sorting.