Algorithms Data Structures In Java #2 (+Interview Questions)

Tries Data Structures, Ternary Search Trees, Data Compression, Substring Search and Sorting Algorithms

What you'll learn
Grasp the fundamentals of algorithms and data structures
Develop your own algorithms that best fit to the personal need
Detect non-optimal code snippets
Understand data compression
Understand sorting algorithms
Understand tries and ternary search trees
Understand Strings and StringBuilders
Requirements
Core Java
Internet connection
Description
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. How to sort an array of integers, doubles, strings or custom objects? We can do it with bubble sort, insertion sort, mergesort or quicksort. You will learn a lot about the theory as well as the concrete implementation of these important algorithms. The last lectures are about data compression: run-length encoding, Huffman encoding and LZW compression.Thanks for joining the course, let's get started!

Overview

Section 1: Introduction

Lecture 1 Introduction

Section 2: Trie Data Structures (Prefix Trees)

Lecture 2 What are tries (prefix trees)?

Lecture 3 Prefix tree introduction - insertion and searching

Lecture 4 Prefix tree introduction - sorting

Lecture 5 Prefix tree introduction - autocomplete

Lecture 6 Prefix tree introduction - associative arrays

Lecture 7 Tries implementation I

Lecture 8 Tries implementation II

Lecture 9 Tries implementation III

Lecture 10 Tries implementation IV - associative arrays

Lecture 11 Tries implementation V - autocomplete

Lecture 12 Tries implementation VI - sorting

Lecture 13 Hashing based data structures and tries

Lecture 14 Applications of trie data structures

Section 3: Interview Questions - IP Routing with Tries

Lecture 15 Networking and the longest common prefix problem

Lecture 16 Longest common prefix implementation

Section 4: Ternary Search Trees (TSTs)

Lecture 17 What are ternary search trees?

Lecture 18 Ternary search tree visualization

Lecture 19 Ternary search tree implementation - insertion

Lecture 20 Ternary search tree implementation - search

Lecture 21 Ternary search trees implementation - traversal

Lecture 22 Recursion and stack memory visualization

Section 5: Interview Questions - Boggle Game

Lecture 23 What is boggle and how to solve it?

Lecture 24 Boggle game with ternary search tree implementation I

Lecture 25 Boggle game with ternary search tree implementation II

Lecture 26 Boggle game with ternary search tree implementation III

Section 6: Substring Search

Lecture 27 Brute-force search introduction

Lecture 28 Brute-force search implementation

Lecture 29 Rabin-Karp algorithm introduction

Lecture 30 Rabin-Karp algorithm implementation

Lecture 31 Knuth-Morris-Pratt algorithm introduction

Lecture 32 Constructing the partial match table

Lecture 33 Knuth-Morris-Pratt algorithm implementation

Lecture 34 Z algorithm introduction

Lecture 35 Z algorithm illustration

Lecture 36 Z algorithm implementation

Lecture 37 Substring search algorithms comparison

Lecture 38 Applications of substring search

Section 7: Strings

Lecture 39 Strings and the String Constant Pool (Intern Pool)

Lecture 40 String's immutability

Lecture 41 Strings and StringBuilders

Lecture 42 String reversion

Lecture 43 Suffixes

Lecture 44 Prefixes

Lecture 45 Longest common prefix

Lecture 46 Longest repeated substring problem

Lecture 47 Why are suffix tries and suffix arrays useful?

Section 8: Basic Sorting Algorithms

Lecture 48 Sorting introduction

Lecture 49 What is stability in sorting?

Lecture 50 Adaptive sorting algorithms

Lecture 51 Bogo sort introduction

Lecture 52 Bogo sort implementation

Lecture 53 Bubble sort introduction

Lecture 54 Bubble sort implementation

Lecture 55 Selection sort introduction

Lecture 56 Selection sort implementation

Lecture 57 Insertion sort introduction

Lecture 58 Insertion sort implementation

Lecture 59 Shell sort introduction

Lecture 60 Shell sort implementation

Lecture 61 Quicksort introduction

Lecture 62 Quicksort introduction - example

Lecture 63 Quicksort implementation

Lecture 64 Hoare's partitioning and Lomuto's partitioning

Lecture 65 What is the worst-case scenario for quicksort?

Lecture 66 Merge sort introduction

Lecture 67 Merge sort implementation

Lecture 68 Merge sort and stack memory visualization

Lecture 69 Hybrid algorithms introduction

Lecture 70 Non-comparison based algorithms

Lecture 71 Counting sort introduction

Lecture 72 Counting sort implementation

Lecture 73 Radix sort introduction

Lecture 74 Radix sort implementation

Section 9: Interview Questions - Sorting

Lecture 75 Interview question #1 - implementing TimSort algorithm

Lecture 76 Interview question #1 - solution

Lecture 77 Interview question #2 - implement quicksort with iteration

Lecture 78 Interview question #2 - solution

Section 10: Data Compression

Lecture 79 What is data compression?

Lecture 80 What is run-length encoding?

Lecture 81 Run-length encoding implementation

Lecture 82 Huffman encoding introduction

Lecture 83 Huffman decoding introduction

Lecture 84 Huffman encoding implementation I - helper classes

Lecture 85 Huffman encoding implementation II - encoding

Lecture 86 Huffman encoding implementation III - testing

Lecture 87 LZW compression introduction - compression

Lecture 88 LZW compression introduction - decompression

Lecture 89 LZW implementation

Section 11: Next Steps

Lecture 90 Next steps

Section 12: ### APPENDIX - COMPLEXITY THEORY CRASH COURSE ###

Lecture 91 How to measure the running times of algorithms?

Lecture 92 Complexity theory illustration

Lecture 93 Complexity notations - big (O) ordo

Lecture 94 Complexity notations - big Ω (omega)

Lecture 95 Complexity notations - big (θ) theta

Lecture 96 Algorithm running times

Lecture 97 Complexity classes

Lecture 98 Analysis of algorithms - loops

Lecture 99 Case study - O(1)

Lecture 100 Case study - O(logN)

Lecture 101 Case study - O(N)

Lecture 102 Case study - O(N*N)

Section 13: Algorhyme FREE Algorithms Visualizer App

Lecture 103 Algorithms Visualization App

Lecture 104 Algorhyme - Algorithms and Data Structures

Section 14: Course Materials (DOWNLOADS)

Lecture 105 Course materials

This course is meant for university students with quantitative background (mathematics, computer science) but anyone with core java knowledge can get a good grasp of the lectures