Introduction to Data Structures & Algorithms in Java

1. Introduction to Algorithms

• Introduction
• Euclid's algorithm
• Bubble sort algorithm
• Why study data structures and algorithms?
• Correctness of an algorithm

2. Analysis of Algorithms

• 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

3. Basic Sorting and Search Algorithms

• 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

4. Linked Lists

• 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

5. Stacks and Queues

• Stacks
• Abstract data types
• Implementing stacks using arrays
• Queues
• Queues using arrays
• Double-ended queues
• Double-ended queues using arrays

6. Recursion

• 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

7. Binary Search Trees

• 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

8. More Sorting Algorithms

• Introduction
• Quicksort
• Quicksort: The partition step
• Shell sort
• Shell sort example
• Counting sort
• Radix sort
• Bucket sort

9. Heaps

• Introduction
• Deleting the root
• Inserting an item in a heap
• Heaps as priority queues
• Representing heaps using arrays
• Heap sort
• Building a heap

10. Hashtables

• 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