Cornell University · CS 4820

Introduction to Analysis of Algorithms

算法分析导论

Greedy algorithms, divide and conquer, dynamic programming, network flow, computability, and complexity.

Start with one small step

Lecture 1: Greedy Algorithms and Minimum Spanning Trees

No path choice or account is required. Start one real official item and OpenStudy will remember where you left off.

Start the first lesson ↗Preview a gentle study plan

Subject：Algorithms

Level：Advanced Undergraduate

Suggested stage：Years 3–4 (inferred)

Public-material edition：2026

Language：English

Videos：Not verified

Assignments / solutions：Not verified / Not verified

Prerequisites

Programming →Discrete mathematics →Data structures →

Start here

All official course content

Lectures, video, assignments and exams are separated so you do not have to hunt through the course homepage.

53 direct tasks

▶Lectures, video & readingCourse content in the official sequence41

Lecture 1: Greedy Algorithms and Minimum Spanning Trees Lecture 2: Minimum Spanning Trees and Interval Scheduling Lecture 3: Interval Scheduling Lecture 4: Weighted Interval Scheduling Lecture 5: Segmented Least Squares Lecture 6: Shortest Paths with Dynamic Programming Lecture 7: Sequence Alignment Lecture 8: Knapsack Lecture 9: Prelim I Review Lecture 10: Stable Matching I Lecture 11: Stable Matching II Lecture 12: Bipartite Matching and Network Flows Lecture 13: Ford-Fulkerson Lecture 14: Flow Correctness and Minimum Cuts Lecture 15: Applications of Maximum Flow Lecture 16: Applications of Minimum Cuts Lecture 17: Reductions, Independent Set, and Vertex Cover Lecture 18: P, NP, SAT, and 3-SAT Lecture 19: Independent Set NP-Completeness Lecture 20: Traveling Salesman and Hamiltonian Problems Lecture 21: Hard Problems with Numbers Lecture 22: Taxonomy of NP-Hard Problems Lecture 23: Fast Integer Multiplication Lecture 24: Fast Matrix Multiplication and the Master Theorem Lecture 25: Prelim II Review Lecture 26: Linear-Time Median Lecture 27: Convolution and Polynomial Multiplication Lecture 28: Fast Fourier Transform Lecture 29: Load-Balancing Approximation Lecture 30: Vertex Cover via Linear Programming Lecture 31: Set Cover Approximation Lecture 32: Exact Algorithms for Hard Problems Lecture 33: Cryptography I Lecture 34: Diffie-Hellman Key Exchange Lecture 35: Models of Computation and the Halting Problem Lecture 36: Undecidability via Reduction Lecture 37: Undecidability of the Halting Problem Lecture 38: Turing Machines and the Church-Turing Hypothesis Lecture 39: SAT Is NP-Complete Lecture 40: Final Review Lecture 41: Current Trends and Final Review

✓Assignments & practiceOpen the matching problem or assignment page9

Homework 1 section quiz and corrections Homework 2 section quiz and corrections Homework 4 section quiz and corrections Homework 5 section quiz and corrections Homework 6 section quiz and corrections Homework 8 section quiz and corrections Homework 9 section quiz and corrections Homework 10 section quiz and corrections Homework 11 section quiz and corrections

◇Exams & quizzesOfficial quizzes, exams and review material3

Prelim I Prelim II Final Exam

Official resource hubs

Use these to browse a complete resource collection; the section above links directly to individual study items.

SyllabusCornell University Department of Computer Science ↗

Lecture notesCornell University Department of Computer Science ↗

Source and verification

Every link points to an official university or course-team page. The year identifies the linked public-material edition, not necessarily the latest on-campus offering; a school may have newer materials that are not public. Unknown facts remain unverified rather than guessed.

Cornell University Department of Computer Science · verified 2026-07-31

Open official course ↗Report a resource issue