Introduction to Searching Algorithms

• Sequential Search

  1. Linear search in unsorted and sorted arrays.

• Binary Search

  1. Prerequisite: understanding of sorted arrays.

  2. Recursive and iterative implementations.

Hashing and Hash Tables

• Hash Functions

  1. Properties of good hash functions.

• Collision Resolution Strategies

  1. Chaining.

  2. Open addressing: linear probing, quadratic probing, double hashing.

• Load Factor and Resizing

  1. Impact on performance.

Sorting Algorithms

• Simple Sorts

  1. Bubble sort.

  2. Selection sort.

  3. Insertion sort.

  4. When and why to use them.

• Efficient Sorts

  1. Merge Sort

     1. Divide and conquer strategy.

  2. Quick Sort

     1. Partitioning method.

  3. Heap Sort

     1. Utilizing heap data structure.

• Non-Comparison Sorts (if time allows)

  1. Counting sort.

  2. Radix sort.

Sorting with Permutation Arrays

• Concepts and practical applications.

Comparison of Sorting Algorithms

• Time Complexity

  1. Best, average, and worst-case scenarios.

• Space Complexity

  1. In-place sorting vs. additional memory.

• Stability in Sorting

  1. Importance and implications.

Algorithm Analysis Techniques

• Big O Notation

  1. Formal definitions.

  2. Common time complexities.

• Best, Average, and Worst-Case Analysis

  1. Understanding different performance scenarios.

Mathematical Foundations

• Recurrence Relations

  1. Solving recurrences using substitution and recursion tree methods.

• Master Theorem

  1. Application to divide and conquer algorithms.

Algorithm Correctness

• Proof Techniques

  1. Loop invariants.

  2. Mathematical induction.

• Case Studies

  1. Correctness proofs for common algorithms.

Applications and Case Studies

• Practical applications of searching and sorting in real-world systems.