Note: This syllabus may be modified as the course progresses. Notice of such changes will be announced in class.
Welcome to Grinnell’s Spring 2020 CSC 301 – Analysis of Algorithms. CSC 301 is the department’s advanced course in algorithms and is a successor to CSC 207 – Algorithms and Object-Oriented Design. In this course, we will develop your skills in the design, implementation, analysis, and verification of algorithms. We will also explore advanced abstract data types and data structures. Along the way, we will consider a variety of classic algorithms, ADTs, and data structures – the “literature” of CS, as it were. Why do we read the literature? Because knowing how problems have been solved in the past helps us solve future problems.
Office: Noyce 3809
Monday, Wednesday, and Fridays: 9am – 10am
Thursdays: 9am – 11am
You can schedule office hours with me through this link. Booking an appointment is not mandatory, but may be helpful during busier parts of the semester.
If none of my office hours work for you, please send me an email to schedule another time to meet.
The best way to contact me is through email. I will do my best to respond in a timely manner, but note that I have other obligations in the evenings and on the weekends, that may mean I don’t respond immediately.
Section 01: 8:00-8:50 MWF, Room Noyce 3819
Section 02: 1:00-1:50 MWF, Room Noyce 3819
Office hours: TBD
Office Hours: TBD
We will use:
Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., and Stein, Clifford (2009). Introduction to Algorithms, 3rd Edition. MIT Press.
Please explore around for a copy that you can afford. The computer science department keeps textbook copies that anyone can use. The general policy is that these books should stay on the 3rd floor of Noyce. However, for this text we have a number of additional copies that some students may “check-out” for the full semester. If you are interested in doing this please let me know. There are also a couple of online copies available at the Grinnell College Library, but as a professional computer scientist, you will likely want to own this book.
CSC-207 and either MAT-218 or CSC/MAT-208
CSC 301 has these high-level goals:
- to gain proficiency in the use of a variety of strategies for algorithm development
- to understand and apply fundamental algorithms to a range of problems
- to learn representative algorithms that are largely independent of data structures, algorithms that support abstract data types and data structures, and algorithms that utilize their own data structures for record keeping
- to learn techniques for analyzing algorithms, such as instruction counts, recurrence relations, probability theory
- to understand and apply methods for showing the correctness of algorithms to solve sample problems
By the end of the semester, students should have the following capabilities:
- Students should be able to identify and explain several strategies for algorithm development and provide at least one example illustrating each strategy.
- Students should be able to explain, implement, and analyze fundamental algorithms from several application domains, such as trees, graphs, strings, and dictionaries.
- When several different algorithms are available for a task, students should be able to apply careful analysis to determine conditions under which one algorithm is better or worse than another.
- Since algorithms are normally designed to help solve problems, students should be able to provide formal arguments establishing that proposed algorithms meet their respective specifications.
It is my intention that students from all backgrounds and perspectives will be well served by this course, and that the diversity that students bring to this class will be viewed as an asset. I welcome individuals of all ages, backgrounds, beliefs, ethnicities, genders, gender identities, gender expressions, national origins, religious affiliations, sexual orientations, socioeconomic background, family education level, ability – and other visible and nonvisible differences. All members of this class are expected to contribute to a respectful, welcoming and inclusive environment for every other member of the class. Your suggestions are encouraged and appreciated.
My goal is to help you learn as much as possible in this course; please let me know what I can do meet your learning needs. If you have a disability that requires accommodations, please contact Disability Services. Disability Resources will work with you to determine your needs, and will provide you with paperwork outlining the accommodations you require. Please give me this paperwork at least a week before the course activity for which you need accommodations. If this timeline is not feasible for any reason, please contact me as soon as possible and we will work together to find a solution.
Attendance at all class sessions is expected. Please let the instructor know in advance of planned absences. Attendance will be taken daily, and regularly missing class could lead to a discretionary reduction in grade.
Collaboration and Academic Honesty
As students, you are members of the academic community. Both the College and I expect the highest standards of academic honesty, as explained in the Grinnell College Student Handbook. Among other things, this means clearly distinguishing between work that is your own, and work that should be attributed to others. This includes ideas, examples, and code that you draw from labs and readings.
You are allowed to use outside resources (e.g. the web) in this course, but under this caveat: You may search for resources on general topics we are studying, but not specific problems. There are many solutions on the web to problems you will see in this class. Sometimes the solutions are not detailed enough, or downright wrong. Beyond that, it is much more beneficial to your learning to develop a solution on your own. Remember that I (your instructor) and your mentor are available to help steer you towards a solution. Note that even re-wording a solution you find online violates this policy.
Computer Science is more fun when learning with your peers, therefore in most cases I encourage you to collaborate with them. Specific notice will be given if collaboration is not allowed. However, you must follow these rules for citing where you received help:
- You must cite statements in the textbook, websites where you find material, etc. Include any information which will help me find the reference.
- If you talk to someone else about an individual problem, then the assistance should be cited at the end of the problem. For example: “I talked about the solution to this problem with ….”. This includes classmates, mentors, and anyone else besides your instructor.
- Any program results or output must be faithfully recorded, not forged. (A thoughtful explanation of unexpected behavior can often be a worthwhile submission and is much better than the alternative.)
- You are responsible for safeguarding your work from being copied by others. This requires you to take reasonable precautions with hard copy printouts as well as file system permissions. (Note that MathLAN’s default permissions prevent others from viewing your files.)
As an instructor, I will meet my obligation to bring any work suspected to be in violation of the College’s Academic Honesty Policy to the attention of the Committee on Academic Standing, after which I no longer have authority over the matter.
There will be 2 oral midterm exams plus an oral final exam. CSC-301 is a great opportunity to practice for internship/job or graduate school interviews. I know that oral exams can induce a lot of anxiety – I can relate! I will do my best to make them as painless as possible.
Exams will be 20-30 minutes in length. A list of possible problems will be distributed before each exam. Actual exam questions may be tweaked slightly from the list. Upon arriving to the exam, you will draw one of the problems and present the solution on the board. You are expected to talk through your solution to me as you present. You may ask for hints for a reduction in your exam grade.
If you anticipate not being able to make an exam appointment, you must contact the instructor as soon as possible – at least 24 hours before the scheduled exam. Rescheduling exams because of illness will require an excuse from a doctor. Rescheduling of exams due to lack of preparedness will not be allowed. Of course, if you have any reason to miss an exam that the college would constitute an emergency, I will work with you to reschedule at a later time.
Exams will take place during the weeks of March 2, April 13, and May 11 (Finals week).
There will be 7 assignments total. Assignments will be handed out in class, and collected in class. Assignments will be mostly proofs with occasional coding. Late work will not be accepted unless an arrangement has been made with me 72 hours before the due date.
After each assignment is turned in, 2-3 students will present solutions to select problems. Each student will present one time during the semester, which will be assigned at the beginning of the semester. The presentation of solutions will count as an 8th assignment towards your grade. Correct, rigorous, and clean solutions will be expected, which means you will need to come discuss your solution with me before class. Assignment details and grading rubric can be found here.
On most days, you will need to complete a reading before arriving to class. Furthermore, there will be a reading guide on Pweb that needs to be turned in by 5pm the day before class. Completion of the readings will be crucial to your learning in the course, and will guide how we spend time in class. Failing to complete the reading with serious effort puts your learning at a significant disadvantage. The reading guides will be graded according to this rubric.
New policy as of 1/29/20: You will be allowed 5 late reading question submissions without penalty to your grade. You do not need to do anything, such as notifying me, about your late submission. At the end of the semester I will look through all reading question submissions and update your grade.
Much of our work in this course will depend on discussion and collaboration in class. Participation involves:
- Arriving on time to class
- Coming to class prepared
- Asking questions when appropriate
- Making positive contributions to class discussion when called upon
- Staying on task when working independently or with classmates
If you regularly meet this criteria, expect to earn an A- in participation. Students who go above and beyond with particularly insightful comments will earn a higher participation score. Students who arrive late to class, or who demonstrate a lack of preparedness can expect to receive a lower score.
Attendance: Penalty Only
Midterms: 40% (20% Each)
Responses to reading: 10%
Some of the content of this syllabus has been taken or adapted from other sources.
- The Inclusivity Statement is taken verbatim from LGBTQ+ Advocacy in STEM.
- Much of the wording from the sections on Participation, Collaboration and Academic Honesty, and Accommodations has been taken from the Grinnell CS 151 course syllabus, a version of which can be found here. The 151 materials have been developed by a number of current and past Grinnell Faculty and Staff including Charlie Curtsinger, Sarah Dahlby Albright, Janet Davis, Fahmida Hamid, Titus Klinge, Samuel A. Rebelsky, John David Stone, Anya Vostinar, Henry Walker, and Jerod Weinman.
- Furthermore, some of the sources of the 151 material can be traced back to Jerod Weinman’s academic honesty statements here and here, and Janet Davis’s Participation Statement here.