Instructor: Prof. Seth Fogarty Email: sfogarty@trinity.edu
Office: CSI 270M Office Hours: Posted on webpage
Meets: MW at 2:30 in CSI 257 Textbook: Algorithms, by Jeff Erickson
The purpose of this course is to explore: computational problems; the design, implementation, and analysis of algorithms to solve those problems; reductions between problems. We will cover four broad categories of algorithms: recursive algorithms, dynamic programming, tree and graph-based algorithms, and algorithms over weighted graphs. Within each category we will analyze correctness and complexity, implement known algorithms, and design new algorithms. Special focus is given to reductions between problems: these reductions both make fundamental algorithms powerful software engineering tools, and provide theoretical tools for describing problem complexity.
The primary objectives of this course are:
Fundamentals: You will be familiar with a variety of fundamental algorithms and be able to identify when a new problem can be reduced to a known, solved, problem. You will be able to write a program implementing that reduction and solution.
Design: You will be able to design new algorithms to solve new problems, leveraging algorithmic tools like divide-and-conquer, dynamic programming, greedy solutions, backtracking, branch-and-bound, and pruning.
Analysis: You will be able to mathematically analyze the correctness and worst-case complexity of an algorithm: while formal proofs are not emphasized, rigorous mathematical reasoning is expected. Just as importantly, you will understand when problems are intractable, the importance of heuristic solutions.
Implementation: You will be able to implement complex, high-level, algorithms in practical code. Further, you will understand the trade-off between simplicity and optimality in software engineering.
Communication: You will be able to communicate with peers about problems, reductions, algorithms, complexity, and correctness both while solving problems, and while presenting solutions.
This course meets two times a week, and is structured around in-class activities, written assignments, and programming projects. Some assignments and projects will be individual, some will allow work in pairs.
Class Activities: Many classes will contain at least one problem, and some days will be devoted to longer activities.
Written Assignments: Written assignments will focus on analyzing the correctness and complexity of existing algorithms, and devising algorithms for new problems. Written assignments are submitted at the beginning of class.
Programming Assignments: Programming assignments will involve implementing known algorithms, as well as handling the reductions between problems that makes algorithmic knowledge so useful. Programming assignments are submitted through Github Classroom,
The course will have four modules: recursive algorithms, dynamic programming, graph and tree algorithm, and algorithms for weighted graphs. Each module will have the following rough structure:
Failure: We will examine canonical problems in a new domain and devise naïve solutions to these problems. We will then analyze these solutions to identify their limitations in correctness or complexity. Usually accompanied by an individual written assignment.
Insight: We will study solutions to the problem that utilize a new insight to improve on the correctness or complexity. Usually accompanied by an individual programming assignment.
Context: We will study closely related problems and devise solutions. Some will be directly reducible to the known solutions, some will require minor variations. Usually accompanied by a pair programming assignment.
Design: We will examine seemingly unrelated problems and design algorithms that use the same insight or techniques. Usually accompanied by a pair written assignment.
Extra class periods, for instance directly before an examination or a break, will be spent reflecting on previous modules through the lenses of complexity, hardness, tractability, and practicality.
Assessment is broken down into the following categories.
Class participation accounts for 10% of the course grade. This includes attendance, participation during discussions and unassessed class activities, and assessed class activities.
The written and programming assignments will be worth 50% of the course grade. This includes both individual and pair assignments
There will be a single out-of-class midterm and a cumulative final examination, which combined are worth 40% of the final grade.
The following grade cutoffs apply for this course. Grading will be stringent to reflect these cutoffs.
Students are expected by abide the Trinity University Honor code. Students must complete individual assignments individually. For assignments that allow pair work, students may complete and submit a single assignment as a pair. In both cases collaboration between individuals (resp. pairs) is explicitly allowed, but all code and text must be written alone (resp. in pairs). Students may look at each other's code and text for peer debugging and review, but should take care not to copy any code or writing directly.
Students are expected to attend all regular classes. Students who will miss class should notify me by email before their absence. Under the COSB, absences for religious observations and University-sponsored activates are fully excused. For the duration of the COVID-19 pandemic, students who are ill will be fully excused from classes.
In line with the Trinity University policy on equal access and equal opportunity, this course will be made accessible to all students. Any student who feels they may need accommodations based on the impact of a disability or long illness should contact me and the office of Student Accessibility Services to discuss your specific needs.
Please be aware that all classroom instruction, including student participation in classroom activities, is subject to recording and dissemination on secure University systems. The recordings will be made available only to students enrolled in the course to facilitate online learning and review. Students are expressly prohibited from capturing or copying classroom recordings by any means; violations will be subject to disciplinary action. Instructors who wish to use a recording outside of class must obtain the written consent of any students who are personally identifiable in the recording.