Be sure to check the previous post before getting started to read this.
Alright! Welcome back. This is CS50! So, recall in the past days we’ve been spending a quite bit of time on C, on programming, on syntax. And, it’s quite normal if you still struggling about Problem Set 2, to banging your head again on the wall. It’s cryptic-error messages and bugs that you can’t quite chase down. So, if that any consolation hang in there for now. If you can solve it then, can you guess what the string actually says when I typed “ X Lvne Noh! “? Fantastic!
Today, though, we begin to transition to higher level which is more complex but actually it can help you more comfortable in programming and how we can go about optimizing and efficiency of our algorithm and generally solving more interesting problem. How can we go coding effectively by using running time. This problem set will introduce you to larger programs with multiple source files. Accustom you to reading someone else’s code, empowering you with Makefiles, and implement a party favor.
You’ll be more comfortable with :
- Searching algorithm
- Sorting algorithm
And anyway, you have to do 2 parts of this problem set :
Recommend Watching :
Lecturer : https://www.youtube.com/watch?v=YxgI7ll4Xtg
Binary search : https://www.youtube.com/watch?v=D5SrAga1pno
Linear search : https://www.youtube.com/watch?v=CX2CYIJLwfg
Bubble sort resources : https://www.youtube.com/watch?v=8Kp-8OGwphY
Insertion sort : https://www.youtube.com/watch?v=DFG-XuyPYUQ
Selection sort : https://www.youtube.com/watch?v=f8hXR_Hvybo
GDB : https://www.youtube.com/watch?v=USPvePv1uzE
Recommend Reading :
Page 17 of http://www.howstuffworks.com/c.htm
Phew, so many videos! And so many pages to read! If you’re done with it, be sure you can anwer these questions when it comes to submit this problem set’s form!
1. Why does binary search require that an array be sorted?
2. Why is bubble sort in O(n) ?
3. Why is insertion sort in Ω(n)?
4. What’s the worst-case running time of merge sort?
5. In no more than 3 sentences, how does selection sort works?
For problem set 3, you’ll instead download “distribution code”(otherwise known as “distro”), written by cs50 team, and add you own line of code to it. You’ll first need to read and understand their code, though, this problem set is as much about learning to read someone else’s code as it is about writing your own!
Let’s get you started. Go ahead and open up terminal window. Then execute :
To make sure your appliance is up-to-date. Then execute
to download a ZIP of this problem set’s distro into your appliance (with command-line program wget). You should see a bunch of output followed by:
Ultimately confirm that you’ve download pset3.zip by executing :
To unzip file. If you run ls again, you should see that you have newly unzipped directory called pset3 as well. Proceed to execute :
And you should find see that the directory contains two “subdirectories” :
Searching algorithm is “ an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots of an equation with integer variables; or a combination of the two”
A Sorting algorithm is “an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other algorithms (such as search and merge algorithms) which require input data to be in sorted lists; it is also often useful for canonicalizing data and for producing human-readable output”
Okay, let’s dive into the first of those subdirectories.
Open up the terminal and execute :
You should see below :
helpers.c helpers.h Makefile find.c generate.c
Phew, that’s a lot of files! Take a look at each file. And try to undersand what do they mean.
And again, please read the spec first! http://d2o9nyf4hwsci4.cloudfront.net/2014/x/psets/3/pset3/pset3.html#_getting_started
Let’s begin the first problem “find”.
- Prompt for numbers to fill the haystack
- Searches the haystack for a needle
– call sorts and searches, function defined in helper.c
helpers.c was the helper function in Problem Set 3. You’ll need to complete the fully function on it.
Open up the terminal and execute :
To make sure you are in a right subdirectory. Then, open up gedit and open helpers.c.
Not sure where to begin?
Anyway,you’ll want to implement a searching and sorting algorithm.
- Return true if value is found at haystack
- Return false if values is not found at haystack
Linear search : you can do better!
• O(n) → slow
• Can search any list
Binary search :
• O(log n) → fast
• Can only search sorted list
Binary search pseudocode :
bool search(int value, int values, int n) while length of the list > 0 look at the middle of list if number found, return true else if number higher, search left else if number lower, search right return false
Sort the values array
void sort(int values, int n)
Selection sort pseudocode :
for i = 0 to n-1 for j = i + 1 to n find index of minimum value swap array[min] and array[i]
Bubble sorts pseudocode :
- iterate over the list - compare adjacent elements - swap elements that are in the wrong order - largest elements will ‘bubble’ till the end - the list is sorted once no elements have been swapped
And, you’re done the first problem! Conguratulations!
The Game Begins
Now the second problem is a Game Of Fifteen puzzle played on a square, two-dimensional board with numbered tiles that slide. The goal of this puzzle is to arrange the board’s tiles from smallest to largest, left to right, top to bottom, with an empty space in board’s bottom-right corner as in the below :
You should make your “move” (i.e that borders the board’s empty space)with sliding any tile from smallest to largest, left to right, top to bottom. Although the configuration of board above depicts the game is already won. You should not make any move diagonally or forcibly removed from the board. If, however and only if the board contain odd number (i.e the height and weight of board are even), the position of number 1 and 2 must be swapped. It solvable if the configuration as see below :
Navigate your way to :
And take a look at fifteen.c with gedit.
Read over the code and comments in fifteen.c and be sure you can answer the questions below before proceeding further.
- Besides 4 x 4 (which are game of fifteen’s dimension), what other dimension does the framework allow ?
- With what sort of data structure is the game’s board represented?
- What function do you apparently need to implement?
You’ll want to take “baby steps” to implement this game. Four things that you’ll need to implements are :
15 14 13 12 11 10 9 8 7 6 5 4 3 1 2 _
Recall that the positions of tiles numbered 1 and 2 should only start swapped as they are in 4 x 4 as example above. But they do not swapped in 3 x 3 example below :
8 7 6 5 4 3 2 1 _
Initializes the game’s board with tiles numbered 1 through d*d – 1 (i.e., fills board with values but does not actually print them), whereby board[i][j] represents row i and column j.
Board represented by 2D dimensional array.
Init pseudocode :
board should contain the starting state • board[i][j] represents the elements at row[i] col[j] Starts in descending order • if the number tiles odd, swap 2 and 1
Prints the board in its current state. Then, print the blank space before single-digit #s using :
Draw pseudocode :
for each row for each value in row print value and space print new line
bool move(int tile)
If tile borders empty space, moves tile and returns true, else returns false.
Move pseudocode :
Accept the number of tile to move Not its positions! Search for the tile’s position. Remember where the blank tile is now
Returns true if game is won (i.e., board is in winning configuration), else false. Game is won when tiles are in increasing order.
1 2 3 4 5 6 7 8 _
Won pseudocode :
- Iterate over board and check the values
- If any values in incorrect, return false
Viola, you’ve finished Game Of Fifteen. To test your implementation of fifteen, you can certainly try playing it.(No check50 for this one). Know that program to quit by hitting ctrl-c. To test your program with, say, the first of those inputs, execute the below.
./fifteen 3 < ~cs50/pset3/3x3.txt
Now, you’re done with both Find and Game Of Fifteen!
This was Problem Set 3.