INTRODUCTION

• Algorithms
• Rate of Growth,
• Types of Analysis
• Asymptotic Notation
• Big-O Notation
• Master theorem for Divide and Conquer
• Method of Guessing and Confirmation

RECURSION AND BACKTRACKING

• Recursion
•  Format of Recursive Function
•  Recursion vs Iteration
• Algorithms of Recursion
• Backtracking
• Algorithms of Backtracking

LINKED LISTS

• Linked List ADT
• Comparison of Linked Lists with Arrays & Dynamic Arrays
• Singly Linked Lists
• Doubly Linked Lists
• Circular Linked Lists

STACKS

• Implementation using Array
• Implementation using Linked List

QUEUES

• Implementation using Array
• Implementation using Linked List

TREES

• What is a Tree? Binary Trees
• Generic Trees (N-ary Trees)
• Threaded Binary Tree
• Traversals (Stack or Queue-less Traversals)
• Binary Search Trees (BSTs)
•  Balanced Binary Search Trees
• AVL (Adelson-Velskii and Landis) Trees

PRIORITY QUEUES AND HEAPS

• What is a Priority Queue? Priority Queue ADT
•  Priority Queue Applications
• Priority Queue Implementations
• Heaps and Binary Heaps

DISJOINT SETS ADT

• Introduction
•  Equivalence Relations and Equivalence Classes
•  Disjoint Sets ADT Applications
•  Tradeoffs in Implementing Disjoint Sets ADT
• Fast UNION  Implementation (Slow FIND), Fast UNION Implementations  (Quick FIND)
• Path Compression
• Summary

GRAPH ALGORITHMS

• Introduction
• Applications of Graphs
• Graph Representation
• Graph Traversals
• Topological Sort
• Shortest Path Algorithm
• Minimal Spanning Tree

SORTING

• Classification of Sorting Algorithms
•  Bubble Sort, Selection Sort
• Insertion Sort
• Shell Sort
•  Merge Sort
• Heap Sort
• Quick Sort
• Tree Sort
• Comparison of Sorting Algorithms
• Linear Sorting Algorithms, Counting Sort
•  Bucket Sort (or Bin Sort), Radix Sort
• Topological Sort
• External Sorting

SEARCHING

• Types of Searching
• Unordered Linear Search
•  Sorted/Ordered Linear Search
•  Binary Search
• Interpolation Search
• Comparing Basic Searching Algorithms
• Symbol Tables and Hashing
• String Searching Algorithms

SELECTION ALGORITHMS [MEDIAN]

• What are Selection Algorithms?
• Selection by Sorting
• Partition-based Selection Algorithm
• Linear Selection Algorithm - Median of Medians Algorithm
• Finding the K Smallest
• Elements in Sorted Order

HASHING

• Introduction
• HashTable ADT
• Understanding Hashing
• Components of Hashing
• Hash Table
• Hash Function
•  Load Factor
• Collision
•  Collision Resolution
• Techniques
• Separate Chaining
• Open Addressing
• Comparison of Collision Resolution Techniques, How Hashing Gets O(1)
• Complexity? Hashing Techniques, Problems for which Hash Tables are not suitable
• Bloom Filters

STRING ALGORITHMS

• String Matching Algorithms
• Brute Force Method
• Rabin-Karp String Matching Algorithm
•  String Matching with Finite Automata
• KMP Algorithm
• Boyer-Moore Algorithm
•  Data Structures for Storing Strings
• Hash Tables for Strings, Binary Search Trees for Strings
• Tries
• Ternary Search Trees
• Comparing BSTs
• Tries and TSTs

ALGORITHMS DESIGN TECHNIQUE

• Introduction
• Classification
•  Classification by Implementation Method
•  Classification by Design Method
•  Other Classifications

GREEDY ALGORITHMS

• Introduction
• Greedy Strategy
•  Elements of Greedy Algorithms
•  Does Greedy Always Work? Advantages and Disadvantages of Greedy Method
•  Greedy Applications
• Understanding Greedy Technique

DIVIDE AND CONQUER ALGORITHMS

• Introduction
• What is Divide and Conquer Strategy? Does Divide and Conquer
• Always Work? Divide and Conquer Visualization
•  Understanding Divide and
• Conquer
•  Advantages of Divide and Conquer
•  Disadvantages of Divide and Conquer
• Master Theorem
• Divide and Conquer Applications

DYNAMIC PROGRAMMING

• Introduction
• What is Dynamic Programming Strategy? Properties of Dynamic
• Programming Strategy, Can Dynamic Programming Solve All Problems?
• Dynamic
• Programming Approaches, Examples of Dynamic Programming Algorithms
• Understanding Dynamic Programming