This syllabus is subject to change based on specific class needs, especially the schedule. Significant deviations will be discussed in class. Individual exceptions to the policies and schedule are granted only in cases of true emergency. Please make arrangements with me if an emergency arises.
The study of algorithms is one of the most crucial areas of in Computer Science. In this course, students will learn the basic tools of algorithm design and analysis through the study of some of the most well known and important algorithms. By the end of the semester, students will have developed not only a firm grounding in the analysis and design of algorithms, but working knowledge of the algorithms that have made computing what it is today.
There are too many algorithms topics to cover fully in a one semester course. To compensate, students will complete an in-depth research project on an algorithms-related topic of their choice, providing not only further depth but also project management skills. While this class focuses mostly on the theoretical design and analysis of algorithms, students will have opportunities to implement algorithms in the language of their choice.
This course will emphasize the first 12 chapters of the main text (TADM) plus occasional material from other sources:
The required course textbook is:
We will occasionally pull material from other sources, especially for parallel algorithms. Any required readings will be posted on this webpage as needed.
I encourage you to take advantage of the wealth of algorithms study resources that can be found online. This material can be difficult; exposure to multiple sources is always useful and sometimes necessary to fully grasp it. I will list here some resources that may be useful (and fun!). Please suggest links to add as you find them.
The weekly workload for this course will vary by student and over the semester, but on average should be about 13 hours per week. The follow table provides a rough estimate of the distribution of this time over different course components for a 16 week semester.
| Category | Amount | Final Grade Weight | Average Time/Week (Hours) |
|---|---|---|---|
| Lectures | 52 | 10% (Participation) | 3.33 |
| Problem Sets | 6–8 | 25% | 4.5 |
| Quizzes | 5–7 | 25% | - |
| Research Project | 1 | 20% | 1.5 |
| Exam/Quiz Study | - | - | 1.67 |
| Exams | 2 | 20% | - |
| Reading | - | - | 2 |
| 13 |
Generally problem sets and quizzes will alternate weeks. There will be a research project on any algorithms-related topic, culminating in a paper and presentation to the class. There are two exams – a midterm and a final – both worth 10% each. The final exam will focus primarily, but not exclusively, on material covered since the midterm. In other words, it will contain a few questions on material from the first half of the semester.
Your participation grade is based on a variety of activities. During class I will often make use of the Socrative app, so you’ll need to install this on your phones. Participating in Socrative questions and with in-class group activities is required for a decent participation grade; an A includes asking questions either in class or in office hours.
Your final grade is based on a weighted average of particular assignment categories, with weights shown above. You can estimate your current grade based on your scores and these weights. You may always visit the instructor outside of class to discuss your current standing. Assignments and final grades use a standard grading scale shown below and will not be curved except in rare cases when deemed necessary by the instructor.
This courses uses a standard grading scale. Assignments and final grades will not be curved except in rare cases when its deemed necessary by the instructor. Percentage grades translate to letter grades as follows:
| Score | Grade |
|---|---|
| 94–100 | A |
| 90–93 | A- |
| 88–89 | B+ |
| 82–87 | B |
| 80–81 | B- |
| 78–79 | C+ |
| 72–77 | C |
| 70–71 | C- |
| 68–69 | D+ |
| 62–67 | D |
| 60–61 | D- |
| 0–59 | F |
You are always welcome to challenge a grade that you feel is unfair or calculated incorrectly. Mistakes made in your favor will never be corrected to lower your grade. Mistakes made not in your favor will be corrected. Basically, after the initial grading your score can only go up as the result of a challenge*.
You are always welcome to challenge a grade that you feel is unfair or calculated incorrectly. Mistakes made in your favor will never be corrected to lower your grade. Mistakes made not in your favor will be corrected. Basically, after the initial grading your score can only go up as the result of a challenge.
Late assignments: You have each been allotted a total of 5 late days. You may apply these to any homework or programming assignment (NOT exams, labs, or reading assignments) you see fit and turn in your solutions with no penalty. Each late days gives you exactly 24 extra hours from the original due date and time. However, you may use at most 2 late days on any individual assignment. The whole point here is to give you some flexibility that allows for things like illnesses, long trips, and the like. I am unlikely to grant further extensions. You must notify me if you will use late days, and how many, BEFORE the assignment is due. Late assignments (beyond any applied late days) will be subject to a grade reduction at my discretion. While you should expect a reasonable penalty for late work, know that I will NEVER give you a 0 for late work as long as it is turned in before the final exam.
Academic dishonesty: Monmouth College’s official policy on academic dishonesty can be found here. You are responsible for reading and complying with that policy.
In this course, any violation of the academic honesty policy will have varying consequences depending on the severity of the infraction as judged by the instructor. Minimally, a violation will result in an “F” or 0 points on the assignment in question. Additionally, the student’s course grade may be lowered by one letter grade. In severe cases, the student will be assigned a course grade of “F” and dismissed from the class. All cases of academic dishonesty must be reported to the Associate Dean who may decide to recommend further action to the Admissions and Academic Status Committee, including suspension or dismissal. It is assumed that students will educate themselves regarding what is considered to be academic dishonesty, so excuses or claims of ignorance will not mitigate the consequences of any violations
Collaboration: We encourage you to make use of the resources available to you – it is fine to seek help from a friend, tutor, instructor, internet, etc. However, copying of answers and any act worth of the label “cheating” is never permissible! In addition to listing your sources and collaborators, you should be producing your own writeup in your own words. By “your own words,” we mean you should be producing the text yourself, without some external aid. Verbatim copying of text is specifically disallowed, but so is taking a source and rearranging some phrases and changing some variable names to create a derivative version! Such behavior is definitely NOT “using your own words.” It does not matter if you helped contribute to this source text with others, since then you are still not the sole author of the text. The point of collaborating on an assignment is not to produce a jointly authored set of solutions, since that violates the course policies. Instead, it is to help you solve the problems, which sometimes involve a bit of creativity. After you have jointly come up with the ideas you need to solve the problems, though, you should part ways with your group and sit down to do the writing by yourself. I also advise against sharing the writeup you submit with others, since if someone else uses your text as a source for their own solution (with or without your permission), you will also be implicated in the violation of the academic integrity policy. In any case, if two nearly identical solutions are received, we have no way of tell which is the original, and the policy is to not award credit for either submission.
Electronic devices: Do not use your phone or other devices in class except where necessary. Any computer or tablet usage should be related to the course. If a device is not being used for Zoom or Socrative it should be put away and turned on silent. Other usage is rude and distracting to others.
General expectations: In short, I expect you to be respectful of others and take responsibility for your own learning. You are here to learn, so work hard and be professional.
Just attending class is not sufficient to truly learn the material. Read the text, use the resources available at Monmouth College, and go beyond the material.
If you miss class, you are responsible for everything covered on that day. College is, in some sense, your job. Take pride in creating quality work. Staple your assignments, label problems, and present your answers neatly and orderly.
Your job is to convince me that you have learned the material – show your work! Even if you do not know a particular answer, guide me through your thought process.
The following tentative calendar should give you a feel for how work is distributed throughout the semester. Readings are are listed when they are due. This calendar is subject to change based on the circumstances of the course.
Unless otherwise specified, the readings come from TADM.
| Date | Topic | Assignment and Readings |
|---|---|---|
| Wed 01/17 (Week 1) | Intro to Algorithm Design | |
| Fri 01/19 | Interval Scheduling, Correctness | 1.1-1.3, PS01 out |
| Mon 01/22 (Week 2) | Proof Exercises | 1.4-1.9 |
| Wed 01/24 | Big-O/Complexity Review | 2.1-2.4 |
| Fri 01/26 | Analysis Examples | 2.5-2.6, Quiz 01 |
| Mon 01/29 (Week 3) | PS01 Questions | 2.7-2.9 |
| Wed 01/31 | Basic Data Structures, Dynamic Array | 3.1-3.2 |
| Fri 02/02 | PS01 Questions | PS02 |
| Mon 02/05 (Week 4) | Dictionaries | 3.3 |
| Wed 02/07 | Trees, (Balanced) BSTs | 3.4 |
| Fri 02/09 | Priority Queues, Heaps, Heapsort | 3.5-3.6, 4.3, Quiz 02 |
| Mon 02/12 (Week 5) | Hashing | 3.7-3.9 |
| Wed 02/14 | Sorting, Mergesort (idea) | 4.1-4.3 |
| Fri 02/16 | PS02 Questions, Mergesort (analysis) | 4.4-4.5, PS03 |
| Mon 02/19 (Week 6) | Quicksort Code/Analysis, Quickselect | 4.6-4.8 |
| Wed 02/21 | Binary search | 5.1-5.2 |
| Fri 02/23 | Recurrence Relations | 5.3-5.4, Quiz 03 |
| Mon 02/26 (Week 7) | Review Master Theorem, D&C Examples I: MCSS | 5.5-5.6 |
| Wed 02/28 | D&C: Closest Pair, Parallel Algorithms I | 5.7-5.8 |
| Fri 03/01 | Parallel Algorithms II: Scheduling, Reduction | Project |
| Mon 03/04 (Week 8) | Parallel Algorithms III: Parallel Mergesort | |
| Wed 03/06 | Midterm Review | |
| Fri 03/08 | Midterm | |
| (Mon 03/11 – Fri 03/15) | (Spring Break) | |
| Mon 03/18 (Week 9) | Midterm Solutions | |
| Wed 03/20 | Problem Set Review | |
| Fri 03/22 | Probability, Hashing Details | 6.1-6.3, PS04 |
| Mon 03/25 (Week 10) | Bloom Filters, Perfect Hashing | 6.4-6.5 |
| Wed 03/27 | Graphs | 7.1-7.4, Quiz 04 |
| (Fri 03/29) | (Easter Break) | |
| (Mon 04/01) (Week 11) | (Easter Break) | |
| Wed 04/03 | Graph Traversal, BFS | 7.5-7.7 |
| Fri 04/05 | DFS | 7.8-7.10, PS05 |
| Mon 04/08 (Week 12) | Applications of DFS on Directed Graphs | |
| Wed 04/10 | MSTs | 8.1-8.2 |
| Fri 04/12 | Union-Find, Shortest Paths | 8.3-8.4, Quiz 05 |
| Mon 04/15 (Week 13) | Dijkstra’s, Floyd-Warshall | |
| Wed 04/17 | Network Flows, Min-Cut | 8.5-8.7 |
| Fri 04/19 | Backtracking | 9.1-9.3 |
| Mon 04/22 (Week 14) | Intro to Dynamic Programming | 10.1, PS06 |
| Wed 04/24 | Edit Distance | 10.2 |
| Fri 04/26 | (No class, watch More Dynamic Programmming) | 10.3-10.4 |
| Mon 04/29 (Week 15) | Reductions | 11.1-1.2, Quiz 06 |
| Wed 05/01 | Satisfiability | 11.3-11.4 |
| Fri 05/03 | More Reductions, P vs. NP | 11.5-11.6, 11.9 |
| Mon 05/06 (Week 16) | Presentations | |
| Wed 05/08 | Final Review | |
| Sat 05/11 3:00 PM–6:00 PM | Final Exam |
The Academic Support and Accessibility Services Office offers FREE resources to assist Monmouth College students with their academic success. Programs include supplemental instruction for difficult classes, drop-in and appointment tutoring, and individual academic coaching. The office is here to help students excel academically, since everyone can work toward better grades, practice stronger study skills, and mange their time better. Please email academicsupport@monmouthcollege.edu for assistance.
If you need course adaptions or accommodations because of a disability please make an appointment with me and/or with the Accessibility Services Office (ASO) (access@monmouthcollege.edu 309-457-2257) as soon as possible. The accessibility of this course for every learner is important to me. If at any time you experience a barrier to learning, please bring it to my attention and I will do my best to address it.
Wellness on Campus: The College wants to support all aspects of your life on campus, including mental and physical health. We offer a health clinic in the lower level of McMichael Residence Hall (open M-F, 9am-1pm): healthcenter@monmouthcollege.edu, 309-536-6055. Mental healthcare will be available from anywhere through online provider TimelyCare. Services include emergency “Talk Now,” counseling sessions, health coaching, medical services, psychiatry, prescriptions, digital self-care, and a peer community. If you would like to be connected to additional local resources, please contact Dean Michelle Merritt at mmerritt@monmouthcollge.edu.
Always, students facing a crisis should contact Campus Safety at 309-457-3456 or the Police at 911. Suicide resources are The National Suicide Prevention Hotline at 1-800-273-TALK, and the local Bridgeway Crisis Hotline at 800-322-7143. For more information, visit our website https://www.monmouthcollege.edu/offices/health-wellness/.