Catholic Tech

Introduction to Algorithms

Course Topics

  1. Week 1: Introduction to Algorithms
    • Overview of algorithms and their importance.
    • Basic algorithmic problem-solving techniques.
    • Algorithm analysis: time complexity and big-O notation.
  2. Week 2: Divide and Conquer
    • Introduction to the divide and conquer paradigm.
    • Recursive algorithms and recurrence relations.
    • Examples: merge sort, quicksort.
  3. Week 3: Greedy Algorithms
    • Introduction to greedy algorithms and their properties.
    • Examples: activity selection, Huffman coding.
  4. Week 4: Dynamic Programming
    • Introduction to dynamic programming.
    • Memoization and tabulation techniques.
    • Examples: Fibonacci numbers, shortest paths.
  5. Week 5: Graph Algorithms
    • Basic graph terminology and representations.
    • Graph traversal algorithms: depth-first search, breadth-first search.
    • Minimum spanning trees and shortest paths.
  6. Week 6: Network Flows
    • Introduction to network flow problems.
    • Maximum flow and minimum cut.
    • Applications of network flow algorithms.
  7. Week 7: NP-Completeness
    • Introduction to computational complexity.
    • Polynomial-time algorithms and NP-completeness.
    • Reductions and NP-complete problems.
  8. Week 8: Approximation Algorithms
    • Introduction to approximation algorithms.
    • Greedy approximation algorithms.
    • Approximation schemes and heuristics.
  9. Week 9: Linear Programming
    • Introduction to linear programming.
    • Formulating optimization problems as linear programs.
    • Simplex algorithm and duality.
  10. Week 10: String Matching and Data Compression
    • String matching algorithms: brute force, Knuth-Morris-Pratt, Boyer-Moore.
    • Introduction to data compression techniques.
  11. Week 11: Parallel and Distributed Algorithms
    • Introduction to parallel and distributed computing.
    • Parallel algorithm design and analysis.
    • Distributed algorithms and their challenges.
  12. Week 12: Online Algorithms
    • Introduction to online algorithms.
    • Competitive analysis and the adversary model.
    • Examples: paging, load balancing.
  13. Week 13: Quantum Algorithms
    • Introduction to quantum computing.
    • Quantum algorithms: Grover's algorithm, Shor's algorithm.
  14. Week 14: Advanced Topics (Selected Topics)
    • Advanced data structures: AVL trees, B-trees.
    • Geometric algorithms: convex hull, closest pair.
    • Randomized algorithms: Monte Carlo and Las Vegas algorithms.
  15. Week 15: Review and Final Project
    • Review of key concepts and algorithms.
    • Final project: Design and implementation of an algorithm for a real-world problem.

Disclaimer

The course syllabus is subject to change at the discretion of the instructor. Any modifications or updates will be communicated in advance.