Instructor: James Skon
Office: Chalmers 428
Phone: 740-427-5369
Department: Computing
Class Location: Chalmers 320
Meeting Times: Monday, Wednesday, Friday, 1:10–2:00 PM
Office Hours
Times: Monday, Wednesday, Friday 9:00–11:00 AM (Chalmers 428)
Appointments: [Book Meeting Link]
Walk-ins welcome, but students with appointments will be given priority.
Class Tutor: TBA
MSSC Hours: TBA
Course Description and Learning Objectives
This course explores the design, analysis, and application of algorithms using Skiena’s The Algorithm Design Manual (3rd Edition) as the primary text. Students develop fluency in core algorithmic techniques—divide and conquer, greedy algorithms, dynamic programming, graph algorithms, network flow, randomized algorithms, and heuristics—while also learning to analyze algorithmic complexity and correctness.
A major focus of the course is applying algorithmic thinking across disciplines. Students will work with real datasets and problem domains from cultural heritage, environmental science, public health, art and design, political science, and AI evaluation. The goal is to experience algorithms as practical tools for solving real-world problems, not just abstract exercises.
Another important component is engineering correct, efficient, and readable implementations. Many labs involve experimentation, performance measurement, and comparing algorithmic strategies.
Prerequisites:
COMP 218 (Data Structures) or equivalent foundational course.
MATH 112 (Calculus II) or higher.
This course does not count toward the mathematics major.
Course Text and Resources
Primary Textbook:
The Algorithm Design Manual, 3rd Edition, Steven S. Skiena.
(Springer, ISBN 978-3-030-54256-6)
Recommended:
Skiena’s online “Hitchhiker’s Guide to Algorithms,” problem catalog, and datasets.
Programming Environment:
Students may use C++, Python, or Java depending on lab requirements.
GitHub Classroom will be used for distribution and submission of labs.
Moodle:
All quizzes, exams, and lab submissions will be through Moodle unless otherwise noted.
Artificial Intelligence (AI) Use Policy
AI tools (ChatGPT, GitHub Copilot, etc.) may only be used when explicitly allowed in specific assignments. Allowable uses may include:
- generating test data
- writing test drivers
- reviewing and commenting on your own code
- generating visualizations
Prohibited uses (unless explicitly permitted):
- generating code solutions
- fixing or completing your lab or project work
- using online solutions (StackOverflow, GitHub repositories, etc.)
Using AI or online sources to produce assignment code constitutes academic dishonesty. All submitted work must reflect your own understanding. If in doubt, ask before using AI.
Grading and Evaluation Criteria
Component Percentage
Quizzes 15%
Labs (10 total) 40%
Midterm Exam 15%
Final Exam/Project 30%
Total 100%
Assessments
Quizzes:
Frequent short quizzes at the start or end of class based on reading and recent topics.
Lowest n quiz scores will be dropped.
No makeup quizzes except for documented long-term circumstances.
Labs (10):
Weekly to biweekly labs form the backbone of the course.
Labs involve implementing algorithms, analyzing performance, and applying methods to real datasets.
Some labs are interdisciplinary and use external data sources.
Exams:
Midterm Exam: in-class exam before Spring Break.
Final Exam or Final Project: To be announced (may include both algorithmic problems and a programming component).
Participation and Engagement:
Attendance, engagement, participation in discussion, and ability to explain your code when asked.
Programming Assignment Grading Criteria
Correctness: Meets requirements, handles all inputs.
Design: Includes appropriate algorithms, structure, and decomposition.
Implementation Quality: Clean, readable, documented code.
Efficiency: Time and space usage appropriate for the problem.
Robustness: Programs should compile; non-compiling labs earn at most 50%.
Runtime Issues: Programs with runtime errors earn at most 75%.
Late Policy
Late submissions are accepted only with prior permission via the Request Form.
One Week Extension: Must request at least one week before due date.
Three-Day Extension: Must request three days before due date.
24-Hour Extension: Must request before the assignment deadline.
Do not modify submissions after the deadline without permission.
Academic Honesty
All work must reflect your own understanding. Collaboration must follow instructions for each assignment. Violations will be handled under the college’s Academic Honesty Policy.
Study Tips
- Read assigned textbook sections before class.
- Take notes on confusing concepts to ask during discussion.
- Start labs early; many require iterative refinement and debugging.
- Attend office hours or tutoring early and often.
- Practice solving algorithmic problems regularly.
Labs (10 Total)
Lab 1: Algorithm Analysis and Benchmarking
Measure performance of simple algorithms; build empirical complexity intuition.
Lab 2: Divide and Conquer
Implement merge sort or quicksort; analyze recursion behavior.
Lab 3: Greedy Algorithms
Solve interval scheduling or similar tasks; evaluate when greedy strategies succeed or fail.
Lab 4: Dynamic Programming
Implement edit-distance or sequence alignment; apply to textual/cultural data.
Lab 5: Graph Algorithms I
Implement BFS/DFS; analyze connectivity and structure.
Lab 6: Graph Algorithms II
Implement shortest paths or MST; use union–find.
Lab 7: Network Flow and Matching
Implement max-flow/min-cut or bipartite matching; apply to community health or network tasks.
Lab 8: Randomized and Hashing Algorithms
Explore randomized quicksort, universal hashing, or probabilistic methods.
Lab 9: NP-Complete Problems and Heuristics
Experiment with heuristics for SAT, TSP variants, or partitioning.
Lab 10: Interdisciplinary Applied Project
Choose a dataset or domain (AI alignment, ecology, political mapping, gallery layout, cultural heritage, etc.); design, implement, and evaluate an algorithmic solution.
Tentative Schedule (High-Level)
Weeks 1–2: Algorithm Analysis; Mathematical Foundations; Skiena Ch. 1–2
Weeks 3–4: Divide and Conquer; Recursion; Skiena Ch. 5
Weeks 5–6: Greedy Algorithms and Heuristics; Skiena Ch. 4
Weeks 7–8: Dynamic Programming; Skiena Ch. 6
Weeks 9–10: Graph Algorithms; Shortest Paths; MSTs; Skiena Ch. 5
Week 11: Network Flow and Matching; Skiena Ch. 7
Week 12: Randomized and Approximation Algorithms
Week 13: NP-Completeness and Hard Problems; Skiena Ch. 12–13
Weeks 14–15: Interdisciplinary Applications and Project Work
Finals Week: Final Exam or Final Project Presentations
| Date | Slides | Examples | Section / Topic / Reading | Quiz | Due |
|---|---|---|---|---|---|
| Jan 12 | Intro | Algorithmic Thinking | Course overview; asymptotics review; Skiena Ch. 1 | ||
| Jan 14 | Algorithm Analysis | Benchmarking | Mathematical foundations; empirical performance | 1 | |
| Jan 17 | Divide & Conquer I | Merge Sort | Skiena Ch. 5; recursion warm-up | 2 | |
| Jan 19 | Divide & Conquer II | FFT overview | Case studies; recursion tree analysis | ||
| Jan 21 | Algorithm Engineering | Profiling Tools | Runtime measurement; optimization basics | 3 | |
| Jan 24 | Greedy Algorithms I | Interval Scheduling | Skiena Ch. 4; greedy design patterns | ||
| Jan 26 | Greedy Algorithms II | Counterexamples | Matroids; when greedy strategies fail | 4 | |
| Jan 28 | Applied: Exhibition Layout | Spatial heuristics | Hybrid greedy/backtracking strategies | ||
| Jan 31 | Dynamic Programming I | Edit distance | Skiena Ch. 6; DP introduction | 5 | |
| Feb 2 | Dynamic Programming II | Text alignment | Cultural heritage applications | ||
| Feb 4 | Dynamic Programming III | Segmentation models | Machine summarization alignment | 6 | |
| Feb 7 | Graphs I | BFS / DFS | Graph modeling; representations | 7 | |
| Feb 9 | Graphs II | Shortest paths | Dijkstra; Bellman–Ford | ||
| Feb 11 | Applied: Community Health | Facility access | Geographic shortest-path modeling | ||
| Feb 14 | MST and Union–Find | Kruskal; Prim | Skiena Ch. 5; disjoint-set deep dive | 8 | |
| Feb 16 | Applied: Environmental Clustering | Habitat networks | Ecological datasets | ||
| Feb 18 | Network Flow I | Max-flow | Skiena Ch. 7 | 9 | |
| Feb 21 | Network Flow II | Matching | Stable/bipartite matching | ||
| Feb 23 | Midterm Review | Case studies | Comprehensive review | Lab 1 | |
| Feb 28 | Midterm Exam | In-class exam | |||
| Mar 2–13 | Spring Break | No class | |||
| Mar 16 | Approximation Algorithms | Vertex cover | NP-hardness introduction | 10 | |
| Mar 18 | NP-Completeness | Reductions | Skiena Ch. 12 | ||
| Mar 20 | Hard Problems | SAT; Clique | Reduction practice | 11 | |
| Mar 23 | Heuristics I | Local search | Simulated annealing; hill climbing | ||
| Mar 25 | Randomization I | Randomized quicksort | Probabilistic analysis | 12 | |
| Mar 27 | Randomization II | Universal hashing | Randomization techniques | ||
| Mar 30 | Applied: AI Hallucination | Summary alignment | Ranking; clustering; dynamic programming | 13 | |
| Apr 1 | String Algorithms | Suffix structures | Text indexing; pattern search | ||
| Apr 3 | Data-driven Algorithms | Embedding graphs | Real dataset analysis | 14 | |
| Apr 6 | Political Maps | Gerrymandering | Graph partitioning | ||
| Apr 8 | Constraint Satisfaction | Backtracking | CSP applications | 15 | |
| Apr 10 | Gallery Layout Optimization II | Constraint solving | Gund Gallery datasets | ||
| Apr 13 | Biological Algorithms | Clustering | Ecosystem modeling | 16 | |
| Apr 15 | Approximation II | PTAS concepts | Advanced approximation | ||
| Apr 17 | Wrap-up Topics | Case studies | Algorithmic synthesis | 17 | Lab 7 |
| Apr 20 | Final Review I | Algorithms panorama | Exam preparation | ||
| Apr 22 | Final Review II | Mixed problems | Targeted practice | 18 | |
| Apr 24 | Course Synthesis | Interdisciplinary wrap | Conceptual integration | ||
| Apr 27 | Final Review III | Strategy and tips | Final Q&A | ||
| May 1 | Last Class | Q&A | Course evaluations and closing |