Introduction to Algorithm Design and Analysis
Algorithmic problems and their mathematical modeling; describing algorithms using pseudocode; correctness and termination; time and space complexity; best-case, worst-case, and average-case analysis; asymptotic notation O, Ω, and Θ; summations and recurrence relations; the Master Theorem.
Fundamental Algorithm Design Techniques
Brute-force search and backtracking; divide-and-conquer; greedy algorithms; dynamic programming; and randomized algorithms. Selection of the appropriate technique based on the structure of the problem. Correctness proofs using mathematical induction, loop invariants, and exchange arguments.
Sorting, Searching, and Selection
Comparison-based sorting algorithms; merge sort, quicksort, and heapsort; finding the median and the k-th smallest element; lower bounds in the comparison model.
Graph Algorithms
Graph representations; breadth-first search (BFS) and depth-first search (DFS); connectivity; bipartiteness; topological ordering; strongly connected components; minimum spanning trees; shortest paths; maximum flow; minimum cut; and bipartite matching.
Computational Complexity and Reductions
Decision problems; efficient and inefficient algorithms; certificates and verification; the complexity classes P and NP; polynomial-time reductions; NP-hardness and NP-completeness; the Cook-Levin Theorem; classical NP-complete problems; and techniques for proving NP-completeness.
Algorithms for Computationally Hard Problems
Randomized and approximation algorithms; approximation ratios; heuristic methods; and other techniques for tackling problems for which no efficient exact algorithms are known.
Selected Topics in Algorithms and Applications:
Presentation of additional areas of algorithmics, depending on available time and course interests. Topics may include, for example, string algorithms, computational geometry, algorithmic number theory and cryptography, online or approximation algorithms, and applications to modern computational problems.
Learning Outcomes
The course introduces the fundamental principles and methodologies of algorithm design and analysis, with particular emphasis on the theoretical foundations and practical aspects of efficient computation. Its primary objective is to cultivate algorithmic thinking, enabling students to transform informal problem descriptions into rigorous mathematical formulations, design correct and efficient algorithmic solutions, and systematically evaluate their computational complexity.
Upon successful completion of the course, students will be able to:
- Model real-world problems as well-defined mathematical and computational problems by identifying relevant inputs, outputs, and constraints.
- Formulate, specify, and communicate algorithms precisely using appropriate pseudocode and mathematical notation.
- Design algorithms based on fundamental paradigms, including brute-force search, divide-and-conquer, greedy methods, dynamic programming, backtracking, and local search.
- Select and justify appropriate algorithmic design techniques by recognizing the structural properties of computational problems.
- Establish the correctness of algorithms using rigorous proof techniques, including mathematical induction, loop invariants, exchange arguments, and proof by contradiction.
- Analyze the time and space complexity of algorithms using asymptotic analysis, summation techniques, and recurrence relations.
- Critically compare alternative algorithmic solutions in terms of correctness, computational efficiency, memory usage, and applicability to different classes of inputs.
- Distinguish between computational problems that admit efficient solutions and those that are considered computationally intractable.
- Understand and apply core concepts of computational complexity theory, including the complexity classes P and NP, polynomial-time reductions, NP-hardness, and NP-completeness.
- Present algorithmic solutions in a rigorous and coherent manner, providing clear justification of design decisions, correctness proofs, and complexity analyses.
Announcements
|
News
