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

Basic Algorithms and Data Structures: AVL tree, Binary Search Trees, Arrays, B Trees, Linked Lists, Stacks and HashMaps

What you'll learn

grasp the fundamentals of algorithms and data structures

detect non-optimal code snippets

learn about arrays and linked lists

learn about stacks and queues

learn about binary search trees

learn about balanced binary search trees such as AVL trees or red-black trees

learn about priority queues and heaps

learn about B-trees and external memory

learn about hashing and hash tables

Requirements

Basic Java (loops and some OOP)

Description

This course is about data structures and algorithms. We are going to implement the problems in Java. The course takes approximately 14 hours to complete. It is highly recommended to type out these data structures several times on your own in order to get a good grasp of it.  Section 1:data structures and abstract data typesSection 2 - Arrayswhat are arrayswhat is random access and how to indexesSection 3 - Linked Listslinked lists and doubly linked listslinked list related interview questionsSection 2 - Stacks and Queues:what are stacks and queuesheap memory and stack memoryvisualizing stack memorySection 3 - Binary Search Trees (BSTs):what are tree data structures?how to achieve O(logN) logarithmic running time?binary search trees Section 4 - AVL Treeswhat is the problem with binary search trees?balanced search trees: AVL trees rotationsSection 5 - Red-Black Treeswhat are red-black trees?what is recovering operation?comparing AVL trees and red-black treesSection 6 - Splay Treessplay trees and cachesachieve O(1) running time for getting the recently visited itemSection 7 - Heaps and Priority Queueswhat are priority queues?what is heap data structure?how to do sorting in O(NlogN) with heaps?Section 8 - B-Treesexternal memory and the main memory (RAM)B-trees and their applications in memoryB* trees and B+ treesSection 9 - Hashing and HashMaps:what are hashing and hashtables (hashmaps)what are hash-functionshow to achieve O(1) running time complexitySection 10 - 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 11 - Substring Search Algorithmssubstring search algorithmsbrute-force substring searchZ substring search algorithmRabin-Karp algorithm and hashingKnuth-Morris-Pratt (KMP) substring search algorithmSection 12 (BONUS):what is LRU cacheLRU cache implementationSection 13 (BONUS):Fenwick trees (binary indexed trees)binary indexed tree implementation Section 14 - 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 complexitiesIn each chapter you will learn about the theoretical background of each algorithm or data structure, then we are going to write the code on a step by step basis in Eclipse, Java.Most of the advanced algorithms relies heavily on these topics so it is definitely worth understanding the basics. These principles can be used in several fields: in investment banking, artificial intelligence or electronic trading algorithms on the stock market.Thanks for joining the course, let's get started!

Overview

Section 1: Introduction

Lecture 1 Introduction

Lecture 2 Complexity theory basics

Section 2: Data Structures Overview

Lecture 3 Why do we need data structures?

Lecture 4 Data structures and abstract data types

Section 3: Installation and Environment Setup

Lecture 5 Installing Java and Eclipse on Windows

Lecture 6 Installing Java and Eclipse on Mac

Section 4: Arrays

Lecture 7 What are array data structures?

Lecture 8 Arrays introduction - operations

Lecture 9 Implementing arrays

Lecture 10 ArraysLists in Java

Section 5: Interview Questions (Arrays)

Lecture 11 Reversing an array in-place overview

Lecture 12 Reversing an array in-place solution

Lecture 13 Anagram problem overview

Lecture 14 Anagram problem solution

Lecture 15 Palindrome problem overview

Lecture 16 Palindrome problem solution

Lecture 17 Integer reversion problem overview

Lecture 18 Integer reversion problem solution

Lecture 19 Dutch national flag problem overview

Lecture 20 Dutch national flag problem theory

Lecture 21 Dutch national flag problem solution

Lecture 22 Trapping rain water problem overview

Lecture 23 Trapping rain water problem theory

Lecture 24 Trapping rain water problem solution

Section 6: Linked Lists

Lecture 25 What are linked lists?

Lecture 26 Linked list theory - operations

Lecture 27 Linked lists in Java !!!

Lecture 28 Linked list implementation I

Lecture 29 Linked list implementation II

Lecture 30 Linked list implementation III

Lecture 31 Linked list implementation IV

Lecture 32 Comparing linked lists and arrays

Lecture 33 Practical (real-world) applications of linked lists

Section 7: Doubly Linked Lists

Lecture 34 What are doubly linked lists?

Lecture 35 Doubly linked list implementation

Lecture 36 LinkedLists in Java

Lecture 37 Running time comparison: linked lists and arrays

Section 8: Interview Questions (Linked List)

Lecture 38 Finding the middle node in a linked list overview

Lecture 39 Finding the middle node in a linked list solution

Lecture 40 Reverse a linked list in-place overview

Lecture 41 Reverse a linked list in-place solution

Section 9: Stacks

Lecture 42 What are stacks?

Lecture 43 Stacks in memory management (stacks and heaps )

Lecture 44 Stack memory visualization

Lecture 45 Stack implementation with linked list

Lecture 46 Stack implementation with arrays

Lecture 47 Dijkstra's interpreter introduction

Lecture 48 Dijkstra's interpreter implementation

Lecture 49 Stacks in Java

Lecture 50 Practical (real-world) applications of stacks

Section 10: Queues

Lecture 51 What are queues?

Lecture 52 Queue implementation with linked list

Lecture 53 Queues in Java

Section 11: Interview Questions (Stacks and Queues)

Lecture 54 Max in a stack problem overview

Lecture 55 Max in a stack problem solution

Lecture 56 Stack with queue overview

Lecture 57 Stack with queue solution

Lecture 58 Stack with queue solution - recursion

Section 12: Binary Search Trees

Lecture 59 Binary search trees theory - basics

Lecture 60 Binary search trees theory - search, insert

Lecture 61 Binary search trees theory - delete

Lecture 62 Binary search trees theory - in-order traversal

Lecture 63 Binary search trees theory - running times

Lecture 64 Binary search trees implementation I - Node and Tree classes

Lecture 65 Binary search trees implementation II - insertion

Lecture 66 Binary search tree implementation III - max, min and traversal

Lecture 67 Stack memory visualization - finding max (min) items

Lecture 68 Stack memory visualization - tree traversal

Lecture 69 Binary search tree implementation IV - remove

Lecture 70 Binary search tree implementation V - testing

Lecture 71 Practical (real-world) applications of trees

Section 13: Interview Questions (Trees)

Lecture 72 Compare binary trees overview

Lecture 73 Compare binary trees solution

Lecture 74 Compare binary trees minor update

Lecture 75 k-th smallest element in a search tree overview

Lecture 76 k-th smallest element in a search tree solution

Lecture 77 Family age problem overview

Lecture 78 Family age problem solution

Section 14: Balanced Trees: AVL Trees

Lecture 79 Motivation behind balanced binary search trees

Lecture 80 What are AVL trees?

Lecture 81 AVL trees introduction - height

Lecture 82 AVL trees introduction - rotations

Lecture 83 AVL trees introduction - illustration

Lecture 84 AVL tree implementation I

Lecture 85 AVL tree implementation II

Lecture 86 AVL tree implementation III

Lecture 87 AVL tree implementation IV

Lecture 88 AVL tree implementation V

Lecture 89 Practical (real-world) applications of balanced binary search trees

Section 15: Balanced Trees: Red-Black Trees

Lecture 90 What are red-black trees?

Lecture 91 The logic behind red-black trees

Lecture 92 Red-black trees - recoloring and rotation cases

Lecture 93 Red-black trees visualizations

Lecture 94 Red-black tree implementation I

Lecture 95 Red-black tree implementation II

Lecture 96 Red-black tree implementation III

Lecture 97 Red-black tree implementation IV

Lecture 98 Red-black tree implementation V

Lecture 99 Differences between red-black tree and AVL trees

Section 16: Splay Trees

Lecture 100 What are splay trees?

Lecture 101 Splay tree introduction - example

Lecture 102 Splay tree implementation I

Lecture 103 Splay tree implementation II

Lecture 104 Splay tree implementation III

Lecture 105 Splay trees application

Section 17: Binary Heaps

Lecture 106 What are priority queues?

Lecture 107 Heap introduction - basics

Lecture 108 Heap introduction - array representation

Lecture 109 Heap introduction - remove operation

Lecture 110 Using heap data structure to sort (heapsort)

Lecture 111 Heap introduction - running times

Lecture 112 Binomial and Fibonacci heaps

Lecture 113 Heap implementation I

Lecture 114 Heap implementation II

Lecture 115 Heap implementation III

Lecture 116 Heaps and java.util.PriorityQueue

Section 18: Heaps Interview Questions

Lecture 117 Checking array heap representation overview

Lecture 118 Checking array heap representation solution

Lecture 119 Converting max heap to min heap overview

Lecture 120 Converting max heap to min heap solution

Section 19: B-Trees

Lecture 121 What is external memory?

Lecture 122 Disk access times

Lecture 123 What are B-trees?

Lecture 124 B-tree introduction - insertion

Lecture 125 B-tree introduction - deletion

Lecture 126 B-tree variants and file systems

Section 20: Hashtables

Lecture 127 What are associative arrays?

Lecture 128 Hashtables introduction - basics

Lecture 129 Hashtables introduction - collisions

Lecture 130 Hashtables introduction - load factor & dynamic resizing

Lecture 131 Chaining implementation I

Lecture 132 Chaining implementation II

Lecture 133 Chaining implementation III

Lecture 134 Linear probing implementation I

Lecture 135 Linear probing implementation II

Lecture 136 Generic linear probing implementation I - basics

Lecture 137 Generic linear probing implementation II - get

Lecture 138 Generic linear probing implementation III - put

Lecture 139 Generic linear probing implementation IV - remove

Lecture 140 Generic linear probing implementation V - resize

Lecture 141 Generic linear probing implementation VI - testing

Lecture 142 Maps in Java Collections

Lecture 143 Maps in Java Collections - hashCode() and equals()

Lecture 144 Why to use prime numbers in hash-functions?

Lecture 145 Practical (real-world) applications of hashing

Section 21: Hashing Interview Questions

Lecture 146 Two sum problem overview

Lecture 147 Two sum problem solution

Section 22: Basic Sorting Algorithms

Lecture 148 Sorting introduction

Lecture 149 What is stability in sorting?

Lecture 150 Adaptive sorting algorithms

Lecture 151 Bogo sort introduction

Lecture 152 Bogo sort implementation

Lecture 153 Bubble sort introduction

Lecture 154 Bubble sort implementation

Lecture 155 Selection sort introduction

Lecture 156 Selection sort implementation

Lecture 157 Insertion sort introduction

Lecture 158 Insertion sort implementation

Lecture 159 Shell sort introduction

Lecture 160 Shell sort implementation

Lecture 161 Quicksort introduction

Lecture 162 Quicksort introduction - example

Lecture 163 Quicksort implementation

Lecture 164 Hoare's partitioning and Lomuto's partitioning

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

Lecture 166 Merge sort introduction

Lecture 167 Merge sort implementation

Lecture 168 Merge sort and stack memory visualization

Lecture 169 Hybrid algorithms introduction

Lecture 170 Non-comparison based algorithms

Lecture 171 Counting sort introduction

Lecture 172 Counting sort implementation

Lecture 173 Radix sort introduction

Lecture 174 Radix sort implementation

Section 23: Substring Search

Lecture 175 Brute-force search introduction

Lecture 176 Brute-force search implementation

Lecture 177 Rabin-Karp algorithm introduction

Lecture 178 Rabin-Karp algorithm implementation

Lecture 179 Knuth-Morris-Pratt algorithm introduction

Lecture 180 Constructing the partial match table

Lecture 181 Knuth-Morris-Pratt algorithm implementation

Lecture 182 Z algorithm introduction

Lecture 183 Z algorithm illustration

Lecture 184 Z algorithm implementation

Lecture 185 Substring search algorithms comparison

Lecture 186 Applications of substring search

Section 24: BONUS: Least Recently Used (LRU) Cache

Lecture 187 Why to use cache?

Lecture 188 LRU cache introduction

Lecture 189 LRU cache implementation I

Lecture 190 LRU cache implementation II

Section 25: BONUS: Fenwick Trees (Binary Indexed Trees)

Lecture 191 What are Fenwick trees?

Lecture 192 Fenwick trees introduction - tree structure

Lecture 193 Fenwick trees introduction - update

Lecture 194 Fenwick trees implementation

Section 26: Next Steps

Lecture 195 Next steps

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

Lecture 196 How to measure the running times of algorithms?

Lecture 197 Complexity theory illustration

Lecture 198 Complexity notations - big (O) ordo

Lecture 199 Complexity notations - big Ω (omega)

Lecture 200 Complexity notations - big (θ) theta

Lecture 201 Algorithm running times

Lecture 202 Complexity classes

Lecture 203 Analysis of algorithms - loops

Lecture 204 Case study - O(1)

Lecture 205 Case study - O(logN)

Lecture 206 Case study - O(N)

Lecture 207 Case study - O(N*N)

Section 28: Algorhyme FREE Algorithms Visualizer App

Lecture 208 Algorhyme Visualization App

Lecture 209 Algorhyme - Algorithms and Data Structures

Section 29: Course Materials (DOWNLOADS)

Lecture 210 Download source code and slides

This course is meant for everyone from scientists to software developers who want to get closer to algorithmic thinking in the main