Syllabus
Contents
Imagine that you have been asked to solve a problem by writing a program. You come up with your solution, implement it, and cross your fingers while you execute the code. No errors print out, but it it also doesn't complete execution, even after a couple minutes! What could be going on? Your program might have an infinite loop or recursion or it might just need some more time running...
In this course, you will develop the language and skills required to design, analyze, and communicate precisely about computational problems and their solutions. An algorithm is a computational procedure that correctly solves a specific problem. Packed into that description is the following algorithm design process:
pose the problem rigorously (formulate a mathematically clean definition)
propose a solution as a procedure (described in a way that can be implemented within a specified computational model, e.g., a random-access machine)
prove that the procedure correctly solves the problem
analyze the procedure's running time
Each of these steps is done with a high-level description of the problem and algorithm, before writing a single line of code. The problems you will see often arise in real-world applications, and you'll discover that some are provably impossible to solve, while others are only known to have solutions that are computationally infeasible (running times that could take more than a lifetime)!
Topics
Algorithmic paradigms [common approaches for solving a problem]
greedy algorithms
divide and conquer
dynamic programming
network flow
Theory for computational infeasibility [intrinsic difficulty of a problem]
NP-completeness
computational intractability
Textbook
We will roughly cover material from Algorithm Design by Kleinberg and Tardos, though I will use supplementary material from other sources as well.
You may wish to refer to Introduction to Algorithms, Third Edition by Cormen, Leiserson, Rivest, & Stein for a concise presentation of the material. It's often referred to as CLRS.
Kleinberg and Tardos, Algorithm Design, Addison-Wesley, 2006
How
My goal is to create an inclusive learning environment that provides the structure and support to help you successfully understand the process of algorithm design. It is your responsibility to utilize the offered resources and undertake the work that optimizes your learning experience. By taking ownership, you will leave this course with tools that can assist in your academic and professional pathway. The grade breakdown is intended to strategically guide effective learning.
The course activities are structured to help you engage with the material:
Lectures & topic modules provide a different presentation of material that is in the textbook, helping to spark your curiosity in the problems, algorithms and analysis. For some topics, more dense content will be found in the topic module via video lectures. Embedded quizzes give you the chance to practice and confirm your initial understanding.
Worksheets provide a chance to practice the material more deeply as well as develop communication skills for technical content.
Articulation activities help you take ownership of your learning by asking you to reflect on a topic module and (optionally) lead a lesson for your peers. Precise articulation of the algorithm design process will improve through practice.
Homeworks provide an opportunity to engage with the material and the process of learning as well as receive feedback.
Quizzes and a self-scheduled final exam are intended to inspire you to acquire a deep understanding of the material.
Learning is a core commitment and the instructor, TAs, and students in CS 312 are expected to be respectful, inclusive of all students, and to not discriminate. Mount Holyoke resources on diversity, equity, and inclusion can be found here. Bias incidents can be reported here. Students are encouraged to bring concerns or feedback to the attention of the instructor.
Requirements
Topic modules with embedded quizzes (open collaboration encouraged).
Learning reflections [individual, through a weekly Google form submission]
Topic reflections [individual, as a 3-5 minutes substantive post to the forum]
(Optional) Peer instruction module, which will adjust the grading criteria as specified in Option B.
Weekly homeworks with limited collaboration encouraged.
3 timed (2 hours limit) take-home quizzes that are open-notes and open-book with no collaboration of any kind.
Review the logistics for accessing your book and notes.
You may use a laptop or tablet device only for accessing your book and notes. If you need to borrow one, you can do so from LITS:
"Laptops are available for either 3-hour or 3-day loan periods on a first-come, first-served basis at the Circulation Desk. We offer Macbook Pros, Dell Latitudes and Dell Chromebooks. You can check on current availability of student laptops at Gadgets-to-Go."
A timed (3-hour) take-home final in the final exam period that is cumulative, with an emphasis on the final 3 topics.
Grading (Option A)
Topic module quizzes: 10%
Articulation: 10%
Weekly learning reflections: 4%
Topic reflections: 6%
Homeworks: 10%
Quizzes: 45%
Final exam: 25%
Grading (Option B)
Topic module quizzes: 10%
Articulation: 20%
Weekly learning reflections: 4%
Topic reflections: 6%
Peer instruction topic module: 10%
Homeworks: 10%
Quizzes: 45%
Final exam: 15%
Lateness Policy
It's important to keep up with the content and pacing of the course. I recognize that sometimes unpredicted situations arise that may prevent you from submitting an homework. Therefore, your lowest homework grade will be dropped.
In addition, you will have 2 additional days (48 hours) to submit topic modules and homeworks without a consequence to your grade. After that, the credit you receive will be reduced each day.
To summarize: I will calculate your grade according to this chart:
≤ 2 days (48 hours): full credit of your earned grade, or
≤ 3 days (48 - 72 hours): 70% credit of your earned grade, or
≤ 4 days (72 - 96 hours): 30% credit of your earned grade, or
> 4 days: 0% credit of your earned grade
Homework logistics
Computer science is a subject that builds up on itself. To encourage you to continue to deepen your understanding of a topic, you will perform a written reflection on each homework. Solutions will be released on moodle along with the homework; you should not look at the solutions until you have completed the work. It is up to you to decide if you want to review each problem’s solution as you go or wait until you’ve completed the whole homework.
It is a violation of the honor code to look at the solutions before you’ve completed your work or to share them with anyone (including students that take the course in other sections or future offerings).
Submission and Grading
When you submit the homework, you must also include a self-assessment and reflection:
Self-assessment. Use the solutions to assess and reflect upon your submission. For each problem, you must:
Give yourself an assessment mark. (These are based on Mark Talbert’s EMRN rubric; here is a link to a flow chart illustration of the rubric).
E - The work meets or exceeds the expectations of the assignment. Communication is clear and complete. Deep understanding of the concepts is evident. There are no non-trivial errors. This work could be used as a classroom example.
M - Understanding of the concepts is evident through correct work and clear, audience-appropriate explanations. Some revision or expansion is needed, but no significant gaps or errors are present. No additional instruction on the concepts is needed.
R - Partial understanding of the concepts is evident, but there are significant gaps that remain. Needs further work, more review, and/or improved explanations.
N - Not enough information is present in the work to determine whether there is understanding of the concepts. The work is fragmentary of contains significant omissions. Or, there are too many issues to justify correcting each one.
? - If you are really unsure as to what mark to assign.
Reflection.
Provide a short and specific reflection as to why you earned your self-assessment mark, such as:
“In problem 2, I was confused by the definition of ….”, or
“For the proof of problem 1, I incorrectly assumed that …”, etc.
Ask specific questions that still remain, such as:
“Is this also a counterexample?” or
<circle a part of a proof you’re unsure of> “I didn’t know how to phrase this – how can I be more technically accurate?”
[Optional] Provide one hint for the problem (to your past self or future student).
Each problem on the homework will be graded on a 3 point scale, analogous to the self-assessment rubric. The grade for the entire homework will be weighted with 75% calculated from the average of the problems and 25% from the quality of your self-assessment/reflection.
E - (3 points) The work meets or exceeds the expectations of the assignment. Communication is clear and complete. Mastery of the concepts is evident. There are no non-trivial errors. This work could be used as a classroom example.
M - (2 points) Understanding of the concepts is evident through correct work and clear, audience-appropriate explanations. Some revision or expansion is needed, but no significant gaps or errors are present. No additional instruction on the concepts is needed.
R - (1 points) Partial understanding of the concepts is evident, but there are significant gaps that remain. Needs further work, more review, and/or improved explanations.
N/? - (0 points) Not enough information is present in the work to determine whether there is understanding of the concepts. The work is fragmentary of contains significant omissions. Or, there are too many issues to justify correcting each one. Or, no self-assessment was provided.
Collaboration
Collaboration is encouraged while thinking through the homeworks; you may wish to use the dedicated Wednesday evening meeting time for this purpose. Problems will take time to understand and solve, and you will benefit from developing ideas and solutions in small groups.
You must write your own solutions, and no collaboration is allowed while writing the solutions. Writing solutions on your own will cement understanding of the problem and demonstrate mastery of the solution. Looking at solutions from other students or any other source (including the web), or collaborating to write solutions, is considered a violation of the honor code. All suspected violations will be referred to the Honor Code Council. For more detail on what constitutes an academic violation of the Honor Code, please see the Student Accountability webpage.
Submission
You must submit written homeworks through Gradescope. Refer to the Tools page for details.
Feedback and grading
Homeworks are a chance for you to engage with the material and the process of learning as well as receive feedback. To this end, you will be evaluated on a mixture of self-assessment and reflection along with more traditional "grading" done by myself and the TAs.
The general workflow will involve:
submission of homework [75%]
self-assessment and reflection [25%]
You may only be graded on a subset of the problems (which you will not know ahead of time) for each homework.
Additional course information
Accommodations
Disability Services is the office on campus that determines academic accommodations for students with disabilities. If you need official accommodations through Disability Services, you have a right to have these met and kept confidential. Please contact Disability Services, located in Mary Lyon Hall 3rd Floor, at 413-538-2634 or disability-services@mtholyoke.edu. If you are eligible for academic accommodations, you will be provided with an accommodation letter. Once you receive your accommodation letter, I would like to meet with you and discuss these approved accommodations and our class. For more information on who might be eligible for accommodations and the application process please see the Disability Services website (https://www.mtholyoke.edu/disability-services).
Title IX/Responsible Reporter:
If you or someone you know has been a victim of discrimination, harassment or violence based on sex or gender and you would like to talk to someone about our resources, please contact the Title IX Coordinator, Shannon Da Silva at titleixofficer@mtholyoke.edu.
As a faculty member, I am a responsible reporter for any information I learn that may be a violation of our Gender-based and Sexual Misconduct Policy. This means that I will need to share this information with our Title IX Coordinator, Shannon Da Silva. This could be anything related to sexual assault, dating violence, stalking or sex or gender-based harassment. If you are experiencing any of these things and you want to talk with someone who is not a responsible reporter, I can help direct you to private and confidential resources on campus (Counseling Service, Health Services, and Alcohol and Drug Awareness Project. These offices have a legal mandate for confidentiality. These offices are not required to turn over identifying information to the Title IX coordinator but may provide anonymous data to the Title IX coordinator for reporting requirements of the Clery Act).
Academic Integrity & Honor Code
Mount Holyoke College is a community of students, faculty, staff, and administrators committed to free inquiry and the pursuit of knowledge in the tradition of the liberal arts. The decision to join this academic community requires acceptance of special rights and responsibilities that are essential for its effective functioning and the realization of its mission. All members of the community share the responsibility to uphold the highest standards of academic integrity.
I expect all your work to abide by the MHC Honor Code: “I will honor myself, my fellow students, and Mount Holyoke College by acting responsibly, honestly, and respectfully in both my words and deeds.” Any work that does not will be reported to the Academic Honor Board. For more detail on what constitutes an academic violation of the Honor Code, please the Student Accountability webpage..
More specifically:
The Computer Science Department follows the Mount Holyoke College Honor Code. Work submitted for grading must be entirely your own, unless you were instructed to work in groups. The purpose of course homeworks is to practice skills, gain a deeper understanding of the course material, and apply that knowledge to new situations. Homeworks are designed to challenge you, stimulate critical thinking, and help you understand the concepts related to the course. Your grade is a reflection of your understanding of the material.
We recognize that collaboration can help you master course material. In fact, there are certain ways in which we will encourage you to collaborate. These include:
discussing course content at a high level
getting hints
talking about problem-solving strategies
discussing ideas together
However, you must do all write-ups on your own. Writing solutions on your own will test and demonstrate your mastery of course material.
Looking at solutions from other students or any other source (including the web), or collaborating to write solutions to individual work, is considered a violation of the honor code. All suspected violations will be referred to the academic honor board. If you are uncertain whether something is allowed, it is your responsibility to ask.
If you have engaged in any of the above acceptable collaboration activities for a homework, you MUST acknowledge the classmates or TAs with whom you spoke – this should be done as a note when you submit your work.
Note that the Association for Computing Machinery has a strong Code of Ethics and Professional Conduct. At this site you can read both the current Code from 1992 and the draft of the new 2018 version.
Internet sources
All material for the course is contained on this web site, the course moodle site and the text.
You should not consult any other source.
Honor code dos and don'ts
These lists are intended to clarify what types of behaviors are and are not generally permissible. Follow these guidelines unless specifically directed otherwise. (clarify if uncertain)
Do:
Organize study groups.
Clarify ambiguities or vague points in class handouts, textbooks, assignments, and labs.
Discuss assignments at a high level to understand what is being asked for, and to discuss related concepts and the high-level approach.
Refine high-level ideas/concepts for projects (i.e. brainstorming).
Outline solutions to assignments with others using diagrams or proof sketches, but not complete machines/proofs.
Get or give help on how to operate the computer, terminal, or course software.
Submit the result of collaborative coding work if and only if group work is explicitly permitted (or required).
Don’t:
Look at another student’s solutions.
Use solutions to same or similar problems found online or elsewhere.
Search for homework solutions online.
Turn in any part of someone else's work as your own (with or without their knowledge).
Share your code or written solutions with another student.
Share your written solutions online.
Allow someone else to turn in your work as their own. (Be sure to disconnect your network drive when you logout and remove any printouts promptly from printers.)
Collaborate while writing programs or solutions to written problems. (But see above about specific ways to give or get debugging help.)
Write homework assignments together unless it is specified as a group assignment.
Collaborate with anyone outside your group for a group assignment.
Use resources during a quiz or exam beyond those explicitly allowed in the quiz/exam instructions. (If it is not listed, don’t use it. Ask if you are unsure.)
Submit the same or similar work in more than one course. (Always ask the instructor if it is OK to reuse any part of a different project in their course.).
Audio/Visual Recording Policy
To encourage active engagement and academic inquiry in the classroom, as well as to safeguard the privacy of students and faculty, no form of audio or visual recording in the classroom is permitted without explicit permission from the professor/instructor or without a letter from AccessAbility Services, signed by the faculty member, authorizing the recording as an accommodation. Authorized recordings may only be used by a student who has obtained permission and may not be shared or distributed for any reason. Violation of this policy is an infraction of the Mount Holyoke Honor Code and academic regulations and will result in disciplinary action.
Thanks to Dan Sheldon for so generously letting me use his materials from his version of this course!