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” 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, more-or-less following the book's chapter order. This includes (not exactly in this order):

• a Java primer;
• bags, stacks, queues, lists, dicts, trees, heaps, and graphs; and
• computational efficiency, recursion, sorting, and hashing.

For more details, please see the schedule page, which will be kept up-to-date as I adjust the schedule throughout the course.

• Attendance / Presence. I expect that you will attend every class meeting — missing class is not acceptable. I'll have some sort of weird scheme for taking attendance; more details about this on the first day. “Presence” is more than just physically being there. Turn off your phone, do not text during class, do not use a laptop for non-note-taking purposes, 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. My goal for this class is to get you to understand the material (and to love it if possible!), so it's sort of pointless for me to be there droning on to a room full of confused and silent faces. There are other resources available to help you (see below), but liberally asking questions in class is usually the best way.
• Readings. Read the book! There will be a (relatively) short reading assigned at the end of each class session that I will expect you to read before the next one. Furthermore, the book does a great job explaining things, so I highly recommend it for studying after the fact. If you’re struggling with a concept, it may be useful to actually code up the relevant structures.
• Homework. There are homework assignments due approximately every other class session, more densely packed toward the beginning of the term.
• Quizzes and Exam. There are four quizzes distributed throughout the term, plus a final exam. If you need accommodations for test-taking because of a disability, please contact me early and we will make appropriate arrangements.

Each programming assignment will be a team assignment or an individual assignment.

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. More on this in the Collaboration Policy below.

• Yourself. If you're stuck on a problem or struggling with a concept from class, take a break and think about something else for a few hours and then try a fresh start. Go through any code you've written line-by-line and simulate the results in your head or on paper. Draw diagrams to help you figure out what's going on. If you haven't written code for something, consider doing so.
• The book (or another book, or Wikipedia). Our textbook is great and it's a very useful place to turn if you're having trouble. Take a shot at the self-test exercises you'll find in each chapter, and compare your answers to those at the end of the chapter. You may find that other textbooks jive better with your way of thinking; check the library. Wikipedia is also a great resource for this course, though the language can get needlessly technical and the terminology that Wikipedia articles use may not match that of our book.
• A teddy bear (or imaginary expert). Seriously! This idea is also known as rubber ducking. When you have a problem, describe it out loud to a teddy bear, or draft an email to a smart person you respect. You'll have to explain the context and particulars of the problem, what you've tried, and why you think what you did doesn't work. In the case of the teddy bear, this is because teddy bears don't generally know a lot of computer science; in the case of the expert, you'll want to be sure to avoid wasting their time by asking about something you haven't really thought through. 90% of the time, you'll find that in the process of explaining your problem to someone else, you realize exactly what the solution is. I still use this trick pretty often, and it's very reliable.
• The course forum. Our Moodle has a forum set up; if you've written a teddy-bear explanation and you're still confused, go ahead and post it to the course forum. Don't worry about being too verbose in your writing; better to be really clear than to leave things out.
• Your classmates. You are each other’s best resource: talking through the course material with someone else who is also trying to master it is a great way for you both to learn. (And don’t discount the learning that you will do while trying to explain to a classmate an idea covered during class that you think you understand! Teaching to others really shows you where the gaps in your knowledge are.) The homework assignments are meant to challenge you, and figuring some of them out together is a great approach. That said, please pay close attention to the Collaboration Policy below.
• Me. My office hours are as follows:
  • Monday 2pm–3pm
  • Wednesday 3pm–4pm
  • Thursday 2:30pm–3:30pm
  • Friday 12pm–1pm

  At these times, you can be sure to find me in my office, CMC 320. I’m generally available most of the time from 9am to 5pm on those same days, except when I’m teaching. If you’d like to meet with me outside of my office hours, please check my calendar, email me 24 hours in advance, and propose at least two different meeting times that would work for you. I reserve Tuesdays and the weekends for research, so while I’ll try to answer any emails in a timely fashion during those times, I won’t be available for in-person meetings.

• The prefect. Will also holds regular office hours:
  • Tuesday 9pm–10pm in CMC209.
  • Sundays 8pm–9pm in CMC209.
• Other college resources. In this class, as with all classes at Carleton, there are a number of college-wide resources that can be of help. Use the library. Use the Write Place (written communication is an essential part of this course; when you “write up a solution” to a problem, you are writing!). Check out 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 who have taken this course and may be able to help. The Math Skills Center may be able to help you with some aspects of the course too. Finally, the college has a tutoring program available, which you can investigate if required.

Your grade will be computed as follows:

Assignments will be submitted via Moodle.

There will be 4 quizzes throughout the course, and you will be able to drop your lowest quiz score. The quizzes will focus on recent topics, but may include all topics up to that point in the course.

The final will be a comprehensive exam.

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.

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 72 hours late will receive no credit.

You are expected to maintain the utmost level of academic integrity in the course. Any violation of the code of academic integrity will result in severe punishment, which may include receiving a failing grade in the course or even dismissal from the college. Academic dishonesty has no place in an institute of higher learning; it wastes my time and yours.

Please familiarize yourself, if you haven't already, with the College's academic integrity policy and the Dean of the College's detailed guide to academic integrity.

My motivation for the course’s collaboration policy, which is below, is as follows. I am a major proponent of you learning from each other in a course like this one, and I strongly encourage you to work together in attacking homework exercises. Students who think about problems together almost always learn more and find difficult problems less frustrating than those who work alone. However, there is a major difference between, on the one hand, thinking about and solving a question as a group (which is good, both educationally and morally); and, on the other hand, copying an answer from someone else or giving a answer to someone else to copy (which is bad, educationally and morally, and has punitive consequences). The policy below is formulated to encourage the former while banning the latter.

I am obligated by the Faculty Handbook to report any suspected violations to the Dean’s office. Any student who is found responsible for academic dishonesty in this class will receive an F for the course.

If you have any doubt about any aspect of this policy, ask beforehand!