Problem Set 1: C

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 problem sets is not permitted 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 to others, but you may not view theirs, so long as you and they respect this policy’s other constraints. Collaboration on quizzes is not permitted at all. Collaboration on the course’s 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 the course’s heads. Acts considered not reasonable by the course are handled harshly. If the course refers some matter for disciplinary action and the outcome is punitive, the course reserves the right to impose local sanctions on top of that outcome that may include an unsatisfactory or failing grade for work submitted or for the course itself.

If you commit some act that is not reasonable but bring it to the attention of the course’s heads within 72 hours, the course may impose local sanctions that may include an unsatisfactory or failing grade for work submitted, but the course will not refer the matter for further disciplinary action except in cases of repeated acts.

Your work on this problem set will be evaluated along four axes primarily.

All students, whether or not taking the course for a letter grade, must ordinarily submit this and all other problem sets to be eligible for a satisfactory grade unless granted an exception in writing by the course’s heads.

Recall that CS50 IDE is a web-based "integrated development environment" that allows you to program "in the cloud," without installing any software locally. Underneath the hood is a popular operating system, Ubuntu Linux, that’s been "containerized" with open-source software called Docker, that allows multiple users (like you!) to share the operating system’s "kernel" (its nucleus, so to speak) and files, even while having files of their own. Indeed, CS50 IDE provides you with your very own "workspace" (i.e., storage space) in which you can save your own files and folders (aka directories). Anyhow, more on all that another time!

First, a hello from Zamyla if you’d like a tour of what’s to come, particularly if less comfortable. Note that she’s using the CS50 Appliance, the (non-web-based) predecessor of CS50 IDE, but not a problem. Any code she writes within the CS50 Appliance should work the same within CS50 IDE!

Shall we have you write your first program? Inside of your pset1 folder, create a new file called hello.c, and then open that file in a tab. (Remember how?) Be sure to capitalize the file’s name just as we have; files' and folders' names in Linux are "case-sensitive." Proceed to write your first program by typing precisely these lines into the file:

Notice how CS50 IDE adds "syntax highlighting" (i.e., color) as you type. Those colors aren’t actually saved inside of the file itself; they’re just added by CS50 IDE to make certain syntax stand out. Had you not saved the file as hello.c from the start, CS50 IDE wouldn’t know (per the filename’s extension) that you’re writing C code, in which case those colors would be absent.

Do be sure that you type in this program just right, else you’re about to experience your first bug! In particular, capitalization matters, so don’t accidentally capitalize words (unless they’re between those two quotes). And don’t overlook that one semicolon. C is quite nitpicky!

When done typing, select File > Save (or hit command- or control-s), but don’t quit. Recall that the leading asterisk in the tab’s name should then disappear. Click anywhere in the terminal window beneath your code, and be sure that you’re inside of ~/workspace/pset1. (Remember how? If not, type cd and then Enter, followed by cd workspace/pset1 and then Enter.) Your prompt should be:

Let’s confirm that hello.c is indeed where it should be. Type

followed by Enter, and you should see both hello.c and hello.txt? If not, no worries; you probably just missed a small step. Best to restart these past several steps or ask for help!

Assuming you indeed see hello.c, let’s try to compile! Cross your fingers and then type

at the prompt, followed by Enter. (Well, maybe don’t cross your fingers whilst typing.) To be clear, type only hello here, not hello.c. If all that you see is another, identical prompt, that means it worked! Your source code has been translated to object code (0s and 1s) that you can now execute. Type

at your prompt, followed by Enter, and you should see the below:

And if you type

followed by Enter, you should see a new file, hello, alongside hello.c and hello.txt. The first of those files, hello, should have an asterisk after its name that, in this context, means it’s "executable," a program that you can execute (i.e., run).

If, though, upon running make, you instead see some error(s), it’s time to debug! (If the terminal window’s too small to see everything, click and drag its top border upward to increase its height.) If you see an error like expected declaration or something no less mysterious, odds are you made a syntax error (i.e., typo) by omitting some character or adding something in the wrong place. Scour your code for any differences vis-à-vis the template above. It’s easy to miss the slightest of things when learning to program, so do compare your code against ours character by character; odds are the mistake(s) will jump out! Anytime you make changes to your own code, just remember to re-save via File > Save (or command- or control-s), then re-click inside of the terminal window, and then re-type

at your prompt, followed by Enter. (Just be sure that you are inside of ~/workspace/pset1 within your terminal window, as your prompt will confirm or deny.) If you see no more errors, try running your program by typing

at your prompt, followed by Enter! Hopefully you now see whatever you told printf to print?

If not, reach out for help! Incidentally, if you find the terminal window too small for your tastes, know that you can open one in a bigger tab by clicking the circled plus (+) icon to the right of your hello.c tab.

Woo hoo! You’ve begun to program!

Now let’s see if the program you just wrote is correct! Included in CS50 IDE is check50, a command-line program with which you can check the correctness of (some of) your programs.

If not already there, navigate your way to ~/workspace/pset1 by executing the command below.

If you then execute

you should see, at least, hello.c. Be sure it’s indeed spelled hello.c and not Hello.c, hello.C, or the like. If it’s not, know that you can rename a file by executing

where source is the file’s current name, and destination is the file’s new name. For instance, if you accidentally named your program Hello.c, you could fix it as follows.

Okay, assuming your file’s name is definitely spelled hello.c now, go ahead and execute the below. Note that 2015.fall.pset1.hello is just a unique identifier for this problem’s checks.

Assuming your program is correct, you should then see output like

where each green smiley means your program passed a check (i.e., test). You may also see a URL at the bottom of check50's output, but that’s just for staff (though you’re welcome to visit it).

If you instead see yellow or red smileys, it means your code isn’t correct! For instance, suppose you instead see the below.

Because check50 doesn’t think hello.c exists, as per the red smiley, odds are you uploaded the wrong file or misnamed your file. The other smileys, meanwhile, are yellow because those checks are dependent on hello.c existing, and so they weren’t even run.

Suppose instead you see the below.

Odds are, in this case, you printed something other than hello, world\n verbatim, per the spec’s expectations. In particular, the above suggests you printed hello, world, without a trailing newline (\n).

Know that check50 won’t actually record your scores in CS50’s gradebook. Rather, it lets you check your work’s correctness before you submit your work. Once you actually submit your work (per the directions at this spec’s end), CS50’s staff will use check50 to evaluate your work’s correctness officially.

Curl up with Nate’s short on libraries and at least two other shorts for this week.

Be sure you’re reasonably comfortable answering the below when it comes time to submit this problem set’s form!

Before forging ahead, you might want to review some of the examples that we looked at in Week 1’s lectures and take a look at a few more, the "source code" for which can be found under Lectures on the course’s website. Allow me to take you on a tour, though feel free to forge ahead on your own if you’d prefer. (My CS50 Appliance will look a bit different from CS50 IDE, but not to worry.)

Suffice it to say that the longer you shower, the more water you use. But just how much? Even if you have a "low-flow" showerhead, odds are your shower spits out 1.5 gallons of water per minute. A gallon, meanwhile, is 128 ounces, and so that shower spits out 1.5 × 128 = 192 ounces of water per minute. A typical bottle of water (that you might have for a drink, not a shower), meanwhile, might be 16 ounces. So taking a 1-minute shower is akin to using 192 ÷ 16 = 12 bottles of water. Taking (more realistically, perhaps!) a 10-minute shower, then, is like using 120 bottles of water. Deer Park, that’s a lot of water! Of course, bottled water itself is wasteful; best to use reusable containers when you can! But it does put into perspective what’s being spent in a shower!

Write, in a file called water.c in your ~/workspace/pset1 directory, a program that prompts the user for the length of his or her shower in minutes (as a positive integer) and then prints the equivalent number of bottles of water (as an integer) per the sample output below, wherein underlined text represents some user’s input.

For simplicity, you may assume that the user will input a positive integer, so no need for error-checking (or any loops) this time! And no need to worry about overflow!

If you’d like to check the correctness of your program with check50, you may execute the below.

And if you’d like to play with the staff’s own implementation of water within CS50 IDE, you may execute the below.

Toward the end of World 1-1 in Nintendo’s Super Mario Brothers, Mario must ascend a "half-pyramid" of blocks before leaping (if he wants to maximize his score) toward a flag pole. Below is a screenshot.

Write, in a file called mario.c in your ~/workspace/pset1 directory, a program that recreates this half-pyramid using hashes (#) for blocks. However, to make things more interesting, first prompt the user for the half-pyramid’s height, a non-negative integer no greater than 23. (The height of the half-pyramid pictured above happens to be 8.) If the user fails to provide a non-negative integer no greater than 23, you should re-prompt for the same again. Then, generate (with the help of printf and one or more loops) the desired half-pyramid. Take care to align the bottom-left corner of your half-pyramid with the left-hand edge of your terminal window, as in the sample output below, wherein underlined text represents some user’s input.

Note that the rightmost two columns of blocks must be of the same height. No need to generate the pipe, clouds, numbers, text, or Mario himself.

By contrast, if the user fails to provide a non-negative integer no greater than 23, your program’s output should instead resemble the below, wherein underlined text again represents some user’s input. (Recall that GetInt will handle some, but not all, re-prompting for you.)

To compile your program, remember that you can execute

or, more manually,

after which you can run your program with the below.

If you’d like to check the correctness of your program with check50, you may execute the below.

And if you’d like to play with the staff’s own implementation of mario within CS50 IDE, you may execute the below.

Not sure where to begin? Not to worry. A walkthrough awaits!

Speaking of money, here’s "a great way to store change and teach children to add it up. With the press of the lever, the coin changer releases coins on demand. Slots allow you to slide this great toy onto your belt."

Of course, the novelty of this thing quickly wears off, especially when someone pays for a newspaper with a big bill. Fortunately, computer science has given cashiers everywhere ways to minimize numbers of coins due: greedy algorithms.

According to the National Institute of Standards and Technology (NIST), a greedy algorithm is one "that always takes the best immediate, or local, solution while finding an answer. Greedy algorithms find the overall, or globally, optimal solution for some optimization problems, but may find less-than-optimal solutions for some instances of other problems."

What’s all that mean? Well, suppose that a cashier owes a customer some change and on that cashier’s belt are levers that dispense quarters, dimes, nickels, and pennies. Solving this "problem" requires one or more presses of one or more levers. Think of a "greedy" cashier as one who wants to take, with each press, the biggest bite out of this problem as possible. For instance, if some customer is owed 41¢, the biggest first (i.e., best immediate, or local) bite that can be taken is 25¢. (That bite is "best" inasmuch as it gets us closer to 0¢ faster than any other coin would.) Note that a bite of this size would whittle what was a 41¢ problem down to a 16¢ problem, since 41 - 25 = 16. That is, the remainder is a similar but smaller problem. Needless to say, another 25¢ bite would be too big (assuming the cashier prefers not to lose money), and so our greedy cashier would move on to a bite of size 10¢, leaving him or her with a 6¢ problem. At that point, greed calls for one 5¢ bite followed by one 1¢ bite, at which point the problem is solved. The customer receives one quarter, one dime, one nickel, and one penny: four coins in total.

It turns out that this greedy approach (i.e., algorithm) is not only locally optimal but also globally so for America’s currency (and also the European Union’s). That is, so long as a cashier has enough of each coin, this largest-to-smallest approach will yield the fewest coins possible.

How few? Well, you tell us. Write, in a file called greedy.c in your ~/workspace/pset1 directory, a program that first asks the user how much change is owed and then spits out the minimum number of coins with which said change can be made. Use GetFloat from the CS50 Library to get the user’s input and printf from the Standard I/O library to output your answer. Assume that the only coins available are quarters (25¢), dimes (10¢), nickels (5¢), and pennies (1¢).

We ask that you use GetFloat so that you can handle dollars and cents, albeit sans dollar sign. In other words, if some customer is owed $9.75 (as in the case where a newspaper costs 25¢ but the customer pays with a $10 bill), assume that your program’s input will be 9.75 and not $9.75 or 975. However, if some customer is owed $9 exactly, assume that your program’s input will be 9.00 or just 9 but, again, not $9 or 900. Of course, by nature of floating-point values, your program will likely work with inputs like 9.0 and 9.000 as well; you need not worry about checking whether the user’s input is "formatted" like money should be. And you need not try to check whether a user’s input is too large to fit in a float. But you should check that the user’s input makes cents! Er, sense. Using GetFloat alone will ensure that the user’s input is indeed a floating-point (or integral) value but not that it is non-negative. If the user fails to provide a non-negative value, your program should re-prompt the user for a valid amount again and again until the user complies.

Incidentally, do beware the inherent imprecision of floating-point values. For instance, 0.01 cannot be represented exactly as a float. Try printing its value to, say, 50 decimal places, with code like the below:

Before doing any math, then, you’ll probably want to convert the user’s input entirely to cents (i.e., from a float to an int) to avoid tiny errors that might otherwise add up! Of course, don’t just cast the user’s input from a float to an int! After all, how many cents does one dollar equal? And be careful to round and not truncate your pennies!

Not sure where to begin? Not to worry, start with a walkthrough:

Incidentally, so that we can automate some tests of your code, we ask that your program’s last line of output be only the minimum number of coins possible: an integer followed by \n. Consider the below representative of how your own program should behave, wherein underlined text is some user’s input.

By nature of floating-point values, that user could also have inputted just .41. (Were they to input 41, though, they’d get many more coins!)

Of course, more difficult users might experience something more like the below.

Per these requirements (and the sample above), your code will likely have some sort of loop. If, while testing your program, you find yourself looping forever, know that you can kill your program (i.e., short-circuit its execution) by hitting ctrl-c (sometimes a lot).

We leave it to you to determine how to compile and run this particular program!

If you’d like to check the correctness of your program with check50, you may execute the below.

And if you’d like to play with the staff’s own implementation of greedy within CS50 IDE, you may execute the below.