Overview
-
Enhance your programming skill set by learning how to use Java to write code to implement data structures and algorithms.
Syllabus
-
1. Introduction to Algorithms
- Introduction
- Euclid's algorithm
- Bubble sort algorithm
- Why study data structures and algorithms?
- Correctness of an algorithm
- Introduction
- How to calculate the time complexity
- The RAM model of computation
- Time complexity of bubble sort algorithm
- Pseudo code: Bubble sort algorithm
- The Big O notation
- Using Big O notation: Examples
- Comparison of running times
- Selection sort
- Selection sort: Pseudocode
- Introduction to insertion sort
- Applying insertion sort algorithm to cue balls
- Insertion sort: Pseudocode
- O(n²) sorting algorithms: Comparison
- Stable vs. unstable sorts
- Searching elements in an unordered array
- Searching elements in an ordered array
- Searching elements in an ordered array continued
- Inserting and deleting items in an ordered array
- Sorting any type of object
- What is a linked list?
- Implementing a linked list in Java
- Inserting a new node
- Length of a linked list
- Deleting the head node
- Searching for an item
- Doubly ended lists
- Inserting data in a sorted linked list
- Doubly linked list
- Insertion sort revisited
- Stacks
- Abstract data types
- Implementing stacks using arrays
- Queues
- Queues using arrays
- Double-ended queues
- Double-ended queues using arrays
- Introduction
- Understanding recursion
- Tail recursion
- Tower of Hanoi
- Tower of Hanoi: Implementation
- Merge sort
- Merge sort: Pseudocode
- Merge step: Pseudocode
- Time complexity of merge sort
- The tree data structure
- Binary trees
- Binary search trees
- Finding an item in a binary search tree
- Implementing the find method
- Inserting an item in a binary search tree
- Deleting an item: Case 1
- Deleting an item: Case 2
- Deleting an item: Case 3
- Deleting an item: Soft delete
- Finding smallest and largest values
- Tree traversal: In order
- Tree traversal: Pre order
- Tree traversal: Post order
- Unbalanced trees vs. balanced trees
- Height of a binary tree
- Time complexity of operations on binary search trees
- Introduction
- Quicksort
- Quicksort: The partition step
- Shell sort
- Shell sort example
- Counting sort
- Radix sort
- Bucket sort
- Introduction
- Deleting the root
- Inserting an item in a heap
- Heaps as priority queues
- Representing heaps using arrays
- Heap sort
- Building a heap
- Introduction
- Direct access tables
- Hashing
- Resolving collisions through chaining
- The hash function
- Open addressing to resolve collisions
- Strategies for open addressing
- Time complexity: Open addressing
- Conclusion
