Syllabus for CS 2500: Algorithms (Fall 2024)

Course Format

4 credit hours
3 LEC + 1 LAB per week

Prerequisites

CS 1200, CS 1575
Math 1208 or Math 1214

Assessment

Assignments: 50%
Midterm: 25%
Final: 25%

1. Fundamentals of Algorithms

  • Definition and examples of algorithms
  • Algorithm analysis and complexity
  • Asymptotic Notation: Big-O, Big-Omega, and Big-Theta
  • Analysis of non-recursive algorithms
  • Counting and rate of growth
  • Tractable vs Intractable problems

2. Recursion and Mathematical Induction

2.1 Recursion Fundamentals

  • Introduction to recursion
  • Simple recursive algorithms (factorial, Fibonacci)
  • Tracing recursive calls
  • Common pitfalls and debugging techniques

2.2 Mathematical Induction

  • Principles of mathematical induction
  • Base case and inductive step
  • Non-recursive examples and applications
  • Common mistakes in inductive proofs

2.3 Recurrence Relations

  • Introduction to recurrence relations
  • Linear vs non-linear recurrence relations
  • Methods to solve recurrence relations:
    • Guess-and-verify (Substitution method)
    • Iteration/Substitution method
    • Recurrence-tree method
    • Telescoping/Difference method
    • Master theorem

3. Basic Sorting Algorithms

  • Introduction to sorting and its importance
  • Comparison-based sorting algorithms
  • Bubble Sort: algorithm and analysis
  • Selection Sort: algorithm and analysis
  • Insertion Sort: algorithm and analysis
  • Proof of correctness for sorting algorithms

4. Advanced Sorting and Divide-and-Conquer

4.1 Heap Sort

  • Introduction to heaps and heap properties
  • Heap Sort algorithm and implementation
  • Time complexity analysis

4.2 Divide-and-Conquer Strategy

  • Principles of divide-and-conquer
  • Problem decomposition and solution combination
  • Applications in sorting and searching

4.3 Merge Sort

  • Merge Sort algorithm and implementation
  • Merging process analysis
  • Recurrence relation and complexity
  • Modified merge sort variants

4.4 Quick Sort

  • Quick Sort algorithm and implementation
  • Partitioning strategies
  • Time complexity analysis
  • Practical considerations and optimizations

5. Order Statistics and Matrix Operations

5.1 Order Statistics

  • Finding maximum and minimum elements
  • Selection algorithms for k-th smallest element
  • QuickSelect algorithm

5.2 Matrix Multiplication

  • Standard matrix multiplication algorithm
  • Strassen's algorithm
  • Comparative analysis and applications

6. Greedy Algorithms

  • Greedy algorithm principles
  • Scheduling problems and solutions
  • Huffman coding
  • Fractional Knapsack problem
  • Minimum Spanning Trees:
    • Prim's algorithm
    • Kruskal's algorithm
  • Dijkstra's algorithm for shortest paths
  • Optimal merge patterns

7. Dynamic Programming

7.1 Fundamentals

  • Principle of optimality
  • Memoization and tabulation
  • Basic examples: Binomial Coefficient, Making Change

7.2 Classical Problems

  • 0/1 Knapsack and variations
  • Subset Sum Problem
  • Equal Sum Partition Problem
  • Longest Common Subsequence
  • Longest Common Substring
  • String transformation problems
  • Longest Palindromic Subsequence

7.3 Advanced Applications

  • Unbounded Knapsack
  • Rod Cutting Problem
  • Coin Change Problems
  • Shortest Path Algorithms:
    • Bellman-Ford Algorithm
    • Floyd-Warshall Algorithm