MWF 10:10am - 11:00am (A3)
MC Reynolds 314
Dr. Brent Yorgey yorgey@hendrix.edu (501) 450-1377 Office Hours
Introduction to standard algorithms and algorithm design strategies, with an emphasis on constructing rigorous formal proofs of algorithm correctness and performance, as well as translating fluently between theory and practice. Strategies discussed include brute-force, greedy algorithms, divide and conquer, dynamic programming, amortization, and problem reduction. The course includes an introduction to complexity theory and the complexity classes P and NP. Prerequisites: CSCI 151 and MATH 240.
Upon completing this course, you will be able to:
Algorithm Design
VisuAlgo
Lecture notes
Below is a unified calendar for the semester showing the topic and mode for each class meeting, as well as assignment due dates. Some specifics may change as the semester progresses, but the calendar will be kept up-to-date.
In this course, you determine your own final grade: you will prepare and submit for my approval a grading contract explaining your chosen final grade and what you will do to achieve it. You will then earn your chosen final grade by fulfilling the agreed-upon contract.
This may be different than what you are used to. Professor Cathy Davidson of CUNY perfectly sums up the reasons for doing things this way:
The advantage of contract grading is that you, the student, decide how much work you wish to do this semester; if you complete that work on time and satisfactorily, you will receive the grade for which you contracted. This means planning ahead, thinking about all of your obligations and responsibilities this semester and also determining what grade you want or need in this course. The advantage of contract grading to the professor is no whining, no special pleading, on the student’s part. If you complete the work you contracted for, you get the grade. Done. I respect the student who only needs a C, who has other obligations that preclude doing all of the requirements to earn an A in the course, and who contracts for the C and carries out the contract perfectly.
There is no specific format required for a grading contract, but it must have the following components:
Your desired course grade. You may choose to contract for an A, B, or C (if you’re wondering about D’s and F’s, see below). Note that your grading contract should not explain the reasons for your choice. I will not judge you because of your choice, and you do not need to justify it: there are as many different valid reasons for choosing to work toward a particular final grade as there are students. If you do wish to explain to me the reasons for your choice—which you are in no way required to do—you may do so in an email, a personal conversation, etc., but it should not go in your contract.
A description of the work and requirements you will complete, in checklist format. It doesn’t have to be super detailed, but you do have to explicitly include everything. For example, you can’t just say “I will complete all the assignments listed in the syllabus”; you must actually list them. This is so that you and I both know that you are explicitly aware of the requirements, and to help you keep track of what you have completed and what you have yet to complete. You also have some choice in terms of which assignments you complete, so you must record your choice in the contract.
Note that at the beginning of the semester you may not have a very good idea about this. For example, if you need to complete eight homework assignments, it’s not reasonable to insist that you know which specific assignments you plan to complete. However, you can refine your contract over the course of the semester. You just have to put something to start; for example, a reasonable default would be to plan to complete the first eight homeworks assigned.
For example, a grading contract might look like this:
My desired course grade in Algorithms is a C. To achieve this grade, I will complete the following:
The above example grading contract is incomplete since it is missing at least one requirement for a C. Read the rest of the syllabus to figure out what it is.
You must turn in an initial proposed grading contract by Friday, August 30. After the initial submission, I may require some revisions before I approve your contract.
Two times during the semester (Monday, September 30 and Monday, November 4) you are required to reflect on your progress in the course and complete an evaluation of your work, comparing it against what you agreed to in your grading contract. Your evaluation should:
Contain a copy of your original grading contract, with items you have completed checked off.
Revise your grading contract with more specific details as appropriate, for example, regarding which modules you intend to complete.
Include a 1-2 paragraph reflection, which answers questions such as the following (you do not necessarily need to answer every single question):
Your evaluation is also an opportunity to request an adjustment to your contract in either direction. If you find that you will be unable to meet the obligations of your contract, you may request to move to a lower grade and its requirements. Contrariwise, if you find that you’ve been performing above the obligations of your contract, you may request to fulfill the requirements for a higher grade.
Note, however, that you don’t have to wait for an evaluation to adjust your contract. If your life has really gone off the rails (or if, say, you are finding the class easier and more enjoyable than you thought!) just come and talk to me about adjusting your contract.
To “complete” an assignment means to complete it at or above the required criteria for receiving credit. For example, “complete a midterm exam” means not just taking the exam, but scoring sufficiently high on the problems so as to receive credit (possibly after retaking it).
[Adapted from Cathy Davidson.] You cannot intentionally contract for a grade of D (and certainly not for an F). However, I reserve the right to award a grade of D or F to anyone who fails to meet their contractual obligations in a systematic way. A “D” grade denotes some minimal fulfilling of the contract; an “F” denotes absence of enough satisfactory work, as contracted, to warrant passing of the course. Both a “D” and “F” denote a breakdown of the contractual relationship.
Midterm grades will be assigned according to the following specification:
The core of your learning in this class will take place through weekly problem sets, typically due at 5pm on Fridays. The table below lists the assignments and their due dates, along with the expected amount of time to complete each assignment (based on average self-reported times from students in past iterations of the course).
Each solution on a problem set or exam will be marked on the following scale:
In addition to the mark, feedback will be provided explaining how you can improve (with the only exception that feedback may not always be provided for solutions marked “E”).
To get credit for a problem set as a whole, you must:
If you do not get credit for a problem set, you may revise it; see the resubmission policy below.
Homework assignments must be turned in electronically, in PDF format, via the submission form. You have several options:
Many of the assignments are gratefully based on materials from Brent Heeringa.
There will be two midterm exams and a cumulative final exam. Each exam will be distributed one week ahead of its administration date. Once you receive the exam, you may:
On the exam administration date, you will take the exam during class, with no external resources allowed; you must recreate your solutions from memory. Thorough understanding of the solutions, rather than memorization, will be the best strategy for ensuring success.
Exam problems will be marked in the same manner as homework problems. To receive credit for an exam, you must receive a mark of ‘S’ or better on all exam problems. (Note that unlike problem sets, it is not necessary to receive a mark of ‘E’ on any problems.)
If you do not receive credit for an exam, you may retake it; see the resubmission policy below.
Weekly problem sets may be turned in late by spending two tokens.
Exams, on the other hand, must be taken on the scheduled day, unless you have made other arrangements with me (e.g. if you will be travelling for sports on the scheduled day).
Once a graded problem set is returned to you, you may submit a revised version, if you wish; submitting a revised version costs one token.
Midterm exams may be retaken, for 2 tokens, at a mutually agreed time. At Dr. Yorgey’s discretion, the retaken exam may include one or more problems which are different than (but still similar to) the problems from the original exam. In such a case you will still be given the new problems in advance, just as with the original exam.
When retaking an exam, you do not need to rewrite solutions to problems on which you already received a mark of ‘S’ or ‘E’.
It is not possible to retake the final exam.
Each student may have banked any number of virtual tokens which they can spend however they wish. Each student starts the semester with 5 tokens, which are non-transferable.
Conversely, additional tokens may be earned at any time:
Completing any of the Kattis problems listed above earns a number of tokens equal to half the difficulty score of the problem, rounded up. For example, solving a problem with a difficulty rating of 2.3 earns 2 tokens; solving a problem with a difficulty rating of 5.0 earns 3 tokens.
To get credit for completing a Kattis problem, submit your code along with a screenshot showing that your submission was accepted by Kattis.
Although you and I play different roles in the course, we both have your learning as a common goal. There are things I expect from you as a student in the course, but there are also things you can expect of me as the course instructor and facilitator.
If I am not fulfilling my responsibilities outlined below, you are welcome (and encouraged!) to discuss it with me.. I will also initiate a conversation if you are not fulfilling yours. However, none of us will meet all of the expectations perfectly—me included!—so it’s also important that we have grace and patience with one another.
Attending class and being an active participant in the class community is one of the most important contributors to your learning. Attendance is especially important in this class since you will often engage in group learning activities.
Discussion and collaboration on the problem sets is encouraged. However, solutions must be written up individually. Copying another student’s writeup, in whole or in part, or directly collaborating on a writeup, will be considered an academic integrity violation. Insightful discussion with others must be cited in your homework solutions. You will not lose credit for such citations.
In this class you may use generative AI (with appropriate citation if you use any AI output as part of your homework submissions). However, note that it may not help you very much on written assignments. I administered the final exam to ChatGPT and it failed miserably.
Hendrix College is committed to high standards of honesty and fairness in academic pursuits. Such standards are central to the process of intellectual inquiry, the development of character, and the preservation of the integrity of the community. Please familiarize yourself with the statement of Academic Integrity.
You should also familiarize yourself with the Computer Science-specific Academic Integrity Policy.
If you have a documented disability or some other reason that you cannot meet the above expectations, and/or your learning would be best served by a modification to the usual course policies, I would be happy to work with you—please get in touch (via Teams or email)! The course policies are just a means to an end; I don’t care about the policies per se but I do care about you and your learning.
It is the policy of Hendrix College to accommodate students with disabilities, pursuant to federal and state law. Students should contact Julie Brown in the Office of Academic Success (505.2954; brownj@hendrix.edu) to begin the accommodation process. Any student seeking accommodation in relation to a recognized disability should inform the instructor at the beginning of the course.
Hendrix College values a diverse learning environment as outlined in the College’s Statement on Diversity. All members of this community are expected to contribute to a respectful, welcoming, and inclusive environment for every other member of the community. If you believe you have been the subject of discrimination, please contact the Dean of Students Office (Donna Eddleman, Eddleman@hendrix.edu, 501-450-1222) or the Title IX Coordinator (JenniferFulbrighttitleix@hendrix.edu, 501-505-2901). If you have ideas for improving the inclusivity of the classroom experience, please feel free to contact me. For more information on Hendrix non-discrimination policies, visit hendrix.edu/nondiscrimination.
Hendrix recognizes that many students face mental and/or physical health challenges. If your health status will impact attendance or assignments, please communicate with me as soon as possible. If you would like to implement academic accommodations, contact Julie Brown in the office of Academic Success (brownj@hendrix.edu). To maintain optimal health, please make use of free campus resources like the Hendrix Medical Clinic or Counseling Services (501.450.1448). Your health is important, and I care more about your health and well-being than I do about this class!