CS 200: Data Structures with Problem Solving

Table of Contents

Course overview

“There must have been a better way to do that last assignment from Intro to CS…”

Data Structures is all about patterns in trying to organize information. All of the software that we create uses data, in one form or another. There are smart ways to store and retrieve this information. How can you do so, and how can you quantify how efficient your techniques are?

Course information

  • Professor: Dave Musicant
  • Educational Associate: Quoc Nguyen
  • Prefect: Thea Traw
  • Teaching Assistants: Colin James, Tony Ni

Textbook

OpenDSA, which is a free online configurable textbook. I will include links to the readings within Moodle.

Communication

We’ve got a variety of ways of communicating with each other.

  • In class! Bring general questions to class and I can answer for everyone.
  • Student hours. I will be holding student hours in person; there is a link on the Moodle site for times that I will be available. You can find it in the “Course Blocks” section of the Moodle site; there’s a link for that on the top-right.
  • I will use Moodle announcements for all general purpose announcements to the entire class. There will be a link for signing up in the first assignment. You will get an email copy of those announcements, and they are also kept in the Moodle announcements forum if you want to see them again later.
  • You should also use the Moodle Q&A forum for any questions related to the course. Please do so rather than emailing me, unless your question is of a personal nature (such as relating to your grade, or something like that). By posting your questions publicly, it’s like asking in class, and everyone in the class can benefit from the answer. Please also pitch in and help each other out: if you know the answer to someone else’s question, please go ahead and answer it. If you wish, you can post a question anonymously so that other students in the class can’t see who it was. Please use this sparingly, though; conversation tends to drop in quality if too much of it is anonymous.
  • Frequency of communication: you should check the course Moodle site and your email at least once a day. I’ll be checking Moodle and my email, and responding to people, three times a day: once early in the morning (likely before 8am), once roughly in the middle of the day (sometime 11am-2pm), and once near the end of the working day (sometime 4pm-6pm). I’ll be less reliable on weekends. When engaging with course activities online, always use your Carleton Gmail/Google account rather than personal accounts.

What you will be doing

You’ll first learn to program in Java, and then we will learn a variety of ways of efficiently managing data structures within Java. We’ll be doing this through in-class group work and out-of-class exercises, both of which will involve a mixture of worksheets and programming. To accomplish this, you’ll be doing a number of things:

  • Participating in class!
  • Doing programming assignments. I’ll have assignments posted to Moodle, with deadlines attached to them. You’ll need to submit those. Some of them will be individualized, and some of them will be done via pair programming. Either way, you can still talk with others about the assignment, and get help.
  • Doing worksheets. Many of these will be done in groups in class.
  • Reading the textbook.
  • Taking in-class exams. The key goal of exams is to check in that you can accomplish the goals of the class without needing help from others to be able to do it.

Grading

Grading for this course will be based on your performance on:

  • submitted assignments
  • participation on in-class worksheets
  • in-class exams

Here are some more details on each, and then how the results will be combined.

Assignments

Each assignment that you submit will receive one of these grades.

  • Exceeds expectations (E). All aspects of specified functionality are working correctly.
  • Meets expectations (M). The core functionality of the assignment has been correctly completed, but one or more of the exceeds-level aspects may not be working correctly.
  • Partially meets expectations (P). The assigned task has been partially completed to a level indicated some understanding of the concepts, but the core required functionality has not been completely achieved. It is clear that the core goal of the assignment is there and is on its way to being accomplished, though it may not be completely correct.
  • Beginnings (B). The work is not complete enough to indicate that a baseline level of correctness has been achieved. This likely applies when the work has very large gaps in functionality or in implementation. A significant number of the automated tests (or possibly all of them) do not work. Nonetheless, the work submitted demonstrates that real progress has been made towards solution of the problem.
  • Not assessable (N). The work was not submitted, or shows a deep disconnect with what was assigned.

For some programming assignments, correctness may be determined based on a set of automated tests that will be provided, as well as some style guidelines. This way, you know mostly, but not entirely, what your grade will be when you submit your work. (The key exceptions will be that we will review your code to verify that you haven’t tailored your code too directly to the specific tests that we have written, and we will be looking for well constructed code.)

Resubmission of your work for regrading is sometimes permitted, but only for two specific circumstances:

  • If a grader finds something problematic in your submission that wasn’t revealed by the automated tests (so you wouldn’t have known about it before submitting), you may resubmit to try to resolve that issue.
  • You may resubmit later to try to receive a grade of E (exceeds expectations) if your assignment got a grade of M on the first submission.

See the late policy below regarding how resubmissions factor into late work.

Gradescope and Moodle will show an E as a 4, an M as a 3, and so on.

In-class worksheets

The in-class worksheets provide an opportunity to practice and learn the new contest as we’re working on it. These will not be graded for correctness, but we will verify that you are participating in them in good faith. You will get a grade of “Satisfactory” for each worksheet that you participated in if a clear attempt was made to work on it. We will then calculate on a 4.0 scale a total worksheet grade: it will be the fraction of worksheets you got a grade of satisfactory on, multiplied by 4.0.

In-class exams

The in-class exams will have a variety of 4-point problems, each of which are targeted to test a particular learning objective for the course. They will be a mixture of shorter programming tasks, or conceptual questions that could appear as mini-essays, short answers, multiple choice, or other possibilities.

There will be a total of 5 in-class exams. The first four will be during the term. The last will be during the final exam period, and will have two parts:

  • The first part will be designed to last for 60-70 minutes, and will test on new material just like the tests. This first part will be weighted the same as each of the other four regular exams. In other words, it’s just a fifth exam.
  • The second part will be optional, and will contain new versions of questions from the previous four tests. (You may have to sign up in advance regarding which questions you retake; we’ll work that out when we get close to the exam.) You can retake any of these questions to improve your grade from previous tests. The final exam schedule gives us a total of 150 minutes. I will be designing part 1 of the same length as the other exams (60-70 minutes), so you’ll have 80-90 more minutes to retake any questions that you wish. That said, I can’t micromanage your time during the exam, so in practice you’ve simply got 150 minutes to allocate between the two parts as you choose. Note that there will be no opportunity to retake any questions from part 1 of the last exam.

Your aggregate grade

Each row in the table below shows the criteria you need to achieve in order to receive that grade. You need to achieve all of the items in a given row in order to earn that grade; each row is an “and”, not an “or”. For example, in order to get a B, you need to have fewer than 2 assignments with a grade of less than P, fewer than 3 assignments with a grade of less than M, and an average on worksheets and exams of at least 2.67 for each.

grade assignments < P assignments < M assignments < E worksheet/exam threshold
D- 9 10   0.33
D 8 9   0.67
D+ 7 8   1.00
C- 6 7   1.33
C 5 6   1.67
C+ 4 5   2.00
B- 3 4   2.33
B 2 3   2.67
B+ 1 2   3.00
A- 0 1 3 3.33
A 0 0 2 3.67

Late policy

Assignments

Every assignment will have a due date associated with it. You have a quota of 7 assignment late days that you may use throughout the term if you like. This means that you can submit 7 assignments one day late each, or a single assignment 7 days late. Moodle does not have any automatic way of keeping track of these late assignment days, but we will review your assignment submissions on a regular basis and keep a somewhat out-of-date inventory in Moodle. Once your 7 assignment late days are used up, you will no longer be able to submit any more assignments late.

Resubmissions will be relatively rare because autotesting will often inform you if you need to keep working before submit, but…

  • If a grader does invite you to resubmit because of something that you wouldn’t have known about before submitting, you begin accruing late days starting from when you heard back from the grader.
  • If you resubmit in order to try to pass the E tests after having passed the M tests on the first submission, you begin accruing late days for that E submission starting from when you make the M submission.

Petitioning for additional late days

You may petition for more late days if need be, but to do so you will need to contact me directly, explain what went wrong, why you need more, and what you will be doing differently to not end up in the same situation again. I want to be able to work with students to help them recover from mistakes or things that went wrong, but I also can’t arbitrarily grant unlimited late days.

In-person class

This is an in-person class, and we learn a lot by being in a room together. There are a variety of reasons that may pop up for which you might not be able to attend class in person. These include being ill, family emergencies, job interviews, and essentially any other reason why you might not be able to attend in person. If you do miss class, there are many ways of catching up on the material:

  • Most importantly, you should check with someone else in the class to get a personal description of what we covered and what we missed. If you can get ahold of one of your in-class group members or someone else before class, you can give them an extra heads-up that you’ll be looking for info on how class went. It is best to plan ahead for this even before any reason comes up why you might miss class; talk to someone and work out what your plan might be if you need one.
  • Any code I write in class will be synchronized online for reviewing afterwards.
  • I’ll post all worksheets to Moodle.
  • I’m happy to answer any specific questions or clarifications in lab hours.

In general, I won’t be simulcasting class over Zoom. My experience is that doing so is sometimes critically necessary, but it reduces the quality of the experience for the rest of the class when I do. Contact me if you believe that a special exception needs to be made.

How to get help

There are lots of resources for help in this course!

  • I have student hours.
  • We have a course prefect, who will hold prefect sessions.
  • We have lab assistants with expertise in this course, who will be holding lab assistant hours.
  • We have the Q&A platform on Moodle.

Working together

  • Each programming assignment will either be a “paired” problem assignment or an “individual” assignment.
  • When working on paired assignments, you and your partner should engage in the pair programming model. One of you is “driving,” i.e. actually using the keyboard and mouse. The other is actively engaged following along, stopping bugs, and providing ideas. I generally expect that you are doing this side-by-side, in person. If you are not and are remotely sharing a screen, you should use Zoom, Google Hangouts, Facetime, a phone call, or some other voice approach for communicating while working. You should make sure that over the course of an assignment that you spend roughly the same amount of time each “driving.” This means, for example, that if you are sharing your screen, then you swap whose screen is being shared every 15 minutes. I will also ask you to turn in a form rating the work that your partner does.
  • Working alone on the paired assignments is also ok. You can change whether or not you work alone each “cycle” that I assign new partners.
  • On non-programming assignments, you may collaborate with others in the class for ideas. In some cases, we may even start working on them in larger groups in class. That said, you should nonetheless take the time to write up your own responses to the questions rather than just copying from the group answers you may have constructed in class.

Plagiarism and appropriate use of other materials

Collaborating is good. Learning is often a social effort. However, it is important that you don’t slip into plagiarizing the work of others, or inappropriate use of work by others, each of which are explained below.

Plagiarism is when someone submits work that isn’t theirs, but that person nonetheless takes credit for doing so. It’s unethical, because you’re taking work that someone else has done and claiming that it’s yours.

Inappropriate use of work by others is when someone submits work by others that is correctly cited (which is good), but the quantity of work taken is inappropriate because it defeats the entire purpose of the assignment.

Here are two quick contrasting examples:

  • If someone submits a program that they didn’t write themselves, and they don’t cite it, that’s plagiarism. This is because by not citing it, that student is implicitly taking credit for it for having written it themselves.
  • If someone submits a program that they didn’t write themselves, but they do cite it, that’s inappropriate use of work by others. This is because the student didn’t actually do the goals specified by the assignment. But because it was correctly cited, it isn’t plagiarism.

Inappropriate use of work by others gets in the way of students learning and achieving the goals of the course. It is generally acceptable to include small amounts of materials found elsewhere when cited correctly, and there’s some more specific information about that below. But the general principle is that the wholesale use of materials found elsewhere and submitted for assignments is not permitted, and results in an assignment receiving a low grade.

Plagiarism is problematic for all of the reasons that inappropriate work by others is, but it is also unethical, illegal, and a violation of the college academic integrity policy. If plagiarism happens, I am compelled by Carleton policy to notify the Academic Standing Committee. The academic penalty for a first offense is determined jointly between me and the Academic Standing Committee, and will likely result in a reduction of the final course grade. Furthermore, the college retains a record of the incident, and may respond with suspension or other sanctions on repeat occurrences.

In short, inappropriate use of work is considered as a poor submission, and is graded accordingly. Plagiarism is a deeper infraction that results in college-level disciplinary action. Students shouldn’t engage in either, but plagiarism is considerably worse.

The good news is that avoiding plagiarism is very easy. If you use work that isn’t yours, CITE IT. If you turn in an entire assignment with code that you got from the somewhere else, and you cite it, at least it isn’t plagiarism.

Can you safely use any uncited materials at all? What about a single word, or examples from class?

Most importantly: if you’re unsure, just ask me. I’m happy to help!

Your default view should be that if you use code or materials from elsewhere, you should cite it.

One exception is that you may use any code or materials that I supply without citation. It is understood that any code I write or provide for this class is done so with the intention that you can use it and/or modify it. Likewise, any concepts, definitions, and theory are intended as a starting point for learning. This includes starter code that I give you for the assignments, but also any code or other materials that I supply in lectures, class worksheets, or the like.

If you find materials anywhere else (StackOverflow, ChatGPT, etc.), you must cite it unless it is exceedingly short. Exceedingly short means perhaps less than three lines of code. Regardless, you should not be looking for code that solves the actual goals of the assignment, as this would be inappropriate use of work by others.

How do you cite material you find elsewhere?

Citing for purposes of this course is easy. If you find it online, add a comment to the code or materials with the URL where you found it. If you find it in a book, put in a comment with the title and author of the book. If it is something that is not findable (i.e., something shared from a person, or an AI tool), put the name of the person/tool in the comment. We’re not writing a research paper, so you don’t need to spend time with carefully formatted bibliography styles. The key point that matters is simply making clear what the source of the material is.

What if you modify the content that you find?

If you are using an idea based on code you find elsewhere, you still must cite it. Taking code that you find online and modifying the variable names, for example, is still plagiarism if you don’t cite it.

How does this apply to things other than code?

If you submit an idea from somewhere else, you must cite it. This applies for example to definitions, explanations, and conclusions that you find elsewhere, either online or from other people.

Assuming you cite everything correctly, how much is inappropriate use of work by others?

Again, if you have any concerns about this, just ask me and I’m happy to clarify in any particular case.

The answer to this varies based on the assignment, and hinges on what the goals of the assignment are. Anything I say here may be superseded by a particular assignment, but here is the philosophy.

The goal of an assignment is for you to accomplish the tasks specified. Of course, you may get help from others — either people, AI tools, or reference sources — to help understand the challenges within. However, you should be assembling these pieces yourself in your own way to accomplish the tasks at hand. If you submit correctly cited work by others that accomplishes the assignment as a whole, or a significant fraction of it, then you are not accomplishing the goals of the assignment, and that is inappropriate work by others. Ask, and I’m always happy to clarify.

How do AI text and code generators fit in?

AI text and code generators (often referred to as Large Language Models or LLMs) such as ChatGPT, Google Bard, GitHub Copilot, and others can generate considerable text and/or code. It’s the case that you can ask ChatGPT to produce complete solutions for many of the homework assignments in this class, and it will reasonably do so. That’s in part because there’s so much code already online that does these sorts of activities, and so ChatGPT can easily assemble such code together.

We are all currently exploring together what it means to learn in a new world with these tools. Here are some ideas that are contributing to how I have designed the course.

  • LLMs are great at producing solutions that combine aspects of previously solved problems. They are still helpful, but less so, when solving more complex novel problems. If we reach the point that LLMs can solve any programming task we want, then you’ve been automated out of a job and we’re in a different place than we are now. I am enthusiastic that our shared goal is to help you learn to be able to solve the larger challenging and innovative problems that humans will be needed to do for a long time to come.
  • In order to be able to solve these complex and challenging problems, you first need to understand how to solve the more basic versions of those first. Using LLMs to produce those solutions is quick, and you might be able to learn something by looking at aspects of those solutions, but if you just use those tools to produce solutions to more basic problems you will not be prepared to take on harder problems yourself.
  • Solving more challenging problems requires being able to reason about the ideas that go into them. The best way to get good at learning how to do that sort of reasoning is by struggling to solve simpler versions of those problems. Simply asking LLMs to solve those problems for you doesn’t help you get better at that form of reasoning, though they might be quite helpful at helping you get unstuck.

Therefore, it is my expectation that the goal for this class is to ultimately be able to solve the problems posed in this class yourself. In order to get there, you might perhaps choose to use LLMs while you’re learning the material when doing assignments. But final success in the course will be measured by your ability to succeed without the use of such tools.

To that end, your ultimate goal in this course is to be able to successfully answer the exam questions, which will be handwritten on paper. The best way for you to learn this material is to practice doing that on the assignments. It is my very strong recommendation that you do as much of the assignments as you can on paper, before having the computer do it for you. Alternatively, if you need the help of the computer at the initial stages while learning how to do these tasks, make sure that once you’ve learned it you are capable of writing the ideas out on paper. You should do this for each assignment when you do it, not only the night before an exam.

It is the policy of this course that you may use LLMs to help you learn ideas, provide explanations, and get small contributions to your code, but not to have them do significant portions of your assignments for you. That’s the same policy that applies to getting help from humans or any other online source.

To summarize:

  • LLMs might be useful to you in learning ideas, and you are welcome to use them if you find that to be the case, so long as you are using it to help prepare you to be able to succeed on your own without them.
  • Cite any content that you get from these tools beyond a couple of lines of code or English.
  • It’s inappropriate to use an LLM to contribute large amounts of content directly to your assignments.

Posting your work online

You are not permitted to post publicly online any of your solutions. If you wish to share your work with potential employers, you need to do so in some kind of private manner.