CS583: Analysis of Algorithms

Instructor

Giuseppe Ateniese (ateniese@gmu.edu)

Office hours: Tuesday, 4:30–5:30 PM (Zoom)

Description

Rigorous study of algorithm design and analysis. Topics include asymptotic notation, recurrence solving, divide-and-conquer, greedy methods, dynamic programming, graph algorithms (shortest paths, MST, flows and cuts), NP-completeness, reductions, approximation algorithms, and randomized algorithms. Emphasis on formal proofs of correctness and tight runtime/space analysis, as well as clear problem-solving strategies that generalize to unseen problems.

Schedule

Thursday, 4:30–7:10 PM, Horizon Hall 2014

Textbook

• Algorithm Design, Jon Kleinberg and Éva Tardos (required)

Prerequisites

Solid background in discrete mathematics and data structures. You should be comfortable with proof techniques (induction, contradiction, invariants), basic probability, and analyzing time/space complexity.

Learning Outcomes

• Analyze algorithms using asymptotic notation; solve common recurrences tightly.
• Design correct and efficient algorithms via divide-and-conquer, greedy, and dynamic programming paradigms.
• Model problems as graphs; apply shortest paths, MST, and network flow algorithms.
• Prove NP-completeness via reductions; evaluate algorithmic consequences.
• Apply approximation and randomized techniques with provable guarantees.
• Communicate proofs and analyses clearly in written solutions.

Grading

• 60% Assignments
• 40% Final Exam

Ethics and University Policies

Adherence to the GMU Common Course Policies, GMU Academic Standards, and the CS Department Honor Code is required.