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 :

- Array(s)
- Searching algorithm
- Sorting algorithm
- gdb

And anyway, you have to do 2 parts of this problem set :

- find
- fifteen

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?*

## Getting Started.

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 :

**update50**

To make sure your appliance is up-to-date. Then execute

**cd ~/Dropbox**

Followed by

wget http://cdn.cs50.net/2013/fall/psets/3/pset3/pset3.zip

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:

‘pset3.zip’ saved

Ultimately confirm that you’ve download pset3.zip by executing :

ls

Then, run

unzip pset3.zip

To unzip file. If you run ls again, you should see that you have newly unzipped directory called pset3 as well. Proceed to execute :

cd pset3

Followed by

ls

And you should find see that the directory contains two “subdirectories” :

fifteen find

## Searching Algorithm

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”

http://en.wikipedia.org/wiki/Search_algorithm

## Sorting

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”

http://en.wikipedia.org/wiki/Sorting_algorithm

Okay, let’s dive into the first of those subdirectories.

Open up the terminal and execute :

**cd ~/Dropbox/pset3/find**

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”.

## 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.

*TODO :*

- Search
- Sort

Open up the terminal and execute :

cd ~/Dropbox/pset3/find

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.

###
Search

- 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

Sort the values[] array

void sort(int values[], int n)

*Selection sort pseudocode :*

for i = 0 to n-1for j = i + 1 to nfind index of minimum valueswap 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 :

~/Dropbox/pset3/fifteen

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 :

- Init
- Draw
- Move
- Won

15 14 13 1211 10 9 87 6 5 43 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 765 4 32 1 _

### INIT

void init(void)

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

### DRAW

voiddraw(void)

Prints the board in its current state. Then, print the blank space before single-digit #s using :

printf("%2d", board[i][j]);

*Draw pseudocode :*

for each rowfor each value in rowprint value and spaceprint new line

**MOVE**

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 moveNot its positions!Search for the tile’s position.Remember where the blank tile is now

**WON**

bool won(void)

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 34 5 67 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.*