Assignment 0-1

Objectives

  • Analyze the algorithmic processes of everyday activities.
  • Learn to express yourself clearly and succinctly.
  • Become familiar with “pseudocode.”
  • Have fun experimenting with your peers’ algorithms.

Academic Honesty

This course’s philosophy on academic honesty is best stated as “be reasonable.” The course recognizes that interactions with classmates and others can facilitate mastery of the course’s material. However, there remains a line between enlisting the help of another and submitting the work of another. This policy characterizes both sides of that line.

The essence of all work that you submit to this course must be your own. Collaboration on problems is not permitted (unless explicitly stated otherwise) except to the extent that you may ask classmates and others for help so long as that help does not reduce to another doing your work for you. Generally speaking, when asking for help, you may show your code or writing to others, but you may not view theirs, so long as you and they respect this policy’s other constraints. Collaboration on quizzes and tests is not permitted at all. Collaboration on the final project is permitted to the extent prescribed by its specification.

Below are rules of thumb that (inexhaustively) characterize acts that the course considers reasonable and not reasonable. If in doubt as to whether some act is reasonable, do not commit it until you solicit and receive approval in writing from your instructor. If a violation of this policy is suspected and confirmed, your instructor reserves the right to impose local sanctions on top of any disciplinary outcome that may include an unsatisfactory or failing grade for work submitted or for the course itself.

Reasonable

  • Communicating with classmates about problems in English (or some other spoken language).
  • Discussing the course’s material with others in order to understand it better.
  • Helping a classmate identify a bug in his or her code, such as by viewing, compiling, or running his or her code, even on your own computer.
  • Incorporating snippets of code that you find online or elsewhere into your own code, provided that those snippets are not themselves solutions to assigned problems and that you cite the snippets’ origins.
  • Reviewing past years’ quizzes, tests, and solutions thereto.
  • Sending or showing code that you’ve written to someone, possibly a classmate, so that he or she might help you identify and fix a bug.
  • Sharing snippets of your own solutions to problems online so that others might help you identify and fix a bug or other issue.
  • Turning to the web or elsewhere for instruction beyond the course’s own, for references, and for solutions to technical difficulties, but not for outright solutions to problems or your own final project.
  • Whiteboarding solutions to problems with others using diagrams or pseudocode but not actual code.
  • Working with (and even paying) a tutor to help you with the course, provided the tutor does not do your work for you.

Not Reasonable

  • Accessing a solution to some problem prior to (re-)submitting your own.
  • Asking a classmate to see his or her solution to a problem before (re-)submitting your own.
  • Decompiling, deobfuscating, or disassembling the staff’s solutions to problems.
  • Failing to cite (as with comments) the origins of code, writing, or techniques that you discover outside of the course’s own lessons and integrate into your own work, even while respecting this policy’s other constraints.
  • Giving or showing to a classmate a solution to a problem when it is he or she, and not you, who is struggling to solve it.
  • Looking at another individual’s work during a quiz or test.
  • Paying or offering to pay an individual for work that you may submit as (part of) your own.
  • Providing or making available solutions to problems to individuals who might take this course in the future.
  • Searching for, soliciting, or viewing a quiz’s questions or answers prior to taking the quiz.
  • Searching for or soliciting outright solutions to problems online or elsewhere.
  • Splitting a problem’s workload with another individual and combining your work (unless explicitly authorized by the problem itself).
  • Submitting (after possibly modifying) the work of another individual beyond allowed snippets.
  • Submitting the same or similar work to this course that you have submitted or will submit to another.
  • Using resources during a quiz beyond those explicitly allowed in the quiz’s instructions.
  • Viewing another’s solution to a problem and basing your own solution on it.

Assessment

Your work on this writing problem will be evaluated along three axes primarily.

Scope
To what extent does your submission align with the requirements of the specification?

Correctness
To what extent is your submission correct and free of factual errors?

Style
To what extent is your submission readable (i.e., thoughtfully organized, coherent, words properly spelled)?

To obtain a passing grade in this course, all students must ordinarily submit all assigned problems unless granted an exception in writing by the instructor.

Step 1: Watch This.

Let’s start off by watching David’s video (from Ted-ED) on Algorithms.

As we see from that video, algorithms are sets of instructions for completing a task step-by-step. Sometimes these algorithms can be quite simple. One way to express an algorithm for deciding how to dress based on the weather might be to say something like this.

Look out the window. If it is raining outside, put on your rain boots and raincoat. 
Then go outside.

Sometimes they can be a bit more complex. Dropbox, if unfamiliar, is a service that provides storage of files “in the cloud”—on physical machines that are not your own but rather are typically owned by a hosting company—and delivers those files to you via the Internet. It also can synchronize your files between all machines on which you’ve installed the Dropbox client and has a web interface for downloading your synchronized files, which is handier than e-mailing yourself a copy of the file you worked on at school so you can continue working on that same file at home.

As the company began to grow and have many users, Dropbox needed many more file servers and a way to organize their millions of users and their billions of files across those servers. As computer scientists might say, they had to develop algorithms for dealing with issues of chunking and sharding:

And don’t worry if you don’t yet understand the processes that Thomas and Alex described in that video. You certainly don’t need to understand either of those things for this assignment, but rest assured that by the time you’ve completed the course, you’ll have a much better appreciation for how this might work!

Step 2: Read This.

The concept of an algorithm is fundamental in computer science. Recall from earlier in this unit that we defined a computer as a device that accepts input, and processes it in some way to produce a result automatically. The critical word in that sentence when we are talking about algorithms is the word “processes”.

Say you’re playing your favorite video game of all time. If you’re a fan of nostalgia, it might be this gem.[1]

Assume you’re racing Sonic around Green Hill Zone and you see a couple of rings up in the air, over Sonic’s head. Because they protect you in the event you are attacked by an enemy, you want to pick them up. In order to grab them, you have to press one of the buttons on the controller. When you press that button, Sonic jumps into the air to a consistent height. When and if he touches the ring, it disappears from the screen so it cannot be claimed multiple times, and the number of rings in his possession—indicated by a ring counter—increases by one.

Every step of that process involved multiple algorithms. Described informally, those algorithms (greatly simplified) might read as something like this:

If the jump button is pressed and if Sonic is standing on the ground, begin moving him 
upward until he reaches the top of his arc. After he reaches the top of his arc, begin
moving him downward by simulating gravity's pull until he is standing on the ground again.

And for the rings:

If Sonic is touching a ring, remove the ring from the screen and increase Sonic's ring 
counter by one.

Let’s focus just on the jumping algorithm for now, because the “input” to that algorithm is a lot clearer. The device that is executing this algorithm is the Sega Genesis console (or, more likely nowadays, an emulator for the same) running the Sonic the Hedgehog software. What is the data or input? That would be you, holding your controller, pressing down on the button that makes Sonic jump. (In fact, as you may recall, it’s actually an electrical pulse that occurred when you pressed that button that likely “jump-started” this algorithm.[2])

What is the result? On the television screen or monitor you see Sonic’s height off the ground begin to change; what he looks like might begin to change, too. Instead of keeping the same appearance as he did when standing on the ground, typically when Sonic jumps hissprite (a term we’ll be seeing again soon) changes to a ball that rotates, indicating that his jump is actually more of a flip or somersault through the air. As in reality, one doesn’t jump off the ground and then just fly off into the sky. What goes up must come down and so eventually after reaching the top of his jump Sonic lands on the ground again.

All of this is a process. And, truly, the process is a lot more fine-grained than that. We’ve oversimplified for purposes of illustration. We’ve also glossed over the notion of multiple algorithms running simultaneously in separate threads (another term we’ll be seeing again soon). But hopefully this example suffices for now.

Because this process of what happens when the jump button is pressed can be described as a clear, unambiguous, series of steps (aka, algorithmically)—at least in the game’s source code—it is consistent and, importantly, repeatable. If Sonic is standing at the same point and we press the jump button again and again—if he is standing on the ground and nothing else gets in his way like an enemy, whose algorithm might at some point fly them over Sonic’s head—the result is the same, again and again. Sonic always jumps to the same height, he spins in the same way while jumping, and he lands on the ground after the same amount of time. Because of the jumping algorithm, the computer always knows exactly what to do when that jump button is pressed, and always does exactly what it is told to do.

Sometimes it is easiest to express an algorithm using common language. That’s what we have done so far. Look back to the very first algorithm mentioned above—about deciding what to wear in the event of rain. Maybe there’s a way to articulate the decision-making process of getting ready more clearly?

Instead of this:

Look out the window. If it is raining outside, put on your rain boots and raincoat. 
Then go outside.

you might see a computer scientist instead use what’s called pseudocode—short expressions in common language organized in a way that resembles what source code looks like—to write their algorithms. We’ll talk more about pseudocode soon, but getting in the habit of writing it before you dive into actual coding in Scratch, C, PHP, or JavaScript is a great idea, much like writing the first draft of an essay.

Here’s one possible way to translate that algorithm into pseudocode:

1   look out the window
2   if it is raining outside
3      put on your rain boots
4      put on your raincoat
5   go outside

We’ve numbered the lines for a reason you’ll see momentarily. But notice how regardless of whether it’s raining the algorithm instructs you to go outside. It just has a special extra set of things you do before stepping outside if it happens to be raining. We call something like “if it is raining outside” a condition. Some algorithms also have steps that get repeated many times over, like this one:

Secretly pick your favorite number from 1 to 50. When your friend gives you a number, 
if they are too high tell them to guess lower and if they are too low tell them to
guess higher. If they are right, have your friend stop guessing.

We call such a repetition a loop, because you’ll keep going around and around the same steps until some condition (your friend guessing the right number) lets you stop. Here’s one of many possible ways to express the guessing game in pseudocode:

 1   secretly pick your favorite number from 1 to 50
 2   have your friend guess your favorite number
 3   if your friend guesses a lower number
 4      tell your friend to guess a higher number
 5      go back to line 2
 6   else if your friend guesses a higher number
 7      tell your friend to guess a lower number
 8      go back to line 2
 9   else
10      tell your friend to stop guessing

Notice here that until your friend guesses the correct number, they will go back to line 2 of the algorithm, which prompts them to make another guess. Only when they guess correctly can they proceed to line 10 and break out of the loop.

Step 3: Write This.

Okay, now you’ve learned a lot about algorithms and pseudocode. Perhaps we should try writing a few—three, to be precise. First, write up algorithms (both in sentence form and in pseudocode) for how to:

  • brush one’s teeth
  • eat an orange

Next, think of something that you do every day or nearly every day. Write an algorithm in sentence form and in pseudocode for how to do the thing you’re thinking of.

If you’re stuck, know that you aren’t just limited to purely text-based ways of writing out algorithms when trying to come up with them. It may help to just get started with a simple flowchart, such as the one Sheldon Cooper used in this clip from TV’s The Big Bang Theory:

Just do your best to avoid any infinite loops (a loop that’s impossible to ever break out of) in your algorithm, lest you be stuck in one forever!

Step 4: Do This.

Now for a little bit of fun. Before you actually turn in your algorithms, you probably should have someone test them out. Here’s what happened in a recent iteration of CS50 when we asked a few brave volunteers to make a peanut butter and jelly sandwich using an algorithm supplied by their classmates.

As you can see, describing algorithms precisely is crucial in order to have the desired effect! Have a few friends or family members test out your algorithms, instructing them to make absolutely no assumptions beyond exactly what you’ve written. Is your algorithm described clearly enough that your set of instructions can be repeated exactly without any ambiguity as to what to do? Did your friend or family member find a way to break your algorithm or, worse, find themselves in an infinite loop?

If so, help them escape, then take another crack at rewriting your algorithm’s instructions to see if you can’t make it a bit clearer.

Go back to the first paragraph of this section and run through those steps again.

See what we did there?

This process may actually be more challenging than it first appears, and that’s okay. We promise though, once you start writing source code you’ll have access to a new (but limited!) toolkit of keywords and commands that will make precise algorithm-writing substantially easier!

This was Writing Problem 0-2.


1. Don’t worry, we’ll give Mario his due soon enough, too!
2. Brace yourself for many more puns like that in the future.
Advertisements