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
Problems
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.
A list of the dates you have scheduled for your interviews. Of course, you must actually schedule the meetings prior to turning in the grading contract!
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:
Warning: 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 the missing requirements are.
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 28 and Wednesday, 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.
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, due at 5pm on Fridays. Problems will be assigned daily, with each problem being worth some number of points (typically 1-3) depending on its difficulty. Each problem set will require a certain point total; you will select a portfolio of problems with at least the required total and submit your solutions all together. (You may split up a problem set into multiple submissions throughout the week, but I would prefer a single submission.)
Note that for a given problem set you may select any problems that you have not previously submitted; i.e. they do not have to be from the same week as the problem set is due. For example, if you get behind, it is up to you whether you select more recent problems to stay “up to date”, older problems to solidify your understanding of previous material, or some combination.
Homework assignments must be turned in electronically, in PDF format, via the submission form. You have several options:
Any problem set submission prior to a due date containing reasonable attempts at problems with at least the required point total will be counted as an on-time submission. A certain number of on-time submissions are required for various final grades, in addition to certain point totals.
There is no way to submit a problem set “late”. If you submit a problem set after a deadline, it will simply count as an on-time submission for the next deadline (assuming it has a sufficient point total; if not, you may submit additional problems before the deadline). Problem sets submitted after the final problem set deadline (December 4) will not count towards your on-time submission total, though they will still count towards your problem completion total.
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”).
If you do not get credit (S or E) for a problem, you may turn in a revised version within one week of receiving feedback. A problem may be revised as many times as necessary, as long as each revision is turned in within one week of receiving feedback on the previous submission.
If you do not revise a problem within one week, then you lose your chance to receive credit for that problem.
You may turn in problem revisions separately, or you may bundle them together with your next problem set submission. Note, however, that revised problems do not count towards the required point total for a problem set.
You will complete four interviews with me throughout the semester. Each interview is a one-on-one meeting with me in my office that you will schedule and attend.
Of course, you are welcome and encouraged to sign up for additional office hour meetings beyond the required interviews!
Each interview must be completed by the dates listed below; for example, the first interview must be completed by Friday, September 18.
As part of your grading contract, you will sign up in advance for interview times throughout the semester. However, I recognize that schedules can change. If you need to reschedule an interview, just let me know.
More details about interviews coming soon!
There will be three midterm exams. Each exam will be distributed at least 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.
If you do not receive credit for an exam, you may retake it at a mutually agreed time, possibly with different but similar questions (you will also be given the new problems in advance, just as with the original exam). Note that you only need to retake problems you did not receive credit for; you do not need to retake the entire exam.
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.
Generative AI/LLM use in this class is strictly prohibited and will be considered an academic integrity violation. This is for a number of reasons:
There is no credible evidence that even appropriate LLM use can enhance learning. To the contrary, there is plenty of evidence that they decrease learning, even for users who are trying to use them responsibly. LLMs promise decreased effort: use an LLM to do the low-level, tedious work so you can focus at a higher level. This is a seductive claim, but the problem is that learning requires effort! If learning is easy, then you are not really learning.
LLMs produce plausible text, without any notion of truth or correctness. No matter how “good” they are, there will always be a need for expert human review and judgment. The only way to acquire that expert judgment is to engage in the hard work of things yourself. Even if you end up using LLMs in a future career, you need to put in the effort now to become an expert capable of wielding them appropriately.
The use of LLMs to generate text that you then send to someone else is fundamentally disrespectful—it essentially trades your time for someone else’s, and hence sends the message that you value your own time more than theirs. A big part of my job is giving you feedback on things you submit (feedback loops are central to the process of learning!). Submitting work even partially generated by an LLM is therefore extremely rude, since it indicates that you do not value the time I spend in teaching you.
The resources needed to train and run LLMs are enormous. Of course, one person’s actions don’t make much difference on their own, but on principle, those who value sustainability should certainly think twice about LLM use. I could not in good conscience encourage you to use LLMs even if they were helpful for learning.
In case you are worried I am being hypocritical, I have made a personal commitment not to use LLMs at all. You may also be interested in reading these reflections I wrote for my students last year.
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.
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!