Introduction to Algorithms
Course Topics
- Week 1: Introduction to Algorithms
- Overview of algorithms and their importance.
- Basic algorithmic problem-solving techniques.
- Algorithm analysis: time complexity and big-O notation.
- Week 2: Divide and Conquer
- Introduction to the divide and conquer paradigm.
- Recursive algorithms and recurrence relations.
- Examples: merge sort, quicksort.
- Week 3: Greedy Algorithms
- Introduction to greedy algorithms and their properties.
- Examples: activity selection, Huffman coding.
- Week 4: Dynamic Programming
- Introduction to dynamic programming.
- Memoization and tabulation techniques.
- Examples: Fibonacci numbers, shortest paths.
- Week 5: Graph Algorithms
- Basic graph terminology and representations.
- Graph traversal algorithms: depth-first search, breadth-first search.
- Minimum spanning trees and shortest paths.
- Week 6: Network Flows
- Introduction to network flow problems.
- Maximum flow and minimum cut.
- Applications of network flow algorithms.
- Week 7: NP-Completeness
- Introduction to computational complexity.
- Polynomial-time algorithms and NP-completeness.
- Reductions and NP-complete problems.
- Week 8: Approximation Algorithms
- Introduction to approximation algorithms.
- Greedy approximation algorithms.
- Approximation schemes and heuristics.
- Week 9: Linear Programming
- Introduction to linear programming.
- Formulating optimization problems as linear programs.
- Simplex algorithm and duality.
- Week 10: String Matching and Data Compression
- String matching algorithms: brute force, Knuth-Morris-Pratt, Boyer-Moore.
- Introduction to data compression techniques.
- Week 11: Parallel and Distributed Algorithms
- Introduction to parallel and distributed computing.
- Parallel algorithm design and analysis.
- Distributed algorithms and their challenges.
- Week 12: Online Algorithms
- Introduction to online algorithms.
- Competitive analysis and the adversary model.
- Examples: paging, load balancing.
- Week 13: Quantum Algorithms
- Introduction to quantum computing.
- Quantum algorithms: Grover's algorithm, Shor's algorithm.
- 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.
- 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.