ICS 46 Spring 2022
Project Guide


The projects


Introduction

This quarter, much of your focus will be on the programming projects found here. While this is a course that is partly about the analysis of data structures and algorithms — understanding how well things work, at a level above the low-level implementation details — it is also a course about their implementation, and these projects will focus your attention on the implementation side. Building on your work in ICS 45C (or related coursework elsewhere), all of these projects will be written entirely in C++. Some of them will require you to master new C++ skills beyond what was taught in ICS 45C, but having completed ICS 45C (or an equivalent course), you should find yourself able to adapt and grow to meet this course's needs. If you've never programmed in C++ before, or if you've had only a very light introduction, you may find yourself overmatched here, and it would be wise for you to take ICS 45C before taking this course.

Note that C++ programming requires a level of care and attention to detail that exceeds what you may have experienced in languages you've used previously, requiring a dual focus on both higher-level abstractions and low-level implementation details that many languages hide and/or handle automatically, though a focus on these kinds of details is an important part of the kind of work we're doing here, regardless of programming language.

Each of these projects focuses on one particular kind of algorithm or data structure, though each attempts to place that underlying problem into a broader, more interesting context. I hope you'll find these projects interesting and exciting, and that you'll discover at the end of the quarter that you've built skills and continued to broaden and deepen your programming skills.


Evaluation of your work

Evaluation criteria

Each of your projects will be graded on a 30-point scale, with the points split (albeit unevenly) into two categories: correctness and robustness (i.e., does the program work?) and quality and design (i.e., how well is the program written?). They are described in more detail below.

Criteria Value Description
Correctness and Robustness 20 points
  • Summary: Does the program do what it's supposed to do for any input that meets the project specifications?
  • When the program is given valid input, does it generate the output specified?
  • Is the output spacing and case correct, if these are specified?
  • When the program is given unusual or erroneous input, and the project write-up doesn't specifically forbid us from testing it, is it handled gracefully?
  • Are all resources allocated by the program (e.g., memory, open files) released before the program ends?
Quality and Design 10 points
  • Summary: Strive to write a clear, well-organized, readable, modifiable program.
  • Your program should be divided into logical parts, each encapsulating a single task or idea.
  • Large functions or classes should be broken up into smaller ones that do simpler jobs.
  • Identifier names should be chosen to reflect their objective; the names should be meaningful to the reader.
  • Comments should be included where necessary to introduce clarity for the reader (though it should be noted that good modularity and well-named identifiers make the commenting burden significantly lighter).
  • Any other rules and/or limitations specified in the project write-up should have been followed.
TOTAL 30 points

Re-evaluation of your work

As projects are graded, you will receive scores and feedback on each in an email from your TA or a reader. If you believe that you've been graded unfairly, your first move is to contact the TA or reader who graded the work and discuss the issue with him or her directly, as that person is more familiar with the details of the grading of your work than I would be — the first thing I usually do is to contact that person, anyway. Most issues are resolved this way. Note that we do not reconsider the rubric used to grade your work afterward, but if it was applied unfairly or incorrectly, we can consider an adjustment.

If, after this, you still believe that you haven't been treated fairly, you are welcome to raise the issue with me and I can arbitrate, though I should point out that it is relatively rare that I overrule a TA's judgment. I've communicated a fair amount with the TAs about grading ahead of time, so they're generally acting on my instructions, so I don't find very often that I think a TA has graded work unfairly.

Note, also, that we will not be willing to regrade your work by having you demonstrate it on your own laptop or device. We are only willing to grade what was submitted before the deadline, and we are only willing to grade your work in the way that we graded everyone else's, which means we must retain control over what files we grade and in what environment we grade them.

Code that does not compile

If you submit a program that does not compile, we will not be able to execute it and, thus, will not be able to evaluate its correctness. It is your responsibility to turn in code that compiles, and it's important that it compiles in the development environment specified for this course — more about that below. Though we will make an honest effort to assess its overall correctness and quality, we can, at our discretion, assign a score as low as zero to a program that does not compile, and you can assume that your score on such a program will not necessarily apporach the percentage of completeness and correctness you actually achieved, as it is impossible for us to measure that without being able to run and test your program.

At the level of experience that is assumed of you, you should be able to ensure that code compiles, even in a partially-completed program; you should be able to work incrementally, save copies when you reach stable state, and so on. You might also consider using a source control tool like Git, which helps you to formalize this kind of incremental work, though this is not required. If you've never used a source control tool before, it would be worth the effort spent to learn about one; given its flexibility and popularity in professional and open source circles, Git is a very good choice. If you prefer something else, feel free to use it. (Git is installed on the ICS 46 VM, but you can install other systems on to the VM pretty easily if you're so inclined.)


Late work

Things happen and ten-week quarters can be unforgiving. It's not unreasonable to expect that you may find it difficult to finish one of the projects on time, even if you're on top of things most of the time. I get emails often from students, saying things like If I just had one more day to work on this, I'd get it done! On the other hand, being consistently behind is a recipe for struggle in this course; we'll be moving quickly, and it will be progressively harder to catch up the farther behind you get.

The best balance between these two realities is that everyone is allowed to have a tough time with a project once this quarter with no penalty — maybe you underestimated the difficulty of an assignment, maybe you have three midterms and a paper due the same day, maybe you have a sudden outside commitment that can't be avoided. However, we generally require you to keep up with the due dates as assigned, and we do generally assign a penalty for work submitted late.

Submitting late work

Aside from the "one-time" late submission, described below, late work is accepted according to the following policy:

Full or partial hours are counted. So, for example, a project submitted at 3:15am the morning after an 11:59pm deadline would be subject to a 4% penalty, because it was submitted 3-1/4 hours late (i.e., three full hours plus a partial one). In that example, if your score on the project would have been 27/30 ordinarily, it will be reduced by 4% and become 25.92/30 instead.

This means, in general, that a project submission has at least some value for 99 hours beyond the stated deadline. At the 100th hour, the project has no value remaining.

The "one-time" late submission

To accommodate the occasional unforeseen issue, we do also allow a "one-time" late submission:

For the purposes of clarification, here are some additional details about how this policy works.

In general, this procedure is automatic and does not require negotiation or notification; we will apply this consistently to everyone as described above. The goal is that this should accommodate the unforeseen issues that might otherwise prevent you from finishing a project on time, while freeing course staff to focus on helping students to learn and improve.

Does this policy apply to Project #0?

Project #0 is not covered at all under this policy. It must be submitted when due in order to be considered at all.

Does this policy apply to the reinforcement exercises?

No. The reason for the reinforcement exercises is to keep you on track as we proceed through the course, so those are also not covered by the late policy.

What to do if you're chronically late

Out-of-the-ordinary circumstances sometimes warrant exceptions to this policy; if you are faced with a problem that is preventing you from getting your work done on time, either on a single project or chronically, please contact me and we can talk about how best to approach the problem. It's important to contact me sooner rather than later; earlier in the quarter, there are a lot more things I can do to help than there are in the tenth week or after the final course grades are determined.


Development environment

Unlike programming languages such as Java or Python, which make it a point to be (more or less) independent of the hardware and the operating system that they run on, C++ is decidedly platform-dependent. This is especially true in recent years, as four new versions of the C++ Standard 9called C++11, C++14, C++17, and C++20) have been completed, but not all compiler implementers have implemented all of the new features of the language yet (and library support is even more hit-or-miss). And even amongst the features that all compilers share, there are differences — all the way down to details such as the maximum value you can store in a variable of type int — that make it important for us to agree on a single development environment: a particular compiler running on a particular version of a particular operating system.

Because not every one of you will be running the same operating system on your own machine, and to avoid the problem of having each of you install and configure the necessary software yourselves, the officially-supported development environment for ICS 46 is provided in the form of a virtual machine, a complete environment that includes an operating system, compiler, debugger, text editors, and so on; we'll call this the ICS 46 VM. Rather than installing software, you'll download the ICS 46 VM and run it as an application on your computer, but log into it as though it was a separate computer. This is explained in more detail in Project #0, which describes how to download it and set it up for use.

What if I don't want to use the ICS 46 VM?

You should be aware that at least some of the project work this quarter will require the ICS 46 VM — it may be possible to work around it, but you might find that it's a lot of work, and we won't be able to support you in it. While everything we do this quarter will be standard C++17, I'll be using third-party libraries (e.g., a GUI library called Qt, a few of the Boost libraries) and I'll sometimes be providing you code in compiled form rather than giving you source code, so you can easily focus your efforts only on the parts of the program that are important. Incompatibilities between compilers, linkers, and operating systems will likely make it difficult or impossible to use that pre-compiled code on machines other than the ICS 46 VM, and I'm making no attempt to ensure that it will run anywhere else. So, in general, you can use whatever you want, but you might find it a very difficult thing to do; your best bet is to acclimate yourself to the ICS 46 VM.

Be aware that we will be grading your work using the ICS 46 VM, so, at minimum, you should always test your projects in the ICS 46 VM before submitting your work. Submitting work that compiles on your favorite compiler but not in the ICS 46 VM is viewed the same as any other work that does not compile at all; as when you work for (or with) someone else professionally, you don't always get to choose your favorite environment to work in, but instead must adapt to what is appropriate to the situation. Additionally, be aware that you're on your own to get software other than the ICS 46 VM set up and configured; we can't realistically support everyone's separate home installation, whereas the ICS 46 VM gives us a single system to support.

Also (and especially if you've never used Linux before or spent a lot of time on a command line), you should consider the practical usefulness of learning new skills that will no doubt prove to be valuable as you pursue professional and academic options further down the line. Trying out something new while having the safety net of a large course staff to help you is a lot better than struggling with it on your own. Even if only for that reason, I'd strongly encourage you to use the ICS 46 VM for all of your work, even if it seems like a difficult transition at first. Linux and command lines are an important part of real-world computing, and you would be wise to gain some experience with them.

What I want to use a previous ICS 45C VM instead?

Unfortunately, the ICS 45C VM from a previous iteration of ICS 45C is unlikely to work for you this quarter, as the set of software installed this quarter is not the same, and since the ICS 45C VM contained scripts and templates specific to that course. You'll need to obtain the ICS 46 VM and use it, though you'll find it a familiar environment, as it's based on the same version of Linux and its configuration is similar.


Submitting your projects

When you complete each project, you must submit it to us electronically on Canvas. Understand that we will only accept projects submitted to the appropriate dropbox (for the appropriate assignment) on Canvas; we do not accept printed copies of your projects, nor do we accept them via email or other means under any circumstances.

You are responsible for submitting the version of your project that you want graded. We will grade the most recent submission made before the deadline. Accidentally submitting the wrong version, nor is there any remedy (outside of the late policy described above) for forgetting to submit your work at all.


Academic honesty

The policy

As ICS 46 students, you are expected to know and follow the academic honesty policies of both the Bren School of ICS and the University as a whole. Please take a few minutes to read the policies, which can be found at this link.

All of your work on projects and reinforcement exercises is expected to be completed solely by you. Working in larger groups and/or sharing of code between students is not permitted. Note that "high-level discussion of course material for better understanding" is permitted and encouraged, but when it comes time to sit down and write code, that is expected to be done by you and you alone. All submissions are compared to one another using an automated plagiarism detection system. This system is extraordinarily good at finding similarities between submissions, even when there are superficial differences. (Note that we also compare your submissions to those submitted during previous quarters whenever one of these assignments was given during a previous quarter, so it is an exceedingly bad idea to turn in, or even refer to, code written by a friend of yours who took the course already.)

Since all of your work is expected to be completed solely by you, you will be held responsible even if you plagiarize only a small portion of someone else's work.

Academic honesty is a two-way street. Providing your code to other students for them to turn in as their own is not permitted any more than turning in someone else's code. Resist the temptation to give code to your friends "for reference." Based on my experience, I can say that your "friends" may very well betray you and turn it in, anyway, and then you'll have a lot to answer for.

Naturally, the Final Exam is also expected to be an individual effort. Dishonest behavior during an exam will not be tolerated.

All violations of academic honesty policies will be reported to the UCI Office of Academic Integrity & Student Conduct (AISC) and will trigger an administrative procedure, which is described on their web site. Additionally (and at least as importantly), you can receive a course grade of F — as a number of students in my courses do, because of this issue, every quarter — without the option to drop the course to avoid the grade. A single documented case of academic dishonesty may also have other ramificiations, such as precluding you from switching into computing majors, registering for computing minors, joining the ICS Honors Program, and graduating from a computing major with honors. All of this is University and Bren School of ICS policy and is not subject to negotiation.

Knowing when you're being dishonest

I've been asked by students how they know when they're crossed the line between asking for help and being academically dishonest. To me, there is a fairly straightforward way to know the difference. Did you actually write the code in question? That's not a matter of whether you typed it in; that's a matter of whether it was you who wrote it (i.e., it is comprised of your own ideas about how to solve the problem, how to organize the solution, and so on).

The easiest way to determine whether you've crossed the line is whether your work was driven by someone else's existing solution. Here are some examples:

In my view, this really isn't that complicated. We require you to do your own work, because that's how the learning is done in this course. A large part of what you're learning to do is to design and write programs, a skill that can only be built by designing and writing programs. You have to make the decisions about what to do next, how to organize your program, and so on. If someone else is making most of those decisions for you, you're not building the skills necessary to be ready for the courses that follow on from this one. And, from the standpoint of academic honesty, if someone else is making most of those decisions for you, that's plagiarism.

The lesson

Okay, so the moral of the story is that it's wise to avoid cheating. I believe that it's relatively rare that students enter a course with the conscious intent to cheat their way through it; why come to UCI if you're not planning to get something out of the coursework? So why do people cheat every quarter in every course? The answers vary, but here's the easiest way I can boil down the numerous conversations I've had with students caught cheating in my courses over the years: I fell behind and couldn't figure out how to catch up. Things happen and ten-week quarters are unforgiving. You might get sick, you might have issues crop up in your family, you might have misunderstood one of the earlier topics in this course (or one or more important topics in previous coursework) on which later topics depended, you might have an off-campus job that's demanding too much of your time, you might be trying to decide whether you're on the overall life path you want to be on... Any of those things (and many others) can make it hard to keep up. You fall a little behind, you fall a little further behind, and pretty soon the situation seems hopeless. You're under pressure, temptation gets the better of you, and suddenly it seems better to submit someone else's work than to submit nothing. As upwards of 10% of my students (who have cheated like this) can attest, it's not.

If you feel like you're beginning to slip off course or things are getting beyond your control, the best thing to do is to talk to us sooner rather than later. We're here to help; we understand. But the reality of taking large-sized courses at a large-sized institution is that we're not going to know you're in need unless you tell us. If things are happening in your life, tell us; you don't have to be specific if you're not comfortable with it. Before the fact, there's often a way to work things out. After the fact, it's usually too late.

And, in general, some students won't pass this course with a C or better this quarter, and won't be ready to take follow-on courses yet. And that's not as disastrous as it sounds. Most students who get less than a C in ICS 46 take the course again; most of those who take the course again pass it the second time around, with their feet firmly underneath them and ready to move forward.

Sharing your own solutions online

Some of our past students have wanted to post their own solutions to their projects online, with the goal of helping others or just showing off work that they were proud of. This is also problematic from an academic honesty perspective, because many or all of the projects you're working on will be reused in a future quarter; good problems are good problems, and I don't rebuild five new projects every quarter. Given that, posting your prior work online will absolutely lead to other students finding it and plagiarizing it — this is now one of the more common root causes of plagiarism cases that we find.

I can appreciate, of course, that you might want to build a portfolio of work to demonstrate your skills as you build them, and I'm not unsympathetic about that. However, the reality is that posting solutions to first-year coursework is very unlikely to be of use in job searches or other professional scenarios. I've asked a number of hiring managers over the years, including ones I've worked for in my industry career, and have universally received the same response about it: Hiring managers generally aren't interested in seeing prior homework. Projects in courses like this one are sanitized, in the sense that they're problems that have been designed to be solved using techniques just taught, with the requirements clearly spelled out, and with few enough rough edges that a large number of students can solve them without encountering roadblocks that can't be overcome. Real-world work isn't like this, as it turns out. Figuring out what needs to be built is as important as figuring out how to build it. Building a portfolio is best done with your own solutions to your own problems, containing things you've written to scratch your own technology itches or explore concepts that you wanted to learn more about on your own.

So, in general, despite the fact that you may be proud of the work you've done, you need to understand that there is a very strong likelihood that the only thing you'll be doing is enabling future students to plagiarize your work — and quite possibly becoming embroiled in the investigation yourself and being reported to AISC — while not accomplishing much of anything positive for youself.

Do not share your prior solutions online.