Generally, the best way to reach me is via email.
TAs:
Rohaan Khalid rkhalid@knox.edu,
Office hours: Friday 4-6pm in the SMC library
In this class, we focus on designing and analyzing data structures and algorithms. You will further develop your skills creating mathematical descriptions of "real world" computational problems. We will examine a variety of problems to illustrate important general techniques like divide and conquer, dynamic programming, graphs, greed, amortized analysis, and network flow. For all these techniques, you will learn how to formally prove algorithm correctness so you can be confident about the solutions. We also look at formal ways to identify "hard" problems, illuminating the limitations of computing and providing you with a way to know that a particular algorithm cannot be further improved.
Our scheduled class time is Monday, Wednesday, Thursday, and Friday during 5th period (1:20-2:30). The class meets in SMC A-204.
There will not be class on 10/3 or 10/21 so that you can work on exams.
Our textbook is "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein (4th edition). We will also be covering some material from the following:
In addition to the course webpage, we'll also use Google Classroom. I've invited everyone who is registered for the class; be sure to join ASAP so that you don't miss announcements.
In order to prepare to fully participate in class, you will be required to read before many class meetings. See the "required reading" column on the Lectures page.
Expect to work for this class. This is one of three classes that make up a full-time schedule so you should spend ~13 1/3 hours/week on it.
The best way to spend your time on the course is to practice. While I believe that reading the text is important for your success, extra study time should be more than reading it again. Instead, try to work the problems from class or some extra problems from the text. Alternately, you can try to rederive some of the results they present without referring to their presentation. You will learn better by trying to apply the techniques yourself rather than simply watching the authors (or me) apply them.
In addition, be sure to come to class, participate actively, and TAKE NOTES. A fair amount of the material is from the book, plus I'll be posting my slides, but studies have shown that the act of writing notes helps students to digest the material and learn it.
If you find yourself struggling in this course, get help right away. The term will move quickly and concepts in this course build on one another so you can't afford to get too far behind. Don't hesitate to come by my office or email me a question.
Week 1: Array ADT. Balanced trees (AVL trees). Induction review. Asymptotic notation.
Week 2: Divide and conquer algorithms. Solving recurrences.
Week 3: Multithreaded algorithms.
Week 4: Dynamic programming. Exam 1
Weeks 5 and 6: Graphs. Graph problems: traversals, MST, and shortest paths.
Week 7: Network flow. Exam 2
Week 8: Greedy algorithms. Amortized analysis. Union-find.
Weeks 9 and 10: Lower bounds. NP-completeness. Online algorithms. Approximation algorithm.
Practicing by working on assignments is a key part of learning the material in this course. This class will have the following types of assignments:
Due dates for reading quizzes are strictly enforced since the main goal of these assignments is to prepare you for class.
No work can be accepted after the end of finals, which is when our final will be due. Thus, its due date is also firm.
Homeworks and the exams other than the final will be due at midnight. Everyone has an automatic extension for 8 hours (i.e. until 8am the next morning). Exams cannot be submitted after that point. I may release homework solutions or discuss them in class at any time after the automatic extension. If I do so, those problems cannot be submitted afterwards. Otherwise, homework submitted up to 24 hours after the automatic extension incurs a 10% penalty and work submitted after that incurs a 20% penalty.
To account for normal things that happen during a term, you get two "late days" that may be used to reduce the late penalties on homework assignments during the term. (Note that late days CANNOT be used for exams or reading quizzes.) Each allows you to reduce the late penalty on an assignment by 10%. They can be used for the same assignment (completely removing the penalty on that assignment) or different assignments (reducing the penalty by 10% on each).
Individual extensions beyond the automatic extensions and these two late days may be granted, but require extraordinary circumstances.
I assign extra credit problems infrequently, but I will give extra credit for attending colloquium talks sponsored by the CS department (possibly other departments, depending on the talk) and submitting a short writeup about the talk. This offer applies to any qualifying talk for which you are not otherwise getting credit; you should not submit a writeup to me and also for another class. I will announce the talks that count for my class, though you may suggest possible talks if you think I'm missing one.
In order to get credit for a talk, submit a quick writeup (~1 page) to me within a week or so of the talk (slight extensions possible, but you need to remember the talk...). DO NOT just summarize the talk; I want to hear what you thought about it or how it relates to other things you've seen/heard. While your writeup doesn't have to be brilliant prose, I do expect you to write thoughtfully and correctly and I may return your writeup for revisions before giving you credit.
Reading questions and exams in this class must be completed individually. Many of the in-class activities will be completed collaboratively in small groups. The homeworks fall between these extreme cases. You are allowed to talk with your classmates about the concepts involved in the homework, but each student is expected to write up their solution on their own. When you do this, however, you must do two things:
The same policies apply to getting help from inanimate sources, including AI systems. If you use such a source other than our textbook or other course materials, you must cite this source. As in collaborations with another person, you are expected to write your own solution; do not copy text or code from any source. In general, you may look at other sources for examples or conceptual help, but not actual solutions. Some problems assigned for this class may have been previously assigned to other classes, but you are expected not to deliberately seek solutions. (If you come across one accidently, let me know and I may give you a modified assignment.)
Please feel free to contact me if you have any questions about this policy.
Students who qualify for accommodations in this class are encouraged to contact Stephanie Grimes (sgrimes@knox.edu) in the Office of Disability Support Services as soon as possible to ensure that such accommodations are implemented in a timely fashion.
At the end of the term, all of your work will combined into an overall course percentage based on the following weights:
| Reading quizzes | 5% |
| Clicker questions | 10% |
| Homework | 35% |
| Exam 1 | 15% |
| Exam 2 | 15% |
| Final | 20% |
The range of scores mapping to each grade will be determined at the end of the term based on the "standard" 90/80/70/60, but perhaps being more generous based on the difficulty of the assignments. In general, spend your time learning the material rather than worrying about your grade, but feel free to talk with me if you are concerned about it.