Project 125%
Race Your Sort
Write one sorting algorithm from scratch and race it against Python's built-in sort on three input shapes. Hand in the code and a screenshot of the race — no report.
Full specification: Race Your Sort →Fall 2026 · Section 001 · Class #4435 · 3 credits
AI 230
Introduction to Algorithms
This course introduces the design, analysis, and practical implementation of algorithms. Students learn to reason about correctness and efficiency, to select and adapt appropriate algorithmic strategies for a problem, and to justify their choices with both mathematical analysis and empirical measurement. Every major technique — divide and conquer, greedy methods, dynamic programming, graph traversal, and the boundaries of tractability — is developed through working code applied to realistic problems rather than through proof exercises alone.
Tue & Thu 4:00 – 5:50 PM
Online — all sessions live on Google Meet
Room of record: Pratt 520
Dial in: +1 573-741-0170 · PIN 948 640 826# · more numbers
Lecture notes
Session Notes
Posted before the session they're used in and kept available all term. Each set is a self-contained page — read it, work the examples, and bring questions.
01
Algorithmic Thinking, Specification, and Correctness
WEEK 1 · S1 · SEP 3 02 Asymptotic Analysis: Big-O, Omega, Theta
WEEK 2 · S2–S3 · SEP 8, SEP 10 03 Recursion, Recurrences, and the Master Theorem
WEEK 3 · S4–S5 · SEP 15, SEP 17 04 Sorting: Insertion, Merge, and Quicksort
WEEK 4 · S6–S7 · SEP 22, SEP 24 05 Sorting II: Heaps, Floors, and Clever Cheats
WEEK 5 · S8–S9 · SEP 29, OCT 1 06 Hash Tables: Hashing, Collisions, Load Factor, and Amortized Cost
WEEK 6 · S10–S11 · OCT 6, OCT 8 07 Trees, Binary Search Trees, Balancing, Heaps and Priority Queues
WEEK 7 · S12–S13 · OCT 13, OCT 15 08 Greedy: The Algorithm That Never Looks Back
WEEK 8 · S14–S15 · OCT 20, OCT 22 09 Dynamic Programming: Greedy That Keeps Receipts
WEEK 9 · S16–S17 · OCT 27, OCT 29 10 Dynamic Programming II: Edit Distance, DNA, and the Notebook in the Trees
WEEK 10 · S18–S19 · NOV 3, NOV 5 11 Graphs: Maps, Mazes, and Exploring Without Getting Lost
WEEK 11 · S20–S21 · NOV 10, NOV 12 12 The Cheapest Network: Kruskal, Prim, and Union-Find
WEEK 12 · S22–S23 · NOV 17, NOV 19
WEEK 1 · S1 · SEP 3 02 Asymptotic Analysis: Big-O, Omega, Theta
WEEK 2 · S2–S3 · SEP 8, SEP 10 03 Recursion, Recurrences, and the Master Theorem
WEEK 3 · S4–S5 · SEP 15, SEP 17 04 Sorting: Insertion, Merge, and Quicksort
WEEK 4 · S6–S7 · SEP 22, SEP 24 05 Sorting II: Heaps, Floors, and Clever Cheats
WEEK 5 · S8–S9 · SEP 29, OCT 1 06 Hash Tables: Hashing, Collisions, Load Factor, and Amortized Cost
WEEK 6 · S10–S11 · OCT 6, OCT 8 07 Trees, Binary Search Trees, Balancing, Heaps and Priority Queues
WEEK 7 · S12–S13 · OCT 13, OCT 15 08 Greedy: The Algorithm That Never Looks Back
WEEK 8 · S14–S15 · OCT 20, OCT 22 09 Dynamic Programming: Greedy That Keeps Receipts
WEEK 9 · S16–S17 · OCT 27, OCT 29 10 Dynamic Programming II: Edit Distance, DNA, and the Notebook in the Trees
WEEK 10 · S18–S19 · NOV 3, NOV 5 11 Graphs: Maps, Mazes, and Exploring Without Getting Lost
WEEK 11 · S20–S21 · NOV 10, NOV 12 12 The Cheapest Network: Kruskal, Prim, and Union-Find
WEEK 12 · S22–S23 · NOV 17, NOV 19
Fifteen weeks
Weekly Schedule
The schedule is aligned to the LIU Brooklyn academic calendar; any session affected by a University holiday or closure is adjusted and announced in class and on Brightspace. The current week is highlighted.
| Week | Sessions | Topic | Materials | To do |
|---|---|---|---|---|
| WK 1 | S1 · Sep 3 | Course overview. Algorithmic thinking, problem specification, and correctness | Notes 01 |
|
| WK 2 | S2–S3 · Sep 8, Sep 10 | Asymptotic analysis: Big-O, Omega, Theta. Analyzing loops | Notes 02 |
|
| WK 3 | S4–S5 · Sep 15, Sep 17 | Recursion, recurrence relations, and the Master Theorem | Notes 03 |
|
| WK 4 | S6–S7 · Sep 22, Sep 24 | Sorting I: insertion, merge, and quicksort. Divide and conquer | Notes 04 |
|
| WK 5 | S8–S9 · Sep 29, Oct 1 | Sorting II: heapsort, lower bounds, counting and radix sort. Searching | Notes 05 |
|
| WK 6 | S10–S11 · Oct 6, Oct 8 | Hash tables: hashing, collisions, load factor, and amortized cost | Notes 06 |
|
| WK 7 | S12–S13 · Oct 13, Oct 15 | Trees, binary search trees, balancing, heaps and priority queues | Notes 07 |
|
| WK 8 | S14–S15 · Oct 20, Oct 22 | Greedy algorithms: interval scheduling, Huffman coding, exchange arguments Project 1 due (Oct 19) |
Notes 08 |
|
| WK 9 | S16–S17 · Oct 27, Oct 29 | Dynamic programming I: memoization, knapsack, longest common subsequence | Notes 09 |
|
| WK 10 | S18–S19 · Nov 3, Nov 5 | Dynamic programming II: edit distance, sequence alignment, DP on trees | Notes 10 |
|
| WK 11 | S20–S21 · Nov 10, Nov 12 | Graphs: representations, BFS, DFS, topological sort, connectivity Project 2 due (Nov 9) |
Notes 11 |
|
| WK 12 | S22–S23 · Nov 17, Nov 19 | Minimum spanning trees (Kruskal, Prim) and union-find Project 3 due (Nov 16) |
Notes 12 |
|
| WK 13 | S24 · Nov 24 | Shortest paths: Dijkstra, Bellman-Ford, Floyd-Warshall. Introduction to flow◦ Nov 26 — no class (Thanksgiving) Capstone proposal due |
Notes 13 · soon |
|
| WK 14 | S25–S26 · Dec 1, Dec 3 | Tractability: P, NP, NP-completeness, and reductions in practice | Notes 14 · soon |
|
| WK 15 | S27–S28 · Dec 8, Dec 10 | Approximation, randomization, and heuristics. Capstone presentations | Notes 15 · soon |
|
| FINALS | Dec 14 – 21 | Final capstone deliverables due. No final examination. | ||
No examinations
Projects & Grading
This course is graded entirely on four hands-on projects — there are no exams. Specifications and rubrics are released at least two weeks before each due date. Every project is submitted as a Git repository plus a written report; late work is reduced by 10% per calendar day.
Project 225%
Break the Hash Table
Play the villain: find five words that all crash into the same bucket of a bad hash table, and watch O(1) collapse to O(n) in a provided script. One script and one screenshot — no report.
Full specification: Break the Hash Table →Project 325%
Optimization Engine
Solve a single realistic optimization problem twice — once with a greedy strategy and once with dynamic programming — and report on correctness, optimality, and cost, stating precisely when the greedy approach is safe and when it fails.
Specification released in classProject 425%
Capstone: Graph-Based Application
Design and build an application driven by graph algorithms (routing, scheduling, dependency resolution, or recommendation) that includes at least one computationally hard subproblem addressed by a heuristic. Working system, technical report, and a live presentation during the final session block.
Specification released in classGrading rubric — how every project is assessed
Every project is graded on the same four criteria. Each project rubric is released with its specification.
| Criterion | Weight | What is assessed |
|---|---|---|
| Correctness and completeness | 35% | The artifact does what the specification requires, and the required cases are handled. |
| Implementation quality | 20% | Structure, readability, and evidence of testing. Commit history shows sustained individual work. |
| Analysis and written report | 25% | The report explains the design, justifies the decisions, and reports results honestly, including what did not work. |
| Demonstration and defense | 20% | The student can run the artifact live and answer questions about any part of it. |
Grading scale
| Letter | Range % | GPA |
|---|---|---|
| A | 93–100 | 4.00 |
| A- | 90–92 | 3.67 |
| B+ | 87–89 | 3.33 |
| B | 83–86 | 3.00 |
| B- | 80–82 | 2.67 |
| C+ | 77–79 | 2.33 |
| C | 73–76 | 2.00 |
| C- | 68–72 | 1.67 |
| D | 60–67 | 1.00 |
| F | < 60 | 0.00 |
Expected time commitment (160 h total)
| Synchronous class sessions | 51 h |
| Review of posted notes | 30 h |
| Project 1 — Race Your Sort | 17 h |
| Project 2 — Break the Hash Table | 20 h |
| Project 3 — Optimization Engine | 20 h |
| Project 4 — Capstone and presentation | 22 h |
| Total | 160 h |
The fine print
Course Info & Policies
Prerequisites
Introductory programming proficiency in a language of your choice (Python recommended) and college-level discrete mathematics, or permission of the instructor.
Software & tools — all free
- Python 3.11 or later (primary language for all projects; another language may be used with prior approval)
- Git and a personal GitHub account
- A code editor of your choice (VS Code recommended)
- Jupyter Notebook or equivalent, for benchmarking and analysis write-ups
- Google Meet, for all synchronous class sessions
What you'll be able to do
- Analyze the time and space complexity of an algorithm and express the result in correct asymptotic notation.
- Implement, test, and empirically benchmark fundamental sorting, searching, and data-structure algorithms.
- Select and justify an appropriate algorithmic strategy — divide and conquer, greedy, or dynamic programming — for an unfamiliar problem.
- Model a real-world problem as a graph and apply traversal, spanning-tree, and shortest-path algorithms to solve it.
- Recognize computationally intractable problems and design a defensible heuristic or approximation approach.
- Communicate an algorithmic design and its performance characteristics in written form and in a technical presentation.
Live sessions & attendance
All class sessions are held live on Google Meet at the scheduled times. Students are expected to attend, to have their development environment running, and to be able to share their screen when demonstrating work. Every student presents current work and takes part in critique at each meeting.
Communication
Modes of communication are Brightspace (lms.liu.edu) and email; expect a reply within 24 hours. Virtual office hours are held by appointment — email the instructor to schedule.
Materials & this site
All course notes, examples, and project specifications are distributed through the course repository and this site. Students are responsible for reviewing the current version before each session.
Submission & late work
Every project is submitted through Brightspace as a link to the student's Git repository, together with the written report. Commit history is part of the evidence of individual work. Late work is reduced by 10% per calendar day. Extensions are granted only for a documented medical or family emergency, requested before the deadline by email.
Individual work & AI use
Projects are individual work unless a specification explicitly designates a team deliverable. Discussing approaches is fine, but submitted code, models, and writing must be your own. Generative AI tools may be used as a learning aid and are treated like any other reference: any AI-assisted portion of a submission must be disclosed in the project report, and you must be able to explain and defend every line of what you submit.
Recording
Recording of class sessions by students is not permitted without the instructor's prior written consent.
Accommodations
Students with a documented disability/impairment who require reasonable accommodations should provide an Accommodation Letter from Student Support Services (Sloan Building, 1st Floor · 718-488-1044 · studentsupportservices@brooklyn.liu.edu · Mon–Fri 9am–5pm).
Technical issues
For issues with Brightspace, LIU email, Google Meet, or campus network access, contact IT: It@liu.edu · 718-488-3300 (Mon–Fri 9am–5pm).