Shell sort with Algo-rythmics ♫

Whoa, it has been over two months since my last post!

Let’s get this train back on track (choof choof).

So, two weeks ago I was studying for my midterms and I was reminded of an awesome group called AlgoRythmics. They are a bunch of people from a university in Romania that demonstrate the sorting algorithms with various folk dances (mostly Hungarian). Although my midterm was not about sorting or any sort of algorithm at all, I watched all of their videos, totally hypnotized by their nerdiness and awesomeness.  My favorite ones are merge sort, shell sort and quick sort (although I feel like they should’ve chosen a different dance for quick sort – the video is even longer than the one on bubble sort!).

I understood the mechanisms behind all of them at first glance, except shell sort. I haven’t learned it before so I had to watch it more than once (sorry, systems programming midterm)  before I could have a clue of what is going on. That’s why today we’re going to learn how shell sort works.

First things first: please watch this to continue.

for-my-cakeday-i-present-my-skeptical-dog-62998
you watched it, right?

 

By the way, I do not understand what they yell  most of the time but I have some legit guesses. So let’s learn some Hungarian.

  1. öt: five
  2. három: three
  3. Hej, te szomszed!: Hey, you’re next!

…and that’s all of my Hungarian knowledge.

…sooo when a bunch of people turns to camera (like in 0:05) I will assume they are yelling “holeeey”. 

for-my-cakeday-i-present-my-skeptical-dog-62998
sceptical dog is still sceptical

Shell sort works as follows: We compare the n elements that have distance k from each other only, and then decrease k until it becomes 1. There are several ways to decrease the gap. Easiest way is to take k = n/2 and go with k = k/2 in each iteration. In this video, however, they go with “5,3,1” instead of “5,2,1”. I will take a wild guess here: if n/2 evaluates to an odd number, they start with that k and subtract 2 in each iteration. If n/2 is even, they start with k = n/2 – 1 since the algorithm should end with k=1, not k=0 (if you have any other guesses, please let me know by writing a comment below).

Let’s go step by step. This is their first arrangement:

first

This is when they say “holeeey” for the first time:

second

We should compare a[0] with a[5], a[1] with a[6] and so on. If the one on left is larger than the one on right, we should swap them (since we are looking for an increasing order).

(Note that the array elements with the same color of dot are in the same sublist, so swapping will occur only between those elements, if there is any).

third
a[0] – a[5] and a[4] -a[9] are swapped. The others just lift their hands, indicating that no swapping will be done.
This is when they say “holeeey” for the second time (or something like haj mosteve?)

fourth

Now, we are comparing a[0] with a[3], a[1] with a[4] and so on (that’s why they yell something with harow). a[0] – a[3], a[1] – a[4] and a[2] – a[5] dance as pairs but no swapping occur, so a[6] starts to dance with a[3].

fifth

Now be careful! a[6] swapped with a[3], but we still have to check a[0] and a[3] since they have a distance of three.

We check it, and see that no swapping should happen. False alarm. Phew.

We apply the same to the rest:

sixth
after some dancing, a[4] swaps with a[7] and a[6] swaps with a[9].
Then, the dancers face the camera once more:

seventh

Now, since the interval is 1, every element is in the same sublist and every one of them can swap with each other, so we apply basic insertion sort (we try to place the element where it belongs at last).

“Why should I even bother? What’s the point, really?” He thought for a moment.amca.png

“Who says there has to be a point?” he asked.

“Or a reason. Maybe it’s just something you have to do.”

 

You may ask yourself (as I also asked myself) why you even bothered to learn this algorithm since it boils down to insertion sort anyway. Now, imagine that you have a list that is almost in order except for an element or two and they are far away from each other.

deck1

If you performed an insertion sort on this list (or shell sort with gap = 1), you would have to move 3, 4, 5 and 6 to the left of 7, then you would move 2 to the left of 6, 5, 4 and finally 3, a total number of 8 moves. However, if you performed shell sort with gap = 5, you would just swap 2 and 7 and your list would be sorted.

Valla kod yazmadan bırakmam. I am currently learning Python for a course, so I gave it a shot.


def main():
    mylist = [3,0,1,8,7,2,5,4,9,6]
    shellSort(mylist) 
    print mylist

def shellSort(mylist):
    gap = len(mylist)//2 #gap is integer division of the list's length
    if gap % 2 == 0: #if even gap, make it odd
        gap-=1

    while gap > 0:

        for start in range(gap):
            for i in range(start+gap, len(mylist), gap): #start from starting position + gap, go until end, increment by gap in each iteration

                pos = i #current position
                current = mylist[pos]
                
                while pos >= gap and mylist[pos-gap] > current: #if one on the right is less, swap
                    mylist[pos] = mylist[pos-gap]
                    pos -= gap 
            
                mylist[pos] = current
        gap -= 2 #subtract 2 from gap in every iteration

main()

p e a c e   o u t

Build Your Own Maze

So far, I’ve only talked about how to solve problems. Today I will tell you how to create one for a change. You can create mazes as hard as you want and have fun watching your friends try to solve them!

ShiningMaze
mehehehehe

There are many algorithms for creating a maze, of course (♫ You’ll take the high road and I’ll take the low road, and I’ll be in Scotland before you ♫). The algorithm I will show you is called recursive backtracking. It will be easy as a Dr. Oetker pudding recipe once you know what depth-first search (DFS) and a stack means. I will try to explain them as I go on.

We start with a table like this (here, I chose a 4×8 table. You can start your maze with anything you like, it’s not important – unless you start with a 1×1 one).

maze0

We randomly choose a box to start. Then, we again randomly choose an unvisited “neighbor” to step on – either the left, right, up or down one (down-left box is not a neighbor, for example). When we travel from one box to another, we remove the wall between them. We keep repeating this algorithm until all squares are visited.

We have to be careful though – if we step to a box and that box happens to have no unvisited neighbors, we will have to take a step/steps back until everything turns back to normal. We will still mark that box as visited. This is called as DFS since we do not backtrack until we reach the very end.

As we visit boxes for the first time, we will put them in a stack. Stack is a data structure which follows the last in first out (LIFO) principle. A box of Pringles is an example of a

pringles
yup, just like a stack

stack – the last chip you will eat is actually the one which is packed first (we also use “stack” as a term in Ultimate Frisbee – usually the last one in the stack makes the first cut). We dynamically grow or shrink the stack as we continue on. The program terminates when stack is finally empty.

 

‘Nuff said. Let’s start with the box 32. I will color the visited boxes with blue and add them to a stack as I proceed (click on the images pls):

Then, I randomly chose 31. I delete the walls between 30 and 31, and mark 31 as visited as usual.

 

Then…

dustin-hoffman-rain-man-1
Uh-oooh…

We’ve reached a dead end. We cannot proceed from 31 to anywhere since all of its neighbors are already visited. We “pop” 31 from the stack and see if 30 has other neighbors. Fortunately, 30 has 29 as a neighbor so we do not need to backtrack anymore.

 

So far so good…

Let’s continue:

Obviously this maze will start at 32 and end at 1, but this doesn’t change the fact that we need to visit every box in this table, meaning that the big square should be completely blue and the stack should be empty when we finish.

It’s actually very difficult to show these step by step, so I will skip a few steps. I believe you already understood how to proceed anyway:

Again, we’ve reached a dead end. This time, one step back is not enough, so we continue backtracking and popping off the stack until we can proceed with another box.

We still have 13 to visit:

Although we see it clearly from this image, we still need to backtrack from 13 in order to see if any box is unvisited:

Aaaaaaand we-are-done!

finalmaze
yes… I know it’s the easiest maze in the world

You may now think this algorithm is not worth it since our final maze is very easy. However, I used a table of only 4×8 as an example. Also, I explained it step by step which made the creation seem so long. That’s what computers are for: once you implement this algorithm, you will see it’s a very fast algorithm. I will not give a full implementation though (if I feel like it later, I will edit here). I just wanted to show you how mazes are created with computers.

Some day, inshallah mashallah (lol), I will be able to create my own demos. Until that day comes, here is an a-mazing (lolol) animation (warning, may cause addiction):

~~IMPORTANT EDIT~~ My classmate Mahmut made an awesome demo! Please also check that out. You can play with the animation rate and grid size.

So long, folks!

Source:

  1. Check out this awesome demo!
  2. Wikipedia, of course
  3. I love this blog
  4. Easy learn tutorial – implementation

Ultimate Frisbee in CS World

(I had to dedicate this post to Özgür in order not to be a muddy woman… ask him, not me).

I joined the ultimate frisbee team after two months I started university. I must admit, I was expecting to meet people majoring in fields other than computer science since nearly all people I knew at school were in my class. Things didn’t work out as I planned though (no offense pls) (I love my teammates) (seriously, I do): 1 out of 4 people I met were computer engineers. We have over 30 people in our team, last year 8 of them were computer engineers, this semester we had 4 outgoing but 5 incoming CS people!

At first I thought this was a coincidence since computer engineers form a large part of the population of my school. They could be anywhere.

However, I saw that this was not a coincidence at all when I attended a Google Tech Talk. They didn’t mention anything about ultimate in the talk, but guess what they gave us at the end as presents together with Google pens, Android toys etc:

Snapchat-2149421391673519591
(I took like 5 and ran away lol)

That was when I started to wonder why computer engineers are inclined towards ultimate. I first thought why am playing it in the first place and I came up with some answers but before, I feel like I should talk about the sport a little because something tells me you are thinking “duh, because frisbee throwing is not an actual sport and computer engineers are not athletic”.

black-woman-with-attitude-1
oooh snap

If  you are seriously thinking this, it clearly shows you don’t know anything about this sport and you didn’t see my athletic, agile engineer teammates. I bet they would beat (most of) you in a running race.

 

Ultimate frisbee is an actual team field sport generally played with 7 people in each team. Points are scored when one team catches the disc in the opposing team’s end zone. The player holding the disc must maintain a pivot point and he cannot “travel” with the disc, he may only advance the disc to the end zone only by passing. If a pass is defensed (“D’d”), incomplete or caught out of bounds, the opposing team gains possession and tries to score in the opposing direction. The field must be 100 m to 37 m, which makes it a pretty big field especially when there are many “turn over”s in a game and you have to continuously run from one end zone to the other. (thanks Wikipedia)

One interesting thing about ultimate is that the game is self-refereed. The quality of the game relies entirely on the honesty and knowledge of the rules of the players. Ideally no player intentionally violates the rules and stays respectful while discussing the calls. This is called Spirit of the Game. SotG is very important in ultimate. In tournaments we have two awards, one is for the winner of the games and the other is for the SotG.

Here is a highlights video (women) for you:

So… why CS people like to play ultimate?

IMHO, the main reason why CS people fall in love with this sport is that computer scientists are lazy people. I used this word as a compliment though. A computer engineer always finds the easiest way to accomplish tasks and solve problems (that’s what we have been doing throughout this blog). In order to play ultimate, you have to be both athletic AND clever, else you would be running around without any meaning. You have to learn to read the disc, which means you should figure out where to run in order to read the disc, especially while catching a deep throw. You have to take the wind, the speed and the spin of the disc into account. This becomes so much fun once you learn.

Ultimate is a sport with very clear rules, so clear that if two players disagree on a call, the rule book tells them exactly how to proceed. This is also very similar to how computers (and eventually, computer scientists’ brains) process the tasks: when you give a clear, step by step algorithm, the computer/brain functions perfectly. The clarity of the rules also appeal the CS people.

What makes ultimate stand out from the other sports is SotG, and I think that is the main reason why I love ultimate very much. I like honesty and integrity and I cannot stand watching sports without real fairplay. I also like to solve problems without any aggressiveness. From what I have observed so far, nearly all CS people are also patient and calm.

I will finish this post with a Microsoft interview question:

“How many Ultimate Frisbee players are there in United States?”

0/1 Knapsack Problem or: How I Learned to Stop Coding and Rob a House

Ahoy!

It’s been over a week since I posted about another dynamic programming problem. I thought I would be posting more on winter break. Sorry about that.

I have usually written about everyday problems in this blog. Again, I will teach you a very useful, daily life application of computer science: efficient stealing.

Here we go:

Suppose you are a thief and you planned to enter a house. You know that there are only four valuable items in the house that weigh 1, 3, 4, 5 kilograms and cost 1000, 2000, 4000 and 4500 dollars, respectively. You are a very sloppy thief, i.e., you did not plan things ahead, so you brought a knapsack with a capacity of only 7 kilograms. What is the maximum total value of goods that you can steal? 

problem
(the vase is probably from Beymen lol)

In the above example, you can easily see that the wisest decision would be stealing 6000$ worth of goods. In some houses though, there will be thousands of objects with very small weights or you will have a bigger knapsack so it will definitely be harder to decide. It’s easier to find the optimum solution with a clever algorithm rather than trying every combination and calculating the values each time.

In this case, our clever algorithm will be dynamic programming.

Remember that the dynamic programming approach is all about dividing the problem into subproblems. As in the stair-climbing problem, we do not jump directly into the problem of fitting the combination of the items with the maximum total value. Instead, we check for capacities less than 7, store the maximum total value up to that capacity and increase the capacity one by one.

Let’s see this on a table:

table

I inserted the items in non decreasing order and filled the “zeroth” column (I will implement this with arrays, that’s why there is a zeroth column) with all zeros since we cannot fit anything to the knapsack if it has zero capacity. Then, we start with only the first item with weight 1 (camera) and we increase the capacity of the knapsack one by one. For each capacity, the best (by best, I mean the maximum total value) we can do with that item is to include that item if it fits. It seems that weight 1 fits to every capacity greater than or equal to 1, so we fill the table according to that:

table2
(the max total value we can get with the camera only)

Then, we consider the second item with weight 3 (laptop) together with the camera. If the capacity of the knapsack is 1 or 2, we can only fit the camera to the knapsack. If the capacity of the knapsack is 3, we can either put the camera or the laptop. We compare their values (we go one row up) and laptop turns out to cost more than the camera, so we choose the laptop. Here comes the trick for capacities bigger than 3 kg: we check for the maximum total value of the goods before adding 3 and add 3 on that value. If we are on column 4, for example, we go up and go 3 columns back and add the value of the laptop to that. If this value we have is bigger than the value when we go one row up, we write that value to that cell.

I know my attempt to explain the algorithm is very confusing, but I am sure that you will understand what I am trying to say:

table3-1
we can fit the item with weight 1 only
table3-2
we choose laptop over camera
table3-3
we check for the maximum before adding the item with weight 3, then choose to add it or not

Next, we include the items with weights 1, 3 and 4. For the capacities less than 4, the best we can do is what we can do without including the item with weight 4 (necklace). Instead of recalculating these, we directly go up one row and write the maximum total values with just including the camera and the laptop. Then, for the capacities greater than or equal to 4, we either do not include item with weight 4 to the solution (go 1 row up and write the value 3000) or we go 4 back, one up, add necklace’s value to that value. For example, for the capacity of 4, we check for maximum total value with capacity of zero and add 4000 to it or we directly write 3000. Since 4000 is greater than 3000, we choose to write 4000.

table4.jpg
(here, blue arrow means directly including the value above. orange arrow means adding 4000 to the value that the arrow comes from)

For the final row, we apply the same steps:

table5

Note that in the last row, we chose to include the value above the 5th column instead of including the one where we go 1 up and 5 back since 5000 is bigger than 0 + 4500 = 4500. Same goes for the 7th column: we chose 6000 over 1000 + 4500 = 5500.

table5.jpg
The value we want to find is the value on bottom right!

From this table, we can also see that, for example, the maximum value of goods we can steal when we have a knapsack with capacity 6 is 5500, with 5 is 5000, with 4 is 4000, and so on.

~~~~END OF TORTURE~~~~

Now, you may think implementation of this algorithm takes a loooooong time. Well, you will be surprised. All of the text above comes down to this formula:


i = current row/item, j = current column/capacity
if(i == 0 || j == 0) 
      TABLE[i][j] = 0  
else if (j < (i-1).weight) 
      TABLE[i][j] = TABLE[i-1][j] 
else 
      TABLE[i][j] = max(TABLE[i-1][j], (i-1).value + TABLE[i-1][j-(i-1).weight])

(For all j, TABLE[0][j] = 0 in the above formula. I did this in order not to manually fill in the first row. That’s also why I am looking for weights and values of i-1 instead of i. I did not show this on the tables, sorry about that.)

TL;DR What we do here is for the capacities less than the weight, we check for the maximum total value we found before, without including that weight. If the capacity is greater than or equal to the weight, we either do not include the weight and directly write the maximum total value we found before that fits that capacity or we include that weight and check for the maximum value subtracting that weight from the capacity and check for the maximum value at that capacity without including that weight.

Easy, right?

Well, maybe it will be easier if you also see a full implementation (in C++ this time):


#include <iostream>
#include <utility>
using namespace std;

int capacity; int numOfItems;

//returns the max value of two integers
int max(int a, int b) { return (a > b) ? a : b; } 

int knapsack_01(pair<int, int>* items){
    int TABLE[numOfItems+1][capacity+1]; //construct the table
    
    for(int i=0; i<numOfItems+1; i++){
        for(int j=0; j<capacity+1; j++){
            if(i == 0 || j == 0) 
                //fill TABLE[0][j]s and TABLE[i][0]s with 0s
                TABLE[i][j] = 0;  
            else if (j < items[i-1].second)
                TABLE[i][j] = TABLE[i-1][j]; 
            else
                TABLE[i][j] = max(TABLE[i-1][j], items[i-1].first + TABLE[i-1][j-items[i-1].second]);
        }
    }
    return TABLE[numOfItems][capacity];
}

int main(){
    capacity = 7;
    numOfItems = 4;
    
    //a pair holds one item
    //items[item].first = value of item, items[item].second = weight of item
    
    pair<int, int> items [numOfItems] = {make_pair(1000, 1), make_pair(2000, 3), make_pair(4000, 4), make_pair(4500, 5)};//array of pairs (items)
    
    cout << knapsack_01(items) << endl;
}

Aaand that’s pretty much it. If you have a computer with you while stealing (…or you can steal one from the house), you can copy and paste the code above to a C++ shell and see the result. You can always change the capacity and the items.

computer_thief.jpg
(formal attire is not required)

(If you get caught in the act, you don’t know me and you didn’t read this post.)

Source:

  1. Similar source code
  2. Tushar Roy strikes again!