Introduction to Data Structures & Algorithms in Java

Table of Contents

Chapter 1 : Introduction to Algorithms

Introduction

Euclid’s algorithm

Bubble Sort algorithm

Why study data structures algorithms

Correctness of an algorithm

Chapter 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

Chapter 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 un ordered array

Searching elements in an ORDERED array

Searching elements in an ORDERED array - contd.

Inserting and Deleting items in an ORDERED array

Sorting any type of object

Chapter 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

Chapter 5 : Stacks and Queues

Stacks

Abstract Data Types

Implementing Stacks using Arrays

Queues

Queues using Arrays

Double Ended Queues

Double Ended Queues using Arrays

Chapter 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

Chapter 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 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

Chapter 8 : More Sorting Algorithms

Introduction

QuickSort

QuickSort: The partition step

Shell Sort

Shell Sort Example

Counting Sort

Radix Sort

Bucket Sort

Chapter 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

Chapter 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