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 to the Administrative Board and the outcome is Admonish, Probation, Requirement to Withdraw, or Recommendation to Dismiss, 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 to the Administrative Board.

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

All students, whether taking the course SAT/UNS or 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 the CS50 Appliance is a "virtual machine" (running an operating system called Ubuntu, which itself is a flavor of Linux) that you can run inside of a window on your own computer, whether you run Windows, Mac OS, or even Linux itself. To do so, all you need is a "hypervisor" (otherwise known as a "virtual machine monitor"), software that tricks the appliance into thinking that it’s running on "bare metal."

Alternatively, you could buy a new computer, install Ubuntu on it (i.e., bare metal), and use that! But a hypervisor lets you do all that for free with whatever computer you already have. Plus, the CS50 Appliance is pre-configured for CS50, so, as soon as you install it, you can hit the ground running.

First, a hello from Zamyla if you’d like a tour of what’s to come, particularly if less comfortable.

Shall we have you write your first program? Go ahead and launch gedit. (Remember how?) You should find yourself faced with another Unsaved Document 1. Go ahead and save the file as hello.c (not hello.txt) inside of hacker1, just as before. (Remember how?) Once the file is saved, the window’s title should change to hello.c (~/Dropbox/hacker1) - gedit, and the tab’s title should change to hello.c. (If either does not, best to close gedit and start fresh! Or ask for help!)

Go ahead and write your first program by typing these lines into the file (though you’re welcome to change the words between quotes to whatever you’d like):

Notice how gedit 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 gedit to make certain syntax stand out. Had you not saved the file as hello.c from the start, gedit 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 ctrl-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 its prompt should start blinking. But odds are the prompt itself is just

which means that, so far as the terminal window’s concerned, you’re still inside of John Harvard’s home directory, even though you saved the program you just wrote inside of ~/Dropbox/hacker1 (per the top of gedit's window). No problem, go ahead and type

or

at the prompt, and the prompt should change to

in which case you’re where you should be! Let’s confirm that hello.c is there. Type

at the prompt 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 whatever message you wrote between quotes in your code! Indeed, if you type

followed by Enter, you should see a new file, hello, alongside hello.c and hello.txt.

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 ctrl-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 ~/Dropbox/hacker1 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 precisely the below?

If not, reach out for help!

Incidentally, if you find gedit​'s built-in terminal window too small for your tastes, know that you can open one in its own window via Menu > Programming > Terminal. You can then alternate between gedit and Terminal as needed, as by clicking either’s name along the appliance’s bottom.

Woo hoo! You’ve begun to program!

Now let’s see if the program you just wrote is correct! Included in the CS50 Appliance 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 ~/Dropbox/hacker1 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 2014.fall.hacker1.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.

In addition to check50, the CS50 Appliance comes with style50, a tool with which you can evaluate your code’s style vis-à-vis CS50’s style guide. To run it on, say, hello.c, execute the below:

You should see zero or more lines of suggestions. Yellow smileys indicate warnings that you should consider addressing. Red smileys indicate errors that you should definitely address.

If you instead see java: command not found, execute sudo apt-get -y install default-jre-headless (which will install software that we forgot to install for you!), then try again.

Note that style50 is still a work in progress (a "beta" version, so to speak), so best to consult CS50’s style guide for official guidance.

Head to https://cs50.harvard.edu/shorts/1 and curl up with Nate’s short on libraries. Be sure you’re reasonably comfortable answering the below when it comes time to submit this problem set’s form!

Curl up with at least two other shorts at https://cs50.harvard.edu/shorts/1. Some additional questions may be in your future!

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 Daven’s 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 GetLongLong from CS50’s library to get users' input. (Why?)

Of course, to use GetLongLong, you’ll need to tell clang about CS50’s library. Be sure to put

toward the top of credit.c. And be sure to compile your code with a command like the below.

Note that -lcs50 must come at this command’s end because of how clang works.

Incidentally, recall that make can invoke clang for you and provide that flag for you, as via the command below.

Assuming your program compiled without errors (or, ideally, warnings) via either command, you can run your program with the command below.

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, GetLongLong itself will reject hyphens (and more) anyway:

But it’s up to you to catch inputs that are not credit card numbers (e.g., Lauren’s 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 in the appliance, you may execute the below.

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 at https://cs50.harvard.edu/lectures/1. Allow me to take you on a tour, though feel free to forge ahead on your own if you’d prefer. Not to worry if your appliance also looks a bit different from mine.

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 ~/Dropbox/hacker1 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! And be sure that main returns 0.

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 mario in the appliance, you may execute the below starting Tue 9/17.