Problem Set 1: C

Head to cs50.io and log into CS50 IDE. You may be prompted (again) for your email address. If so, after providing it, click Private under Hosted workspace, then click Create workspace.

You should then be informed that CS50 IDE (aka Cloud9, the software that underlies CS50 IDE) is "creating your workspace" and "creating your container," which might take a moment. You should eventually see your workspace, which should resemble mine from Week 1. If not, do just email the course’s heads to inquire!

Toward the bottom of CS50 IDE’s UI is a "terminal window" (light blue, by default), a command-line interface (CLI) that allows you to explore your workspace’s files and directories, compile code, run programs, and even install new software. You should find that its "prompt" resembles the below.

Click inside of that terminal window and then type

followed by Enter to ensure that your workspace is up-to-date. It might take a few minutes for any updates to complete. (Be sure not to close the tab or CS50 IDE itself until they do!)

Okay, let’s create a folder in which your code for this problem set will soon live. Toward CS50 IDE’s top-left corner, you should see a little folder called ~/workspace in which all of your work will (soon!) live. Control-click or right-click that folder and select New Folder. A new folder called New Folder should appear; rename it pset1, then hit Enter. (If you misname it or can’t seem to edit its name, control-click or right-click the new folder and select Rename to try again!)

Next, control-click or right-click that pset1 folder that you just created and select New File. A new file called Untitled should appear; rename it hello.txt (all lowercase) and then hit Enter. (If you misname it or can’t seem to edit its name, control-click or right-click the new file and select Rename to try again!) You should see that hello.txt is indented immediately beneath pset1, which indicates that the former is inside of the latter. If hello.txt doesn’t appear to be inside of pset1, simply drag and drop the former into the latter.

Double-click hello.txt, and a new tab should appear within CS50 IDE via which you can edit the file. Go ahead and type something simple (e.g., hello or the ever-popular asdf). Notice that red dot should then appear atop the tab, to the right of the tab’s name. That red dot indicates that your file has changed but not yet been saved. Go ahead and save the file via File > Save or, more quickly, via command-S (on Macs) or control-S (on PCs). The red dot should disappear.

Okay, now let’s confirm via your terminal window that the file is indeed where it should be and start to familiarize you with that terminal window’s command-line interface. As before, your terminal window’s prompt should be the below.

That prompt indicates that workspace is the name of your terminal window’s "current working directory" (i.e., the folder that’s currently open within that command-line environment). The tilde (~), meanwhile, refers to your account’s "home directory," in which your workspace directory lives, but more on that another time. As you might have guessed, this workspace directory is identical to that ~/workspace folder in CS50 IDE’s top-left corner.

Okay, let’s poke around. Again click somewhere inside of that terminal window and then type

followed by Enter. That’s a lowercase L and a lowercase S, which is shorthand notation for "list." Indeed, you should then see a list of the folders inside of your workspace, among which is pset1! Let’s open that folder. Type

or even, more verbosely,

followed by Enter to change your directory to ~/workspace/pset1 (ergo, cd). You should find that your prompt changes to

confirming that you are indeed now inside of ~/workspace/pset1/ (i.e., a directory called pset1 inside of a directory called workspace inside of your home directory). Now type

followed by Enter. You should see hello.txt! Now, you can’t click or double-click on that file’s name there; it’s just text. But that listing does confirm that hello.txt is where we hoped it would be. (If not, take another stab at these steps or simply ask classmates or staff for some help!)

Let’s poke around a bit more. Go ahead and type

and then Enter. If you don’t provide cd with a "command-line argument" (i.e., a directory’s name), it whisks you back to your workspace by default. Indeed, your prompt should now be

again. To get back into pset1, type

and then Enter. Make sense? If not, no worries; it soon will! It’s in this terminal window that you’ll soon be compiling your first program!

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 get_int will handle some, but not all, re-prompting for you.)

To compile your program, remember that you can execute

after which you can run your program with the below.

If you encounter any errors you don’t understand, try asking help50 for help. (Remember how?)

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, here’s Zamyla:

Toward the beginning of World 1-1 in Nintendo’s Super Mario Brothers, Mario must hop over two "half-pyramids" of blocks as he heads toward a flag pole. Below is a screenshot.

Write, in a file called mario.c in your ~/workspace/pset1 directory, a program that recreates these half-pyramids using hashes (#) for blocks. However, to make things more interesting, first prompt the user for the half-pyramids' heights, a non-negative integer no greater than 23. (The height of the half-pyramids pictured above happens to be 4, the width of each half-pyramid 4, with an a gap of size 2 separating them.) Then, generate (with the help of printf and one or more loops) the desired half-pyramids. Take care to left-align the bottom-left corner of the left-hand half-pyramid, as in the sample output below, wherein boldfaced text represents some user’s input.

No need to generate the bricks, cloud, numbers, or text in the sky or Mario himself. Just the half-pyramids!

We leave it to you to determine how to compile this program.

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

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

Like to implement these two half-pyramids but not sure how to approach them? Here’s Zamyla with a walkthrough.

Ever seen one of these, a "classic coin changer just like [the] ones used by street vendors and the ice cream truck", which lets you dispense coins by pressing levers?

When using a device like this, odds are you want to minimize the number of coins you’re dispensing for each customer, lest you have to press levers more times than are necessary. 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 get_float 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 get_float 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 get_float 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.1 cannot be represented exactly as a float. Try printing its value to, say, 55 decimal places, with code like the below:

And so, before making change, 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 take care to round your cents (to the nearest penny); don’t "truncate" (i.e., floor) your cents!

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.

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.

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

Odds are you have a credit card in your wallet. Though perhaps the bill does not (yet) get sent to you! That card has a number, both printed on its face and embedded (perhaps with some other data) in the magnetic stripe on back. That number is also stored in a database somewhere, so that when your card is used to buy something, the creditor knows whom to bill. There are a lot of people with credit cards in this world, so those numbers are pretty long: American Express uses 15-digit numbers, MasterCard uses 16-digit numbers, and Visa uses 13- and 16-digit numbers. And those are decimal numbers (0 through 9), not binary, which means, for instance, that American Express could print as many as 10^(15) = 1,000,000,000,000,000 unique cards! (That’s, ahem, a quadrillion.)

Now that’s a bit of an exaggeration, because credit card numbers actually have some structure to them. American Express numbers all start with 34 or 37; MasterCard numbers all start with 51, 52, 53, 54, or 55; and Visa numbers all start with 4. But credit card numbers also have a "checksum" built into them, a mathematical relationship between at least one number and others. That checksum enables computers (or humans who like math) to detect typos (e.g., transpositions), if not fraudulent numbers, without having to query a database, which can be slow. (Consider the awkward silence you may have experienced at some point whilst paying by credit card at a store whose computer uses a dial-up modem to verify your card.) Of course, a dishonest mathematician could certainly craft a fake number that nonetheless respects the mathematical constraint, so a database lookup is still necessary for more rigorous checks.

So what’s the secret formula? Well, most cards use an algorithm invented by Hans Peter Luhn, a nice fellow from IBM. According to Luhn’s algorithm, you can determine if a credit card number is (syntactically) valid as follows:

That’s kind of confusing, so let’s try an example with my AmEx: 378282246310005.

So, validating credit card numbers isn’t hard, but it does get a bit tedious by hand. Let’s write a program.

In credit.c, write a program that prompts the user for a credit card number and then reports (via printf) whether it is a valid American Express, MasterCard, or Visa card number, per the definitions of each’s format herein. So that we can automate some tests of your code, we ask that your program’s last line of output be AMEX\n or MASTERCARD\n or VISA\n or INVALID\n, nothing more, nothing less, and that main always return 0. For simplicity, you may assume that the user’s input will be entirely numeric (i.e., devoid of hyphens, as might be printed on an actual card). But do not assume that the user’s input will fit in an int! Best to use get_long_long from CS50’s library to get users' input. (Why?)

Consider the below representative of how your own program should behave when passed a valid credit card number (sans hyphens), wherein underlined text represents some user’s input.

Of course, get_long_long itself will reject hyphens (and more) anyway:

But it’s up to you to catch inputs that are not credit card numbers (e.g., a phone number), even if numeric:

Test out your program with a whole bunch of inputs, both valid and invalid. (We certainly will!) Here are a few card numbers that PayPal recommends for testing:

https://www.paypalobjects.com/en_US/vhelp/paypalmanager_help/credit_card_numbers.htm

Google (or perhaps a roommate’s wallet) should turn up more. (If your roommate asks what you’re doing, don’t mention us.) If your program behaves incorrectly on some inputs (or doesn’t compile at all), time to debug!

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 credit within CS50 IDE, you may execute the below.

Like to tackle this problem but not sure how to begin? Here’s Zamyla with a walkthrough.

Head to https://forms.cs50.net/2016/fall/psets/1 where a short form awaits. Once you have submitted that form (as well as your source code), you are done! If you end up resubmitting your files (per step 1 of 2), no need to resubmit the form.

This was Problem Set 1.