Questions? Feel free to head to CS50 on Reddit, CS50 on StackExchange, the #cs50ap channel on CS50x Slack (after signing up), or the CS50 Facebook group.

Objectives

  • Explore Makefiles.

  • Reuse and repurpose previously written code.

  • Learn about and implement linear and binary search.

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 problem set will be evaluated along four axes primarily.

Scope

To what extent does your code implement the features required by our specification?

Correctness

To what extent is your code consistent with our specifications and free of bugs?

Design

To what extent is your code written well (i.e., clearly, efficiently, elegantly, and/or logically)?

Style

To what extent is your code readable (i.e., commented and indented with variables aptly named)?

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.

Getting Ready

Lots of recommended videos for you for this problem, although a few of them you’ve seen before and should feel free to skip over. Chances are at least a few of these will come in handy.

First up, sorting algorithms with Jackson and Tommy:

And then a discussion of linear and binary search with Patrick (don’t worry too much about when Patrick turns the discussion toward binary search trees in the second half of the binary search video… we’ll get there soon enough, though!):

Getting Started

Below are two options for getting started with this problem. The first option is for those who wish to start with a staff-provided pseudorandom number generator. The second option is for those who wish to use their own pseudorandom number generator from Problem 3-0

But first, log into cs50.io and execute

update50

within a terminal window to make sure your workspace is up-to-date.

Then, execute

cd ~/workspace/unit3

at your prompt to ensure that you’re inside of unit3 (which is inside of workspace which is inside of your home directory). Then execute

wget http://cdn.cs50.net/ap/1516/problems/3/6/seek.zip

to download a ZIP of this problem’s distro into your workspace (with a command-line program called wget). You should see a bunch of output followed by:

'seek.zip' saved

Confirm that you’ve indeed downloaded seek.zip by executing

ls

and then run

unzip seek.zip

to unzip the file. If you then run ls again, you should see that you have a newly unzipped directory called seek as well. You can now delete the ZIP, with:

rm seek.zip

confirming your intent to delete that file, then proceed to execute

cd seek

followed by

ls

and you should see that the directory contains five files:

Makefile  generate.c  helpers.c  helpers.h  seek.c

Only choose one of the below two options.

Then, after having chosen your option and followed all the steps therein, pick up at "Seek and Find".

Option 1: Use the Staff’s PRNG

You’re pretty much done getting set up at this point, actually. Except you should probably peruse generate.c; you’ll notice that we’ve left several comments just reading TODO. Take a few minutes to complete those comments, just to ensure you understand what’s happening in that file.

Option 2: Use Your Own PRNG

The staff’s PRNG can be found in generate.c, but you can fairly easily replace it with your own. Let’s first delete the staff’s PRNG with

rm -f generate.c

Now, let’s copy over the PRNG that you wrote a few problems back. Assuming you followed our directory hierarchy conventions, that file should be called rng.c and should live inside of a directory called rng inside of your unit3 directory, inside of your workspace, all of which is inside of your home (~) directory. Sounds like a mouthful. But knowing that, we don’t even need to move from where we currently are to get that file. That’s kind of cool. Before doing anything, ensure that you currently are inside of your seek subdirectory. The Linux command pwd (for "present working directory") will tell you where you currently are. Type

pwd

and you should get the following output:

/home/ubuntu/workspace/unit3/seek

If so, great! If not, make sure to navigate there with cd. Then, type the following:

cp ~/workspace/unit3/rng/rng.c .

The space and the . are deliberate! What this command basically does is tell the computer to copy the first argument (which is the absolute path to the rng.c file you’ve previously written) to the second. But what the heck is .? Well, it turns out that’s the shorthand way of saying "where I currently am." So, you’ve just told the computer to place a copy of rng.c inside of your present working directory. Confirm as much with:

ls

and you should see rng.c among your files. If not, odds are you made a small mistake a few steps back. Retrace your steps and try again.

Now, we could open up the Makefile and edit it so it creates an executable called rng, but that would require quite a bit of work. Why not instead just rename our file to generate.c? It’s pretty easy, just:

mv rng.c generate.c

And now if you

ls

one final time, no longer should you see rng.c among your files, but rather generate.c.

Seek and Find

You’ll be writing your code in helpers.c and helpers.h only in this problem. seek.c can be left alone, as can generate.c (with the exception that if you are using the staff’s PRNG you should comment that file!)

To begin, simply type

make

which will create not one but two executables: seek and generate (open up Makefile to see why!).

Now take a look at seek.c. Notice that this program expects a single command-line argument: a "needle" to search for in a "haystack" of values.

Go ahead and run this program by executing, say, the below.

./seek 13

You’ll be prompted to provide some hay (i.e., some integers), one "straw" at a time. As soon as you tire of providing integers, hit ctrl-d to send the program an EOF (end-of-file) character. That character will compel GetInt from the CS50 Library to return INT_MAX, a constant that, per seek.c, will compel seek to stop prompting for hay. The program will then look for that needle in the hay you provided, ultimately reporting whether the former was found in the latter. In short, this program searches an array for some value. At least, it should, but it won’t find anything yet! That’s where you come in. More on your role in a bit.

In turns out you can automate this process of providing hay, though, by "piping" the output of generate into seek as input. For instance, the command below[1] passes 1,000 pseudorandom numbers to seek, which then searches those values for 42.

./generate 1000 | ./seek 42

Note that, when piping output from generate into seek in this manner, you won’t actually see generate's numbers, but you will see seek's prompts.

Alternatively, you can "redirect" generate's output to a file with a command like the below.

./generate 1000 > numbers.txt

You can then redirect that file’s contents as input to seek with the command below.

./seek 42 < numbers.txt

search (1)

And now the fun begins! Notice that seek.c calls search, a function declared in helpers.h. Unfortunately, we forgot to implement that function fully in helpers.c! (To be sure, we could have put the contents of helpers.h and helpers.c in seek.c itself. But it’s sometimes better to organize programs into multiple files, especially when some functions are essentially utility functions that might later prove useful to other programs as well, much like those in the CS50 Library.) Take a peek at helpers.c with, and you’ll see that search always returns false, whether or not value is in values. Re-write search in such a way that it uses linear search, returning true if value is in values and false if value is not in values. Take care to return false right away if n isn’t even positive.

When ready to check the correctness of your program, try running the command below.

./generate 1000 50 | ./seek 127

Because one of the numbers[2] outputted by generate, when seeded with 50, is 127, your code should find that "needle"! By contrast, try running the command below as well.

./generate 1000 50 | ./seek 128

Because 128 is not among the numbers outputted by generate, when seeded with 50, your code shouldn’t find that needle. Best to try some other tests as well, as by running generate with some seed, taking a look at its output, then piping that same output to seek, looking for a "needle" you know to be among the "hay".

Incidentally, note that main in seek.c is written in such a way that seek returns 0 if the needle is found, else it returns 1. You can check the so-called "exit code" with which main returns by executing

echo $?

after running some other command. For instance, assuming your implementation of search is correct, if you run

./generate 1000 50 | ./seek 127
echo $?

you should see 0, since 127 is, again, among the 1,000 numbers outputted by generate when seeded with 50, and so search (written by you) should return true, in which case main (written by us) should return (i.e., exit with) 0. By contrast, assuming your implementation of search is correct, if you run

./generate 1000 50 | ./seek 128
echo $?

you should see 1, since 128 is, again, not among the 1,000 numbers outputted by generate when seeded with 50, and so search (written by you) should return false, in which case main (written by us) should return (i.e., exit with) 1. Make sense?

When ready to check the correctness of your program officially with check50, you may execute the below.

check50 1516.unit3.seek helpers.c

Anyhow, if you’d like to play with the staff’s own implementation of seek, you may execute the below.

~cs50/unit3/seek

Sorting

Alright, linear search is pretty meh. Recall from Week 0 that we can do better, but first we’d best sort that hay.

sort

Notice that seek.c calls sort, a function declared in helpers.h. Unfortunately, we forgot to implement that function fully too in helpers.c! Take a peek at helpers.c, and you’ll see that sort returns immediately, even though seek's main function does pass it an actual array.

Now, recall the syntax for declaring an array. Not only do you specify the array’s type, you also specify its size between brackets, just as we do for haystack in seek.c:

int haystack[MAX];

But when passing an array, you only specify its name, just as we do when passing haystack to sort in seek.c:

sort(haystack, size);

(Why do you think we pass in the size of that array separately?)

When declaring a function that takes a one-dimensional array as an argument, though, you don’t need to specify the array’s size, just as we don’t when declaring sort in helpers.h (and helpers.c):

void sort(int values[], int n);

Go ahead and implement sort so that the function actually sorts, from smallest to largest, the array of numbers that it’s passed, in such a way that its running time is in O(n2), where n is the array’s size. Odds are you’ll want to implement bubble sort, selection sort, or insertion sort, since you’ve already done so in the Sort Race. Just realize that there’s no one "right" way to implement any of those algorithms; variations abound. In fact, you’re welcome to improve upon them as you see fit, so long as your implementation remains in O(n2). However, take care not to alter our declaration of sort. Its prototype must remain:

void sort(int values[], int n);

As this return type of void implies, this function must not return a sorted array; it must instead "destructively" sort the actual array that it’s passed by moving around the values therein.

Although you may not alter our declaration of sort, you’re welcome to define your own function(s) in helpers.c that sort itself may then call.

We leave it to you to determine how best to test your implementation of sort. But don’t forget that printf and GDB are your friends. And don’t forget that you can generate the same sequence of pseudorandom numbers again and again by explicitly specifying generate's seed. Before you ultimately submit, though, be sure to remove any such calls to printf, as we like our programs' outputs just they way they are!

Here’s Zamyla with some tips:

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

~cs50/unit3/seek

search (2)

Now that sort (presumably) works, it’s time to improve upon search, the other function that lives in helpers.c. Recall that your first version implemented linear search. Rip out the lines that you wrote earlier.

Cruel, we know.

Anyway, re-implement search as binary search, that divide-and-conquer strategy we’ve seen employed. You are welcome to take an iterative approach (as with a loop) or, if feeling like jumping ahead a bit, a recursive approach (wherein a function calls itself). If you pursue the latter, though, know that you may not change our declaration of search, but you may write a new, recursive function (that perhaps takes different parameters) that search itself calls.

When it comes time to submit your work, it suffices to submit this new-and-improved version of search only; you needn’t submit your original version that used linear search.

Here’s Zamyla again:

This was Problem 3-6.


1. This command and all subsequent references to the generate program assume use of the staff-provided PRNG. If you use your own PRNG you either have to change the command-line arguments you provide, since the PRNG you wrote took 2 or 3 command line arguments (not 1 or 2, like the staff’s), or modify your copy of generate.c to no longer take the max parameter. Your choice!
2. Again, assuming you’re using the staff-provided PRNG!