(From How Not to Be Wrong, by Jordan Ellenberg)
This course takes a problem-driven, example-driven approach to learning the basics of design and analysis of 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, and network/graph 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.
All information is subject to change at any time. Check the course website and moodle page daily for announcements and updates.
Tuesdays and Thursdays from 10:25-11:40 in Fanning 315
Dr. Christine Chung
New London Hall 220
Tentative office hours: Wednesdays and Fridays 10:00 to 11:30 (please sign up for appointment slots).
Weekly TA sessions: Sunday, Tuesday, and Wednesday, times and locations TBA.
· Required text: Algorithm Design, by Jon Kleinberg and Éva Tardos (on reserve in the library)
o A wonderful text based on an amazing class they taught at Cornell. 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 Recommended 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 for writing up homework (see below for more info)
Homework must be submitted each Thurs at the start of class. Homework problems must be solved solely from discussions with your homework group, other students in our class, the TA, 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*.
That said, use your allowable resources as much as possible! Whenever you bump into another Algorithms student on campus, start up a conversation about the homework problem that’s really confounding you! See if you can glean hints from each other. Ask to join the meetings of other groups, etc. Each week you will have a new set of mysteries to be actively solved using all resources at your disposal!
Homework groups will be initially 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 Sunday and the second between Mon and Wed. 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. What can happen between the first and second meetings that will facilitate this resolution?
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’re 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, in the shower, 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 nights a week, your TA will hold 2-hour help sessions. (Sunday, Tuesday, and Wednesday.)
Here is how you should use these sessions:
a. Bring your questions about specifics. E.g.,
· the meaning of a particular sentence, phrase or word in a homework question or in the reading,
· if a 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. 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. Hand outs. The TA has been instructed not to give direct answers to questions like: “I’m lost on this problem… how do I go about solving 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. Each other. You should talk to other students in the class liberally about the problems each week. It is not so important that the final ideas for how to solve the problem were all yours or even your group’s. It is important that the writing-up of the solution you hand in is all yours.
4. 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 to hold one or both of part of your meetings of each week during the TA sessions. After your group’s first meeting, you should begin a draft of your individual write-ups. Try to get 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 the solutions.
Each student must submit their own, individually-written, solution set. The problem solving is only half the battle, because it’s only when you have to sit down and write it up clearly that you really make it or break it. Homework submissions will be due before the start of class on Wednesdays. Late homework will be penalized (even if it is five minutes late), in order to encourage on-time attendance and full participation in class every day. Email me or come see me if a genuine 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.,
4. TeXmaker (lately I’ve been mostly using this one, and find it to be quite convenient…)
5. etc, etc
6. or use any text editor (one that does syntax highlighting always helps) and then compile your .tex file using LaTeX at the command prompt
All the offline options (options 3 and onward) will require you to download/install LaTeX on your machine, but off-line compiling of LaTeX docs can be faster, and it’s a good skill to learn. If you go with 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 (according to above tutorial) from the command prompt.
2. If you are on a Mac, try this guide: http://guides.macrumors.com/Installing_LaTeX_on_a_Mac
3. Here’s a good intro with a sample file
If you go with online editing, compiling can be more cumbersome, but there are nice, instructive templates at overleaf that allow you to dive right in. You can just go there and click “Create a New Paper”
Either way, you should also test out (compile them to generate the corresponding pdf for) these very helpful sample files:
Note that hand-drawn diagrams/tables that aid in your exposition are always encouraged and welcome as attachments to your homework submission. (Of course, diagrams and tables that are not hand-drawn are even better, but these can sometimes take extra time/effort to create.) If you attach them to the end of your write-up, please reference them from within the text so we realize they are there as we are grading.
Start each HW write-up with a HW participation log entry for the week: indicate the location, date/time and duration of your HW group meetings along with 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.
Homework questions will generally 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’s 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 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’re 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, your grade will be penalized. Be sure to always write exactly what you mean, and mean exactly what you write.
You may challenge a homework grade within one week of receiving the grade. Stipulations:
1. You must attach to the original, graded homework set, a detailed 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, the professor may return your submission with the same score, a higher score, or a lower score. (Please note that other than obvious/blatant grading errors, when a student asks me to look back on their graded assignment, I am usually surprised by how lenient I was the first time I graded it.)
At least ten hours per week should be dedicated to this course: 4-6 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, you will probably need around 15 hours for this class each week. Your weekly COM304 schedule will look something like this:
§ Day 1 (Friday): 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)
§ Day 2 (Saturday): Read the problems carefully, repeatedly as needed, and start figuring out what is really being asked, noting/posting questions. Meet with an instructor to discuss any remaining questions you have about the last HW that was returned to you. (2-3 hours)
§ Days 1, 2, or 3 (Fri-Sun): Meet with your groups for problem solving session #1, discussing everyone’s questions from the the last HW and the reading, then working together on the first two HW problems. (2-5 hours)
§ Day 3-4 (Sun-Mon): 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. (2-5 hours)
§ Days 3-5 (Sun-Tues): Continue “background processing” (see above), see TAs, other students, prof, as needed.
§ Days 4-6 (Mon-Wed): Meet with your groups for problem solving session #2. (2-5 hours)
§ Day 6 (Wed): Finish writing up your homework solutions. (2-5 hours)
§ Day 7 (Thursday): Rest/reflect/recover.
You must do the reading carefully, thoroughly, and in a timely fashion… early enough to be able to post anything about the reading and/or homework that confused you to the 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, etc.). All comments/questions posted to moodle will contribute to your class participation grade. This works especially well if you prefer not to participate in class too often.
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, when you meet 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 professor’s 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.
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.
A semester course is normally equivalent to four semester hours. Connecticut College complies with federal regulations defining the credit hour. For each credit hour awarded, students are expected to complete no fewer than three hours of combined instructional or studio/lab time and out-of-class work per week.
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 misconduct, intimate partner violence, stalking, or other forms of gender-based discrimination. Heidi Freeland-Trail, the Director of Sexual Violence Prevention and Advocacy, can advise you confidentially as can Counseling Services and any of the College chaplains. Heidi can also help you access other resources on campus and in the local community. You can reach Heidi at 860-439-2219 or firstname.lastname@example.org, and her office is in Cro 222.
The student sexual misconduct, intimate partner violence, stalking, and non-discrimination policies are in the Student Handbook, 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 the Office of Institutional Equity and Inclusion at 860-439-2035 or Fanning 110.
The Academic Resource Center (ARC) offers services to support your academic work such as study skills workshops, time management, coaching and tutoring. Our offices are located on the second floor of Shain Library. Please visit us or call 860-439-5294 for more information or to schedule an appointment.
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. To make an appointment, call 860-439-2173 or stop by the Writing Center at 214 Blaustein. If you're a confident, experienced writer we can help you to push your ideas and polish your style; if you're a relatively inexperienced and not-so-confident writer we can also help you, by working on grammar or organization or whatever you need. Writing Center tutors are trained to help you to discover what you think through writing. 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. For further information, visit the Writing Center web page at http://write.conncoll.edu/.
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 present your Accommodation Memo privately during my office hours as early as possible in the semester. 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- 5428or email@example.com.
Student Health Services, located in the Warnshuis Student Health Center behind the library, is available to all full-time, matriculated students. Our purpose is to help students maintain optimal general health through the disciplines of physical and mental health, and health education around lifestyle choices. This is accomplished through a full-time staff and a variety of professional consultants in many disciplines. All professional services are delivered with attention to confidentiality. In the event of a serious illness or injury, parents or guardian will be notified at the discretion of the staff. You can schedule an appointment Monday through Friday by calling 860-439-2275. Information on Care When We Are Closed, Our Services, and Student Health Insurance may be found on Camelweb, in the Student Life Section, under Student Health Services
The mission of the Student Counseling Services is to promote the emotional and psychological growth and well being of the students at Connecticut College. The Student Counseling Services' goal is to enhance each individual's ability to learn, to create and to be fully participating members of the College community by utilizing safe, culturally sensitive and inclusive approaches to mental health treatment. To carry out this mission, Student Counseling Services makes available to students a wide range of outpatient clinical services in a safe, non-judgmental atmosphere including:
o Individual and group counseling
o Psychopharmacological evaluation and medication management
o Crisis intervention services
o Outreach and consultation to the College community
o Psycho-educational forums
o Referral to off-campus clinicians for specialized and/or intensive treatment
Connecticut College Student Counseling Services has been accredited by the International Accreditation of Counseling Services (IACS) since 2005. Appointments may be made by phone at (860) 439-4587 or via email at SCS@conncoll.edu.