COMP 368.00 Applied Algorithms

COMP 368.00 Applied Algorithms – Spring

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; appointments receive priority.

Class Tutor: TBA
MSSC Hours: TBA

---

Course Description and Learning Objectives

This course explores the design, analysis, and implementation of efficient algorithms for solving
computational problems. Students will develop mastery of core algorithmic techniques, including
divide and conquer, greedy design, dynamic programming, graph algorithms, hashing, and network flow.

The course emphasizes:

• How to analyze algorithm performance using asymptotic notation.
• How to reason about correctness, optimality, and edge cases.
• How to translate mathematical insights into efficient implementations.
• How to recognize when problems are tractable, hard, or provably intractable.

A major theme of the course is interdisciplinary application of algorithms. Students will connect classic
algorithmic methods with problems in the humanities, natural sciences, social sciences, arts, and community research.
Possible domains include:

• Cultural heritage algorithms (text alignment, clustering variants, intertextual networks).
• Summarization alignment and hallucination detection in modern AI.
• Environmental clustering and habitat detection using ecological datasets.
• Community health access modeling with shortest paths and facility-location methods.
• Exhibition-layout optimization using constraint solving and greedy heuristics.
• Philosophical decision modeling with decision trees.
• Historical diffusion modeling using graph processes.
• Economic optimization problems under constraints.
• Musical structure modeling with trees and heaps.
• Biological clustering using union–find and related methods.
• Political districting as graph partitioning.
• Archaeological spatial clustering and reconstruction.
• Art and design: algorithmic generation and layout variants.

Students will work with real datasets, public repositories, and partner organizations whenever feasible.

Prerequisites:
COMP 218: Data Structures or equivalent.
MATH 112 (Calculus II) or higher.
This course does not count toward any mathematics major requirement.

---

Course Resources

Textbook:
Steven Skiena, The Algorithm Design Manual, 2nd Edition.
Algorithm archive and resources: https://www.algorist.com/

Programming Environment:
Students may use their preferred C++, Python, or mixed environment depending on the assignment.

• Replit.com (quick start, browser-based).
• VS Code with C++ or Python tools installed.
• GitHub Classroom for assignment distribution and submission.

GitHub:
Use your Kenyon email and a name-identifiable username.
Assignments will be distributed via GitHub Classroom.
Join using the link provided on Moodle.

Moodle:
All assignments, labs, quizzes, and exams will be posted and submitted via Moodle.

---

Artificial Intelligence (AI) Use Policy

The purpose of this course is for students to learn how to design, analyze, and implement algorithms.
To ensure authentic learning, the use of AI tools is restricted.

Permitted Use:

AI tools may be used only when explicitly allowed in a particular assignment, such as:

• Generating test data or scenario variations.
• Producing small helper scripts to analyze datasets.
• Reviewing student-written code after it has been tested.
• Checking mathematical steps or verifying proofs for clarity.

Prohibited Use:

Unless explicitly permitted, students may not use AI tools or online code repositories to:

• Generate or complete code for assignments.
• Solve programming or mathematical problems.
• Rewrite or optimize assignment solutions.

All work must reflect the student’s own reasoning. Using AI or online sources beyond what is allowed
constitutes academic dishonesty.

If you are uncertain whether a particular use of AI is allowed, ask the instructor before using it.

---

Grading and Evaluation Criteria

Component	Percentage
Quizzes	20%
Interdisciplinary Labs/Projects	45%
Midterm Exam	10%
Final Exam	25%
Total	100%

---

Assessments

Quizzes

• Short quizzes at the start of many classes.
• Based on the reading and topics for the day.
• Bring a laptop to every class.
• Lowest quiz scores will be dropped.
• No makeup quizzes except for documented long-term circumstances.

Labs and Interdisciplinary Projects

• Weekly or bi-weekly algorithmic problem-solving labs.
• Projects involve applying algorithms to real or semi-real datasets.
• May include cultural heritage, ecological data, health access modeling, design optimization, or other interdisciplinary themes.
• Collaborative coding is encouraged where specified.
• Labs are the most heavily weighted part of the course.

Exams

Midterm Exam: Friday, February 28 (in class).
Final Exam: Friday, May 2 (Moodle test; details announced on Moodle).

---

Participation and Engagement

Students are expected to participate actively. Legitimate absences (illness, religious observances, athletics)
must be communicated in advance.

Participation includes:

• Attendance.
• In-class work and discussion.
• Explanations of submitted code when called upon.
• Engagement with Moodle discussions.
• Collaboration etiquette during projects.

---

Programming Assignment Grading Criteria

• Correctness: Meets requirements and handles edge cases.
• Design: Modular, well-structured algorithms.
• User Interface (when required): Clear and functional.
• Style & Documentation: Readable, well-commented code.
• Efficiency: Reasonable time/space complexity based on course expectations.

Programs failing to compile: maximum 50%.
Programs with runtime errors: maximum 75%.

---

Late Policy

Late submissions are accepted only with prior permission through the Request Form.

Options:

• One-Week Extension: Request at least 1 week in advance.
• Three-Day Extension: Request at least 3 days in advance.
• 24-Hour Extension: Request any time before the due date.

No editing of submissions after the due date without permission.

---

Academic Honesty

All work must reflect your own understanding. Pair or team work must follow the course guidelines.
Violations will follow the college’s academic honesty policy.

---

Study Tips

• Complete the reading before each class.
• Come prepared with questions about the material.
• Start labs early and work consistently.
• Make use of office hours, tutoring, and peer support.
• Practice implementing algorithms multiple times.
• Work through examples by hand before coding.

---

Tentative Course Schedule

MWF, January 12 – May 1
Spring Break: March 2–13 (no classes)
This schedule will be updated as needed on Moodle.

<

Date	Slides	Examples	Section/Topic/Reading	Quiz	Due
Jan 12	Intro	Algorithmic Thinking	Course overview; review of asymptotic notation; Skiena Ch. 1
Jan 14	Algorithms Review	Growth rates	Mathematical foundations; problem models	1
Jan 17	Divide & Conquer	Merge Sort	Skiena Ch. 2; recursion warm-up	2
Jan 19	D&C Applications	FFT overview	More divide-and-conquer; case studies
Jan 21	Engineering Algorithms	Profiling	Runtime measurement and instrumentation	3
Jan 24	Greedy Algorithms	Interval scheduling	Skiena Ch. 4
Jan 26	Greedy Failures	Counterexamples	When greedy fails; matroids intro	4
Jan 28	Interdisciplinary: Exhibition Layout	Spatial heuristics	Greedy and backtracking for layout optimization
Jan 31	Dynamic Programming	Edit distance	Skiena Ch. 6; DP introduction	5
Feb 2	DP Continued	Text alignment	Cultural heritage applications
Feb 4	DP Advanced	Sequence segmentation	Machine summarization alignment	6
Feb 7	Graphs I	BFS/DFS	Skiena Ch. 5; graph modeling
Feb 9	Graphs II	Shortest paths	Dijkstra, Bellman–Ford	7
Feb 11	Interdisciplinary: Community Health	Facility access	Shortest-path modeling on local geographic data
Feb 14	MSTs	Kruskal, Prim	Skiena Ch. 5; union–find deep dive	8
Feb 16	Environmental Clustering	Habitat detection	Real ecological network data
Feb 18	Network Flow	Max-flow min-cut	Skiena Ch. 7	9
Feb 21	Flow Applications	Matching	Stable matching; bipartite matching
Feb 23	Midterm Review	Case studies	Comprehensive review		Lab 1
Feb 28	Midterm Exam		In-class exam
Spring Break (March 2–13) – No Class
Mar 16	Approximation Algorithms	Vertex cover	NP-hardness introduction	10
Mar 18	NP-Completeness	Reductions	Skiena Ch. 8
Mar 20	Hard Problems	SAT, Clique	Reduction practice	11
Mar 23	Heuristics	Local search	Simulated annealing, hill climbing
Mar 25	Randomization	Randomized quicksort	Probabilistic analysis	12
Mar 27	Randomized Algorithms	Universal hashing	More randomness
Mar 30	Interdisciplinary: AI Hallucination Detection	Summary alignment	Ranking, clustering, and DP	13
Apr 1	String Algorithms	Suffix structures	Advanced text algorithms
Apr 3	Data-driven Algorithms	Embedding graphs	Real dataset practice	14
Apr 6	Geographic & Political Maps	Gerrymandering	Graph partitioning
Apr 8	Constraint Satisfaction	Backtracking	Applications in design and scheduling	15
Apr 10	Gallery Layout Optimization II	Constraint solving	Gund Gallery dataset
Apr 13	Biological Algorithms	Clustering	Ecosystem modeling	16
Apr 15	Approximation II	PTAS concepts	Skiena supplements
Apr 17	Wrap-up Topics	Student-chosen case studies	Course-wide integration	17	Lab 7
Apr 20	Review	Algorithms panorama	Preparation for final
Apr 22	Practice	Mixed problems	Targeted review	18
Apr 24	Course Synthesis	Interdisciplinary reflections	Conceptual wrap-up
Apr 27	Final Review	Strategy and tips	Final Q&A
May 1	Last Class	Q&A	Course evaluations and closing

Final Exam: Friday, May 2 (Moodle test; details on Moodle)