Syllabus

This course is about organizing data in canonical ways so that both client code (the part of the program using the data) and provider code (the part that organizes the data) can work predictably and efficiently. We’ll learn:

• the difference between “abstract data types” (ADTs) and “data structures”,
• the tradeoffs among different approaches to structuring data,
• the circumstances under which each approach is appropriate to use, and
• how to quantify the efficiency of a given technique.

We are going to cover pretty much the entire book, but taking the chapters entirely out of order. In broad strokes, we'll cover:

• a Java primer;
• a variety of ADTs: graphs, stacks, queues, lists, dicts, sets, priority queues, and trees;
• computational efficiency, recursion, sorting, and hashing; and
• a variety of implementations for the above ADTs, as well as lower-level ADTs such as heaps.

I prepared a diagram showing all the ADTs and data structures we will cover; amazingly, you'll understand this diagram by the end of the term!

• Attendance. I expect that you will attend every class meeting possible — you are responsible for accommodations if you must miss a class. I won't always take roll, but I reserve the right to do so during any class. You may be absent up to twice when I take roll without it affecting your grade. Unless you've made formal arrangements with me in advance*, there are no excused absences beyond this.
• Presence. “Presence” is more than just physically being there. Turn off your phone, do not text during class, do not use your computer for anything other than in-class activities and note-taking, etc. We've only got a short time together, so let's make the most of it.
• Asking Questions. That's right, you are required to ask questions if you have them! (Not that I can enforce that.) Raise your hand, interrupt me if you need to, but don't stay silent! If you have a question, your classmates are probably wondering about it too. If my answer to your question isn't helpful, let me know; I'd much rather take the time to answer your question right than to leave you and your classmates confused.
• Readings. Read the book! The chapters of the book are fairly short, and you'll typically be assigned to read one chapter in preparation for each class.
• Homework. There are regular assignments throughout the term, to give you hands-on experience with ADTs and their implementations. The assignments are meant to be challenging and to stretch you, without being overwhelming; simply put, I believe that the homework is where you will do the vast majority of your learning in this class.
• Quizzes and Exam. There are four in-class quizzes throughout the term, as well as a self-scheduled comprehensive final exam. If you need accommodations for test-taking because of a disability, please contact me early and we will make appropriate arrangements.
• Talking to Me. Keep me in the loop. If you're struggling, stop by my office hours or email me to schedule a time to talk.

If you need help with an assignment, you can consult with other students, consult the book, search online, talk to the prefect, ask a lab assistant, post to Piazza, or come to me. We'll talk some in class about good strategies for searching for answers online, and how best to ask people for help.

If you'd like help from me, please come see me! I am unlikely to answer detailed questions about bugs via email, as it's much easier and more fun for me to do so in person. My office hours are posted at the top of the page; please either stop by then or email me several hours in advance to arrange to meet. I am rarely available on Tuesdays and weekends, as I reserve those for research and other work. I try to respond to email promptly, but I can't promise any faster turnaround than the afternoon of our next class meeting after you email me.

In this class, as with all classes at Carleton, there are a number of college-wide resources that can be of help: the library, the Write Place, the department's online resources. Feel free to talk to the lab assistants in the CS labs on the 3rd floor of the CMC in the evenings; they are often CS majors and may be able to help. The Math Skills Center may be able to help you with some aspects of the course. Finally, the college has a tutoring program available too.

Your grade will be computed as follows:

There will be four quizzes throughout the course, and your lowest quiz score will automatically be dropped. Quizzes will focus on recent topics, but may ask about any topics up to that point in the course.

Using the above weights, a total of 90% and up will earn you some level of A, 80% and up at least some level of B, 70% and up at least some level of C, 60% and up at least some level of D.

Homework will be submitted via Moodle. Assignments turned in early will be rewarded; those turned in late will be penalized. Here's the breakdown:

To be clear, assignments turned in more than 24 hours late will be marked as zeros.

You will have the opportunity to resubmit up to two assignments throughout the term, after you get feedback on them. There will be a separate due date for resubmission. Your resubmitted work will be graded, and the final grade for the assignment will be the average of the grades on the original submission and the resubmission.

In addition, several homework assignments in the second half of the course are designated on the schedule (with an asterisk after their ID) as “leave-one-out” assignments. Out of this set of assignments, you may skip exactly one during the term.

This scheme is designed to eliminate the distinction between “legitimate” and “illegitimate” late or missing submissions. Unless something truly extraordinary happens, there will be no extensions given. If you turn something in late, no explanation is necessary or desired.

Learning and coding are both collaborative arts, and you are encouraged to work together with your classmates.

For some programming assignments, you will be assigned a partner to work with. You and your partner should engage in the pair programming model: Both of you should be sitting at a single machine, side by side. One student should be “driving” (that is, using the keyboard and mouse) and the other should be following along, providing ideas, looking for bugs. Make sure that each partner gets a relatively equal chance to drive.

There will also be individual assignments that you will complete on your own. You are permitted to collaborate with others in the class for ideas and to help solve problems, but the solution should be your own.

Collaboration and Plagiarism

There are two kinds of working together: Collaboration and Plagiarism. The former is encouraged; the latter is forbidden. But when you're starting out, it can be hard to tell the difference between them. The two essential distinctions have to do with transformation and attribution — the artifact (writing or code) that you submit must be entirely your own work (every last word of it), and if any ideas embodied in your work were provided or inspired by someone or something other than yourself, you must cite this source.

Plagiarism is the process of (intentionally or unintentionally) presenting the work of someone else in such a way that a reader might assume it was your own. Here are some examples — note that this list is non-exhaustive:

• Copying someone else's code, changing the variables and comments around, putting your name at the top, and turning it in.
• Finding code on the internet to do a particular task, changing the variables and comments around, putting your name at the top, and turning it in.
• Finding code in a book to do a particular task, changing the variables and comments around, putting your name at the top, and turning it in.

We'll talk about these in more detail during class, but if you have any uncertainty about a particular instance of working together, make sure to check with me first.

I am obligated by Carleton policy to report to the Dean of Students any suspected plagiarism or violations of the College's academic integrity policy. The Dean, in turn, brings it to the Academic Standing Committee. The academic penalty for a finding of responsibility can range from a grade of zero in the specific assignment to an F for the course. Please familiarize yourself, if you haven't already, with the Dean of the College's detailed guide to academic integrity.