COM304: Design and Analysis of Algorithms
Spring 2024
Course Schedule
Course Description
This course takes a problem-driven, example-driven approach to learning the basics of design and analysis of algorithms. We will analyze our algorithms both for run-time complexity and correctness. These analysis skills will be built upon throughout the semester. By studying canonical problems from the field of algorithms, like matching, scheduling, network/graph and other combinatorial optimization problems, we examine fundamental algorithm design techniques, including greedy algorithms, divide-and-conquer, dynamic programming, and network flow. We will conclude with a study of NP-complete problems and coping with intractability.
(From How Not to Be Wrong, by Jordan Ellenberg)
Course Info
All information is
subject to change at any time. Check your email, the course website and the
course moodle page daily for announcements and
updates.
Class meetings
Mondays and Wednesdays from 1:15-2:30, Olin 107
Course web pages
o http://cs.conncoll.edu/cchung/com304
Professor
Dr.
Christine Chung
http://cs.conncoll.edu/cchung
cchung@conncoll.edu
860-439-2074
New London Hall 220
Office hours: sign up for appointment
slots or if you cannot make any of these, stop in or email me for an
appointment!
Teaching
Assistants
Grant Archer
Japmeet Bedi
Libby Flathers
Michelle Le
Dreyenn Osgood
Bill Tran
Weekly TA sessions: please see this
schedule
Course Materials
· Required text (on reserve in the library): Algorithm Design, by Jon Kleinberg and Eva Tardos
o A wonderful text based on an amazing class they taught at Cornell Univ. We will use this extensively each week and throughout the semester.
·
Other
books (also on reserve in the library):
o Additional (minimal) required reading
from: Algorithms, by Dasgupta,
Papadimitriou, Vazirani. (This one is also on reserve in Shain.)
o A
good reference text: Introduction to Algorithms, by Thomas H. Cormen,
Charles E. Leiserson, Ronald L. Rivest, Clifford
Stein
o Another nice reference text: The Algorithm Design Manual, by Steven Skiena
o Recommended reading for fun: The Golden Ticket: P, NP, and the search for the
impossible, by Lance Fortnow
·
Required software: LaTeX
o typesetting software/language for writing up
homework sets (see below for more info)
Course Policies
Grading
|
Homework
Homework must be submitted each week as a pdf via moodle, by the submission deadline on Friday afternoons (see also the course schedule for deadlines). Homework problems must be solved solely from discussions with your homework group, other students in our class, the TAs, or professor. The internet may be used as a general information resource, as always, but directly looking up problem solutions online (or using other similar shortcuts) to solve HW problems will constitute an honor code breach*. See also the AI policy at the bottom of this page.
That said, use your allowed resources as much as possible! Whenever you bump into another Algorithms student on campus, start up a conversation about the homework problem that is really confounding you! See if you can glean hints from each other. Ask to join the meetings of HW groups other than your own, etc. Each week you will have a new set of mysteries to be actively tackled using all resources at your disposal!
Groups meetings and other support
Homework groups will be set by the instructor. Groups may be shuffled by the instructor at any time in the semester. You should schedule at least two meetings per week with your groups, the first before Tues and the second between Tues and Friday. Everyone should have completed an initial reading of the textbook and exercises before the first meeting. The second meeting will be used to resolve remaining open issues that arose in the first meeting and to provide feedback on each other’s writing. What can happen between the first and second meetings that will facilitate your problem solving progress?
1. Your brain’s background processes. Like a computer processor, our brains have foreground processes and background processes. When we are not actively working on our homework problems, our brains will be working on them in the background, while we are walking, playing, eating, talking, sleeping, etc. And background processing is critical for solving problems like this. That is why it is important for your group to meet twice, once soon after the homework is assigned, and again later in the week after background processing has taken its course. Ask any computer scientist or problem solver and they will tell you that they often make the most progress on their problems when they are not actively working on them, e.g., on a jog, while brushing their teeth, etc. In fact, if you feel stuck on a problem for too long, one good strategy is to take a break, thereby moving the problem into background processing for a little while.
2. Your TAs. Three or four nights a week, your TAs will hold TA sessions.
Here is how you should use these sessions:
a. Bring your questions about specifics. E.g.,
· the precise meaning of a particular sentence, phrase or word in a homework question or in the reading,
· if a HW question should be interpreted this way or that way
b. After working for at least one or two hours on the problem, clearly explain to the TA what you’ve tried so far. Showing/using small examples is always helpful. The TA can then try to nudge you in the right direction, or help you start to build off of what you have already done.
Here is what you should not expect of your TA:
a. Handouts. The TA should not give direct answers to overly broad questions like: I am lost on this problem… how do I solve it?
b. Spoon feeding. The TA has been instructed to take a guided inquiry, or Socratic approach whenever possible. It is better if the TA can guide you to a conclusion than give you the answer directly.
3. The algorithms TA mentor that may be assigned to your HW group, if you request it and resources allow. Each HW group may have an algorithms TA mentor that will meet for 30 minutes to an hour per week with that HW group to discuss and help answer questions the group has on the HW.
4. Each other. You should talk to other students in the class liberally about the problems each week. It is not so important that the ideas for how to solve the problem were all your own, or even confined to your own HW group. It is important however, that the writing-up of the solution, the explanation of it that you hand in, is your own. (See more, above and below, on academic integrity.)
5. Your professor. I will have office hours each week (see above, under Course Info). The same guidelines as for the TA sessions apply (see above, item 2 of this list).
You are allowed/encouraged to hold one or both of your meetings each week at/during (or overlapping with) the TA sessions. After your first group meeting, you should each begin a draft of your individual write-ups. Try to get at least halfway done with your write-up before the second group meeting. After the second meeting you should feel ready to finish your write-up of your solutions.
Submissions
Each student must submit their own, individually-written, solution set. The problem solving is only half the battle, because it is only when you have to sit down and write your solutions and explanations sufficiently clearly that you really make it or break it. Homework submissions will be due via moodle each week (see course schedule for deadlines). If it is due on a class day, the HW submission link will close before the start of class and I will re-open it after class for late submissions. Late homework will be penalized, but only minimally if it submitted by midnight of the day it is due. Email me or come see me if an emergency situation prevents you from handing in an assignment on time.
Your homework should be typeset in LaTeX. There are many LaTeX typesetting options now, both cloud-based and offline. E.g.,
1. https://www.overleaf.com/ (I use this one the most lately, and it is completely sufficient for our needs)
2. TeXmaker (for off-line compiling/editing I have been mostly using this one, and find it to be quite convenient…)
3. TeXworks
4. etc, etc
5. or use any text editor (one that does syntax highlighting always helps) and then compile your .tex file using LaTeX at the command prompt/terminal
If you go with online editing, compiling can be a bit slower, and sometimes the web-based interface can be cumbersome, but there are nice, instructive templates at Overleaf that allow you to dive right in. Whatever you decide to use, please create an Overleaf account to try out the templates for some initial exposure. E.g., here is a reasonable template for HW assignments.
All the offline options will require you to download/install LaTeX on your machine, but off-line compiling of LaTeX docs can be faster, and it is a good skill to learn. After you create an Overleaf account, if you also want to try an offline LaTeX option:
1. If you are on a Windows machine, you can install MikTex and compile from TeXworks or TeXmaker or run the pdflatex command from the command prompt.
2. If you are on a Mac, try this guide: https://sourabhbajaj.com/mac-setup/LaTeX/
Here is another guide you could try as well: https://guides.nyu.edu/LaTeX/installation
Either way, whether you use a cloud-based service like Overleaf or an offline option, you should also test out (compile them to generate the corresponding pdf for) these very helpful sample files:
o template-1.tex (source code), template-1.pdf (resulting pdf) [taken from http://people.cs.umass.edu/~mcgregor/courses/CS611F12/]
o template-2.tex (source code), template-2.pdf (resulting pdf) [taken from http://web.engr.oregonstate.edu/~briggsf/cs325/]
There are also neat LaTeX look-up tools here and here!
Note that hand-drawn diagrams/tables that aid in your exposition are always encouraged, and you are not required to embed or attach them in any fancy way. That said, photos of drawings can also be inserted into your LaTeX document quite easily. (Of course, diagrams and tables that are not hand-drawn can be even neater/better, but these are not required as they can sometimes take extra time/effort to create.) If you simply choose to upload any drawings/figures as separate files to moodle when submitting your HW, that is perfectly fine, just please reference them from within the text so we know to refer to them as we are grading.
Grading procedure
Start each HW write-up with a HW participation log entry for the week. For each group meeting you must record the following: (1) meeting location, (2) calendar date & time span of meeting and (3) the names of the students who participated. I will keep a running tally of the HW-based portion of your participation grade using these logs. Each week your HW participation will be counted out of 4. A 4/4 means you got credit for all 4 hours of group meeting time.
Most homework questions will ask you to design an algorithm for a problem. A complete answer must include three parts:
1. a clear description of the algorithm (in pseudocode or English)
2. an analysis of your algorithm run-time (always try to make your algorithms as efficient as possible)
3. a proof that the algorithm works correctly
Each week you will probably have 3-4 questions, which will usually each be graded out of 10 or 15 points. Complete and correct solutions are modeled nicely by the “Solved Exercises” at the end of each chapter. Actually, these solved exercises are more verbose/meandering than needed, since they are describing how to arrive at the solution, including some false starts, rather than simply demonstrating a complete understanding of the solution (the latter being what you need to do), but they give a good sense of what we are looking for. If your solutions are wordy like those modeled in the “Solved Exercises,” but the words are helpful in explaining your solution, as in the text, you will be in fine shape. If your solutions are wordy in a way that detracts from the clarity of your answer, even if your answer is correct, you are likely to lose points from the confusion. Be sure to always write exactly what you mean, and mean exactly what you write.
Hint/tip: you are encouraged to have your group-mates/classmates and possibly TAs review a draft of your exercise solution before finalizing the write-up so that you can get preliminary feedback on it from them. Oftentimes what is completely clear to you as you composed it can actually be very unclear to someone else. Showing your write-up to another student for review/feedback purposes is encouraged. Even if it means you have given away some of your ideas to that person. Indeed, the process will hopefully ignite some good critical discussion about your solution ideas! As long as that student writes up their own version of the solution in their own words, all will have the learning experience that we are striving for. Be sure not to cross that line into COPYING another write-up when sharing ideas or getting feedback from one another. A good rule of thumb is to never be typing up your own solution WHILE simultaneously reading/viewing someone else’s.
For some additional writing and grading guidelines see this page and this page.
Challenging a homework grade
You may challenge a homework grade within one week of receiving the grade. Stipulations:
1. You must give/send me a written explanation of why you believe the grade received was incorrect/unfair. This might involve an explanation of how/why the grader has misinterpreted your solution, etc.
2. When submitting for a re-grade, I may return your submission with the same score, a higher score, or a lower score.
Expectations
Time commitment
At least 12 hours per week should be dedicated to this course: 4-5 spent on reading, 4-10 spent solving the problems with your homework groups, and 4-5 spent on writing up solutions individually. To get an A or B, you will probably need more like 15 hours for this class each week. If you are planning a busy semester or are currently over-pointing you are strongly encouraged to take this course another semester. Your weekly COM304 schedule will ideally look something like this:
o
Day 1 [Saturday]
(Read and reflect): Complete all textbook reading, noting/posting questions. Also
read through the comments we made on the HW that was most recently returned to
you, noting any questions you have. (2-4
hours)
o
Day 2 [Sunday]
(Understand the problems): Read the problems carefully, repeatedly as needed,
and start figuring out what is really being asked, noting/posting questions. Meet/email
a TA/instructor to discuss any remaining questions you have about the last HW
that was returned to you. (2-3 hours)
o
Days 1, 2, or 3
(Group Meeting #1): Meet with your groups for problem solving session #1, discussing everyone’s questions from
the last HW and the reading, then working together on at least the first two HW
problems. Check in with TAs/prof as needed. (2-5
hours)
o
Day 3-4 [Mon-Tues]
(Draft your write-up): Lay down a first draft of at least the first half of
your write-up. This will give you
time to run some of your phrasing/logic/presentation/writing past each other,
the TAs or myself before final submission. Beware, do not give copies of your write-ups to each other.
But showing your write-ups to each
other for peer feedback on them is a good thing. For more details on peer
review of your HW drafts, see “Hint/tip” paragraph above. (2-5 hours)
o
Days 3-5 [Mon-Wed]: Continue
“background processing” (see above), see TAs, other students, prof, as needed.
o
Days 4, 5, or 6
[Tues-Thurs] (Group Meeting #2): Meet with your groups for problem solving session #2. (2-5
hours)
o
Day 6 [Thursday]
(Revise/finalize write-up): Finish writing up your homework solutions. (2-5 hours)
o
Day 7 [Friday]
(Submit): Submit your write-up to moodle. Then
rest/reflect/rejuvenate. (Go back to Day 1.)
Readings and participation
You must do the reading carefully, thoroughly, and in a timely fashion. Please post anything about the reading and/or homework that confused you to the moodle class forum (or ask us in TA sessions/office hours). Answer each other’s questions on this forum whenever possible. Anything you enjoyed about the reading you can post there too (your favorite result/theorem from a particular chapter, the beautiful simplicity and unexpected effectiveness of an algorithm, your ideas for alternative algorithms, etc.). Any/all comments/questions posted to moodle, no matter how trivial, will contribute to your class participation grade. Moodle forum posts work especially well if you prefer not to participate in class too often.
Course Schedule
Other important info
Credit Hour Definition
A semester course
is normally equivalent to four credit hours. Connecticut College complies with
federal regulations defining the credit hour. For each credit hour awarded, a
course will provide an average of at least one hour of classroom or direct
faculty instruction (class meetings, labs, review sessions, field trips, office
hours, film screenings, tutorials, training, rehearsals, etc.) and at least two
hours of out-of-class work (homework, preparatory work, practice, rehearsals,
etc.) per week.
*The
Connecticut College Honor Code
Academic integrity
is of the utmost importance in maintaining the high standards of scholarship in
our community. Academic dishonesty is considered to be a serious offense against the community and represents a
significant breach of trust between the professor, the classmates, and the
student. There are many forms of academic dishonesty including plagiarism,
falsifying data, misrepresenting class attendance, submitting the same work in
two courses without prior approval, unauthorized discussion or distribution of
exams or assignments, and offering or receiving unauthorized aid on exams or
graded assignments. Students violating the Honor Code may be referred to the college's Honor Council for resolution.
Title IX
Statement
As a faculty
member, I am deeply
invested in the
well-being of each student I teach. I am here to assist you with your work in
this course. If you come to me with other non-course-related concerns, I will
do my best to help. It is important for you to know that all faculty
members are trained and required to
report any incidents of gender-based discrimination, including discrimination
based on gender identity, gender expression, and sexual orientation. This means that I cannot keep
information confidential about sexual harassment, sexual assault, dating
violence, stalking, or other forms of gender-based discrimination, and that I
will report that information to the Title IX office, if it is shared with me. However, the Title IX office typically only acts on
formal complaints, and in response to notice from me
will reach out to you to offer support and resources, and
offer you the opportunity to file a formal Title IX complaint, which is up to
you. The Director of Sexual Violence Prevention and Advocacy and the SVPA
Confidential Advocates can advise you confidentially as can Counseling Services
and any of the College chaplains. SVPA can also help you access other resources
on campus and in the local community. You can reach the Confidential Advocates
at SVPA@conncoll.edu, make an appointment with the Confidential Advocates at
http://bit.ly/ConnCollSVPA or contact the SVPA Confidential Advocate ON Call
24/7 at 860-460-9194. The student sexual harassment, dating violence, stalking,
and non-discrimination policies are in the Sexual Harassment and
Nondiscrimination Policy, which can be found on CamelWeb, in the “Documents/Policies” section,
under the Student Life section. There you will find the policies, definitions,
procedures, and resources. If you need to report an incident or have any
questions about the policy, you can contact 860-439-2624 or titleix@conncoll.edu.
Academic
Resource Center
The Academic
Resource Center (ARC) offers services to support your academic work such as
study skills workshops, time management, coaching and tutoring. Its offices are
located on the second floor of Shain Library.
Students can make appointments by clicking on this link: https://forms.gle/BQecmVdK8Bg1sv5P7.
The ARC is open to the community Monday – Friday, 8:30 – 5:00 (evenings are by
appointment only). Students may continue to use the ARC as a quiet study space,
though social distancing and masks are required at ALL times.
If faculty or students have any questions or concerns, they should contact Noel
Garrett (ngarrett@conncoll.edu) or Patricia Dallas (pdallas@conncoll.edu).
Writing Center
The Roth Writing
Center provides one-to-one peer tutoring (free of charge) to help student
writers of all abilities during all stages of the writing process. If you're a confident, experienced writer, our tutors can help you to
push your ideas and polish your style; if you're a relatively inexperienced and
not-so-confident writer, they can help you to work on grammar or organization
or whatever you need. Working with a tutor gives you the opportunity to share
your work-in-progress with an actual reader so that you can get useful feedback
on that work before you have to turn it in for a final grade. You can make an
appointment by using the Google Calendar link on the Writing Center's website
at http://write.conncoll.edu/ or by emailing the Writing Center at
writingcenter@conncoll.edu; a new calendar of appointments will become
available by the second week of each semester.
Office of
Student Accessibility Services
Connecticut
College complies with Section 504 of the Rehabilitation Act of 1973 and the
Americans with Disabilities Act. If you have a documented disability and have been approved for academic accommodations, please have your Faculty
Notification Letter emailed to me through the Student Accessibility online
management system (AIM) and schedule a meeting during my office hours as early
as possible in the semester so that we can discuss the logistics of your
accommodations. If you are not
approved for accommodations,
but have a disability requiring academic accommodations, or have questions
about applying for accommodations, please contact Student Accessibility
Services at 860-439-5428 or sas@conncoll.edu.
Classroom
Recording
With the exception
of those granted accommodations through the Office of Student Accessibility
Services, students are
prohibited from audio,
video, or photographic recording during class periods or out-of-class meetings
with the instructor without explicit permission from the instructor. Recordings
approved in this manner may not be
shared in any form
without permission of the instructor. Violations of this policy shall be considered an Honor Code violation.
Office Hours
Office hours
provide students with additional opportunities to review or ask questions about
the class discussions and assignments. Connecticut College faculty encourage
students to go to office hours so they might learn about your interests, both
inside and outside the classroom. In addition to talking about class material
and assignments, you may find you share common interests, such as music, books,
hobbies, and movies. If a professor knows your interest, they may inform you
about campus programs and activities or other opportunities like fellowships
and scholarships. Most importantly, a professor who knows their students writes
better letters of recommendation. Successful students at Connecticut College
make time to go to their professors’ office hours. All Connecticut College
faculty are required to have office hours on their syllabus and posted on their
office door. If you cannot make your professor’s scheduled office hours,
contact your professor to set up an appointment.
Respecting
Personal Pronouns and Identity
Everyone deserves
to be referred to and addressed in accordance with their personal identity. As a faculty member, I am committed to
ensuring my classroom affirms people of all gender expressions and gender
identities. In this course, we will only use the name and pronouns of
each individual's choosing. The repeated usage of
incorrect names and/or pronouns are against Connecticut College policy and may
constitute a T9 policy violation as well as a violation of state and federal
law. In the classroom, be assured that you will always be referred to by the name and pronouns you choose. If you go by a
different name than your legal name, Connecticut College has a process to
change your preferred name on most campus systems. If you want to learn more
about this process go to conncoll.edu/equity-inclusion/preferred-name-faq/
or email GSP@conncoll.edu. Students, faculty and staff are now able to choose
and share their pronouns within the college community by using the Preferred
Name/Pronouns link on the navigation menu in CamelWeb and the CC Mobile App. Your gender pronouns will appear in
the internal directory located in CamelWeb and the CC Mobile App. If none are selected,
or if “Not Applicable” is selected, no pronouns will display. Enrolled
students’ gender pronouns will also display in Moodle for instructors via the
class participants page. Pronouns are one way to
affirm someone’s gender identity, but they are not necessarily indicative of a
person’s gender identity. Commonly, they/them is a gender-inclusive pronoun
used by a variety of identities. Remember to ask for pronouns, listen, and then
respect the gender identities of those around you by using the proper
terminology. If you have any further questions or you want to learn more about
gender & sexuality, please do not hesitate to contact the Director of
Gender & Sexuality Programs at gsp@conncoll.edu.
AI
Policy
Please
note that the student handbook now includes policy on AI as it pertains to
academic integrity. Here is the relevant passage:
Plagiarism occurs when
work does not reflect the student’s personal and original words,
word-groupings, or ideas. Authorized use of artificial intelligence (AI)
tools such as ChatGPT needs to be acknowledged unless otherwise specified. Plagiarism
is a violation of the Honor Code, regardless of intent. Ignorance or negligence
is not considered an excuse for plagiarism. Plagiarism consists of:
a. handing in a paper,
assignment, or project that is not one’s own work;
b. using the language of another writer
or tool (such as AI or language translator) without proper
documentation (e.g. footnotes, quotation marks, parenthetical documentation,
bibliography);
c. using the ideas, arguments, or
organization of another writer or tool (such as AI or language
translator) without proper acknowledgment;
Generally speaking, the output of large language models (LLMs) like ChatGPT and others does not meet the standards that we tend to hold for student writing. However, you may find some of their functions useful in your writing process–to help you brainstorm, for example.
In this
class, you are allowed to use large language models as a tool to assist your
writing, but you may not use them to generate your writing. AI assistance means
that you might use a language model to help you brainstorm ideas, explore
potential counterarguments to your writing, or engage in a targeted revision.
Targeted revision might mean asking the model to help you revise a few
sentences that you feel you just can’t get right. AI generated writing means
that you use the program to generate large blocks of text or use the model as a
substitute for creating your own ideas. Here is a good rule of thumb: You may
use LLMs to enhance your learning; you may not use them as an opportunity to
cheat yourself of the opportunity to learn.
If you use
a LLM, you are required to cite your use of it in a footnote in a manner
similar to the way a scientist might describe an instrument they have used in
an experiment. If you use a language model and do not cite it, it will be
considered academic dishonesty and an honor code violation. When a reader comes
to a passage influenced by the artificial intelligence, you should create a
footnote with the following information:
·
The
AI tool/program used to assist you (e.g., GPT-3)
·
The
date and/or dates that you used the program to assist you
·
A
general description of how AI influenced the writing, including the actual
prompting language if possible.
Here is an
example footnote: “The following three paragraphs of the text have been
influenced by my work with the GPT-3 Davinci model, used on 1/16/22. Originally,
I drafted and revised this write-up in response to feedback from a
classmate/TA. However, even after revision, I had difficulty with the
organization of the following three paragraphs. The flow did not seem correct
to me. I fed these paragraphs into the LLM and prompted it with the following
language: ‘These paragraphs have organization issues. Please revise them to
make them more coherent.’”