Hanging in the balance

I'm really running out of puns for titles. In this post I wanted to talk some more about Binary Search Trees. But more specifically how to balance them - that's where I left off on my lat post.

The most common technique for balancing a tree is rotation. Rotating a tree is quite simple:

Lets say we have a tree:
     20
    /    \
 10    30
  /\
5 15
If we rotate it right we get
10
 /  \
5  20
    / \
 15  30
And vice versa.

As you can see that really didn't help much since the balance of left and right only differed by 1.
But if it differs by 2..
1
 \
  2
   \
    3
Rotate left and...
    2
  /    \
1       3
Bam! A balanced tree. A tree like that will become way more efficient add items to.
Actually properly implementing tree rotation is a lot more complicated, but feel free to give it a shot and let me know how it goes.

What I just showed you is based off an AVL tree(see link below).
There is also a different way to balance - using red-black trees.
It still uses rotation but the way it figures out what to rotate is a little different.
Check it out below!


I've thrown in some links here for you guys to check out if you'd like to learn more:
http://pages.cs.wisc.edu/~ealexand/cs367/NOTES/AVL-Trees/index.html
http://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html

Once again, thanks for reading. I'll probably make another post this week so stay tuned!

Sorting it all out

Well, I have missed a couple of SLOG entries over this term, so I’m gonna try to make up for it by posting a few today. In this one I want to talk about sorting algorithms. (In the spirit of holidays this post also includes lots of flashing coloured things) We went over the basic and/or most common sorts:

Bubble

Image by Wikipedia User Swfung8

Insertion

Image by Wikipedia User Swfung8

Selection

Image by Wikipedia User Joestape89

Quick

Image by Wikipedia User Matt Chan

and last but not least Merge

Image by Wikipedia User Swfung8

However the world of sorting doesn't end there. One sort I thought of, and I believe we may have done in class was using a binary tree to sort. You make a Binary search tree and add items accordingly, and then do an inorder traversal of it. The performance of such a sort is quite good: O(n log n) on average )( n) in best case. The worst case is a bit more interesting though where you can have a balanced or unbalanced BST. Balanced means the tree's height is the minimum (or close to) of what it can be (log2 n [thats "log base 2 of n"]) and unbalanced means it is more. Balancing a tree can be quite the overhead but it doesn't have to happen upon every insertion. 

The difference in worst case performance is O(n log n) for balanced and O (n^2) for unbalanced.

Balancing a tree seems rather tricky and I have yet to figure it out exactly, but I hope this sparks some interest in some of you.

Anyways that concludes this post, see you guys next week (actually like a few hours).

Every problem has a solution

Another week, another slog post. Unfortunately I skipped last week due to an excessive amount of work, but since this week is a long weekend, I can afford to type up a post. First thing is first: the solution to last post's monkey words problem. I'm gonna paste it as it is in C# primarily because I'm lazy, but also because it adds some challenge and diversity. And also braces.

//Rules
//MW = AW
//MW = AW + "N" + MW

//AW = "A"
//AW = B + MW + S


//Verification algorithm 2 (New and improved)

private static bool IsMonkeyWord(string word)
{
    if (IsAWord(word)) //MW = AW
        return true;

    if (word.Contains('N'))
    {  
        for (int i = 0; i < word.Length; i++)
        {
            string first = "";
            string last = "";

            // Go through each n and test if everything before it is AWord and everything after is MonkeyWord
            if (word[i] == 'N') 
            {
                first = word.Substring(0, i);
                last = word.Substring(i + 1);
                if (IsAWord(first) && IsMonkeyWord(last)) //MW = AW + 'N' + MW
                    return true;
            }
        }
        return false;  
    }
    return false;
}

private static bool IsAWord(string word)
{
    //Check for null or empty
    if (word == "" || word == null) 
        return false;

    // AW = 'A'
    if (word == "A") 
        return true;

    //AW = 'B' + MW + 'S'
    if (word[0] == 'B' && word[word.Length - 1] == 'S')
        return (IsMonkeyWord(word.Substring(1, word.Length - 2)));
    return false;
}

As you can see the solution is pretty straight forward. Two functions that recursively call each other to verify the monkey word. Its pretty much a simple implementation of the rules

As for things more relevant to the course: T2 is coming up! Seemingly there's gonna be mostly trees and traversal as well as Big-Oh stuff. I'm still not quite sure how to judge and classify the efficiency of an algorithm based solely on it's code/the algorithm itself; i.e. without timing it. Would you just go through it manually with a small data set and count how many operations it does? This doesn't seem practical to me, but then again, maybe I'm just that incompetent.

Well that concludes this relatively short post. I didn't want to put too much, again primarily because I'm lazy, but also (always a second excuse!) because the code up there adds a lot of volume and people's attention spans these days are rather short, Aren't they?

Don't forget to leave some comments/feedback below! Did you solve the monkey problem? Have a better solution then mine? Want to discuss Big-Oh? All comments are welcome!

Linking it all together + a cool little monkey thing...

Alas, another week, another blog post.

Despite the dawn of Assignment 2, I want to spend this post talking about linked lists, and some other stuff.

I've had some experience with linked lists in high school - but it was at a pretty basic level. Making a list out of nodes, traversing it, finding items, adding, inserting removing, etc - basic stuff. However we also got to deal with some other interesting things. For example, what if each list node contained not only a pointer to its next node, but also to its previous? This would be a Doubly Linked List. Something like this could be visualized practically in something like a web-browser - every page gets added to the end of a list and you can go back and forward in the list, one element at a time. Another type of linked list is a Circular list (I like to call them Circly lists, you'll see why in a bit) - and its feature is that the last element points back to the first. Now what if you take a doubly linked list and link the head to the tail and vice-versa? You get a Circly-Doubly-Linked-List! As comedic as the name seems something like this is quite applicable. Lets take a music playlist as an example. Each song is a node and is doubly linked to its neighbors (so you can skip forwards or backwards). Now what happens when the user turns on "Repeat Playlist"? The first and last nodes get linked, and so the list becomes a Circly-Doubly-Linked-List.

On a totally unrelated note...
Now remember that other thing I wanted to talk about? Well here it is. In High school we got a quite interesting recursion assignment and I thought I would post it here for those who want to take a shot at it - the comical nature of the whole thing combined with the decent challenge makes it a good load of fun. I also think its kinda up the same alley as A2 (just much simpler of course).

Monkey Words

Your goal is to make a program (in any language of your choice, I did it in C#, you can use python) that will determine if an input word is a monkey word (a word from a monkey's vocabulary).

A Monkey Word can be one of two things:

-It can be an A-Word

-Or it can be an A-Word followed by "N" followed by another Monkey Word.

An A-Word can be one of two things:

-It can be just the letter "A"

-Or it can the letter "B" followed by a Monkey Word followed by "S"

Here are some examples of valid words:

BANAS

BANANAS

BASNANA

BASNANANBAS

BANANANANBANASS

BBBANANASNANASNANASNA

Here is a link to two text files you can test with (each line is one word) as well as my version of the program (so you can test your own words and profile [time] your algorithm).

All the words in False1.txt are not valid Monkey Words, and all the words in True1.txt are valid words.

http://snk.to/f-chjqv35k

My algorithm is a total of two methods and 44 lines (including whitespace and documentation).

Let me know what you think of the problem! Was it easy? Hard? If anyone is interested I can post my solution next week.

Well this was quite the post. I hope you enjoyed reading it, and please comment and let me know what you think. Until next week!

Barking up the wrong tree

This week has been a lot about trees. Obviously I mean binary trees not wooden ones. We've been traversing them, picking them apart, and building them back up. As much as I've heard about binary trees before, I've never actually gotten around to seriously working with them. As much as I dislike python syntax, I have to admit that working with trees is much easier in python than the other languages I'm used to.

I'm writing this blog a bit later than I should be (tuesday as opposed to last friday) but at the same time I want to take this opportunity to talk about the new assignment (and exercise). Regular expressions are quite an invaluable tool, and I'm really looking forward to learning about them, even at the simplified level we are provided with. I'm currently working on a personal project, a component of which is document traversal and indexing, and I think regular expressions are just what I need.

Regular expressions are not exactly intuitive however. With expressions like
^[+-]?(\d+\.?\d*|\.\d+)([eE][+-]?\d+)?$ readability is obviously a concern (looks like what they use to censor swearing in cartoons), but I'm guessing its just a matter of getting used to.

As for exercise 5 - it seems pretty straight forward. Part A is obviously significantly easier requiring a simple traversal of the tree and passing along an integer. As for Part B, it seems like I could use a similar recursive traversal as Part A but store the roots separately. I really haven't given all that much thought to it yet, but it does at least seem easier than E4.

Well, that concludes my slog for today (pun intended), thank you for reading it!

P.S. I'm looking for a better name for this blog, suggestions appreciated!

Cheezus

I've never blogged before. I've haven't really even read blogs before. But I guess there's a first time for everything. Here goes.

Alas, the first assignment is over. There was a lot of recursion, and just as much hair pulling.
In the end I did accidentally submit the assignment with the number of disks hard coded, but I fixed it shortly after, and hopefully Danny will consider my new version, since its just a one line difference. I found it interesting that the method that found the ideal value of i (where i is the point at which to split the original stack of cheese) exponentially increased in the time it took as the number of cheeses increased. I'm assuming this is because the method is both iterative and recursive (recurative?), but it made me wonder if there is a more efficient way of solving the problem.



In this post, I also want to comment on OOP and recursion.

OOP is Object Oriented Programming and in my opinion one the most important things to get a solid grasp of in the programming world. Object oriented programming means representing every component of your program as exactly that: an isolated component, in your code. Every component needs to care about itself and only about itself. This concept is extremely useful in organizing code, keeping it neat and tidy, as well as easy to follow. It goes hand in hand with other concepts such as inheritance and polymorphism.

Recursion is a simpler concept to grasp - it is simply when a method or object calls or refers to itself to accomplish a task. Recursion is very useful for specific types of problems, but a lot of problems don't necessarily require it. With that said, the problems that do need a recursive solution, can often be solved with an iterative one, but the recursive one is often more efficient, more flexible, and shorter.

Well that settles the end of my first slog. Please leave comments and feedback since, again, I've never blogged before so I would love to know how I'm doing.

Until next week!