Course Materials

• Logistics, definition and examples of algorithms
• Rate of growth
• Big-O Notation

• Asymptotic Notation (Big-O and Big-Omega)

• Analysis of non-recursive algorithms (examples)

• Introduction to Recursion:
  • What is recursion? Simple recursive algorithms like factorial and Fibonacci sequence.
• Tracing Recursive Calls:
  • Walk through an example of tracing the recursive calls for a simple problem (e.g., factorial or Fibonacci).
• Common Pitfalls:
  • Discuss common mistakes students might make when writing recursive functions (e.g., missing base cases, infinite recursion).

• What is Mathematical Induction?
  • Introduce the principle with a simple non-recursive example.
• Base Case and Inductive Step:
  • Explain the two parts of an inductive proof.
• Simple Examples:
  • Work through non-recursive examples to ensure understanding.
• Introduction to Induction in Algorithms:
  • Briefly introduce how induction can be used to prove the correctness of recursive algorithms (e.g., factorial), but keep this introductory and not too detailed.

• Introduction to Recurrence Relations:
  • What recurrence relations are and how they describe the time complexity of recursive algorithms.
• Types of Recurrence Relations:
  • Linear vs non-linear recurrence relations.
• Setting Up Recurrence Relations:
  • Show how to derive recurrence relations from simple recursive algorithms like factorial, Fibonacci, and binary search.
• Methods to Solve Recurrence Relations:
  • Guess-and-Verify.

• Iterative method
• Recurrence-tree method
• Telescoping method

• Master theorem
• Proof of correctness of algorithms

• Proof of Correctness for Recursive Algorithms
• Introduction to Sorting:
  • Bubble Sort

• Introduction to Sorting:
  • Selection Sort
  • Insertion Sort
• Proof of Correctness: Loop Invariant Method

• Introduction to Divide-and-Conquer:
  • Concept: Explain the divide-and-conquer strategy in algorithm design, where problems are broken down into smaller sub-problems, solved independently, and then combined to form the final solution.
  • General Steps: Divide the problem, Conquer the sub-problems, Combine the solutions.
  • Examples: Provide an overview of where divide-and-conquer is used, such as in sorting, searching, and computational geometry.
• Merge Sort:
  • Algorithm: Introduce merge sort as another example of divide-and-conquer.
  • Merging Process: Explain how merge sort recursively divides the array and then merges sorted sub-arrays.
  • Recurrence Relation: Set up and solve the recurrence relation for merge sort.
  • Modified merge sort to reduce space complexity.

• Heap Sort:
  • Introduction to Heaps: Briefly introduce the heap data structure, focusing on the binary heap.
  • Heap Sort Algorithm: Explain how heap sort works by leveraging the heap property to efficiently sort an array.
  • Time Complexity: Analyze the time complexity (O(n log n)) and discuss why heap sort is more efficient than the basic sorting algorithms.

• Algorithm:
  • Introduce quicksort as a classic example of divide-and-conquer.
  • Partitioning: Explain the partitioning process that quicksort uses to divide the array.
  • Recurrence Relation: Set up and solve the recurrence relation for quicksort.

• Median and Order Statistics
  • Finding maximum and minimum elements in a set.

• Median and Order Statistics
  • Finding k-th smallest element in a set: QuickSelect Algorithm.
• Matrix Multiplication Basics:
  • Definition: Review the basic concept of matrix multiplication, including the rules for multiplying two matrices.
  • Algorithm: Introduce the standard matrix multiplication algorithm, detailing how the multiplication is performed element by element.
  • Example: Walk through an example of multiplying two small matrices to demonstrate the process.
• Strassen's Algorithm:
  • Introduction to Strassen's Algorithm: Introduce Strassen's algorithm as a more efficient matrix multiplication algorithm.
  • Divide-and-Conquer Approach: Explain how Strassen's algorithm uses divide-and-conquer to reduce the number of multiplications required.
  • Example: Walk through an example of Strassen's algorithm on small matrices.
• Comparative Analysis:
  • Comparison with Standard Algorithm: Compare the time complexity and space requirements of Strassen's algorithm versus the standard algorithm.
  • When to Use: Discuss scenarios where Strassen's algorithm is beneficial and where it might not be as practical.

• Introduction to Greedy Algorithms:
  • Concept: Explain the greedy approach, where local optimal choices are made at each step with the hope of finding a global optimum.
  • Greedy Choice Property and Optimal Substructure: Discuss these two key properties that justify the use of greedy algorithms.
• Scheduling Problem:
  • Problem Definition: Introduce the scheduling problem, where jobs need to be scheduled to minimize the total completion time or maximize the number of tasks completed.
  • Greedy Solution: Walk through the greedy algorithm for scheduling, explaining why it works and how it leads to an optimal solution.
  • Proof of Correctness: Use a simple example to prove the correctness of the greedy approach for the scheduling problem.

• Huffman Coding:
  • Problem Definition: Introduce the problem of constructing an optimal prefix code for data compression.
  • Greedy Algorithm: Explain the Huffman coding algorithm, focusing on how it builds the code tree using a greedy approach.
  • Time Complexity: Analyze the time complexity of Huffman coding.
  • Example: Walk through an example of constructing a Huffman tree.
• Knapsack Problem (Fractional):
  • Problem Definition: Introduce the fractional knapsack problem, where items can be divided to maximize the total value in the knapsack.

• Prim's Algorithm:
  • Concept: Introduce Prim's algorithm for finding the minimum spanning tree of a graph.
  • Algorithm: Explain how Prim's algorithm works by building the MST incrementally.
  • Time Complexity: Analyze the time complexity of Prim's algorithm.
  • Example: Walk through an example to illustrate Prim's algorithm.
• Kruskal's Algorithm:
  • Concept: Introduce Kruskal's algorithm for finding the MST using a different approach.
  • Algorithm: Explain how Kruskal's algorithm works by adding edges in order of weight.
  • Union-Find Structure: Discuss the union-find data structure used in Kruskal's algorithm.
  • Time Complexity: Analyze the time complexity of Kruskal's algorithm.
  • Example: Walk through an example to illustrate Kruskal's algorithm.

• Dijkstra's Algorithm:
  • Problem Definition: Introduce Dijkstra's algorithm for finding the shortest paths from a single source in a graph with non-negative edge weights.
  • Algorithm: Explain the step-by-step process of Dijkstra's algorithm, focusing on how it uses a greedy approach to find the shortest path.
  • Time Complexity: Analyze the time complexity of Dijkstra's algorithm, including the use of a priority queue.
  • Example: Walk through an example of Dijkstra's algorithm on a graph.
• Optimal Merge Patterns:
  • Concept: Introduce the concept of optimal merge patterns.
  • Greedy Approach: Explain how a greedy algorithm can be used to solve the OMP problem.
  • Examples: Walk through examples of OMP, illustrating how the greedy algorithm is applied.

Topics:

• Introduction to Dynamic Programming
• Principle of Optimality
• Making change

Topics:

• 0/1 Knapsack Problem formulation
• DP Solution and recurrence relation
• Related problems (Subset Sum, Equal Partition)

Topics:

• Longest Common Subsequence
• String editing and alignment
• Bellman-Ford Algorithm
• Floyd-Warshall Algorithm