Tuesday, December 25, 2012

Traversing binary trees


It can be hard to remember how to traverse trees by name. It can also be hard to understand the difference between traversing in different ways(postorder, preorder, inorder, level order, etc). I try here to make it easier for the reader to understand the different ways of traversing a binary tree. Intuition is the key to remembering(and visualization ofcourse).


I use the words parents and children for the elements in the tree instead of nodes, root, branches and leafs. I think those words are easier to describe what is going on without getting anyone too confused.



Recursive traversal


I want to firstly point out that this method is commonly called "depth/height traversal". However I use the word recursion as it seems more appropriate to me.
There are three ways to traverse a tree recursively. The only real difference between them is the order we visit the parent node.

  • Pre order ------- here we visit the parent in the beginning

  • In order --------- here we visit the parent second

  • Post order ------ here we visit the parent lastly



Because recursion is hard to grasp and even harder to have a visual insight of the goings, we will use a simple example to begin with. We start by examining, with all three methods, this binary tree:
treebin_3nod_25dpi

Pre order


Here the path we follow to traverse is:

  1. Parent

  2. Left child

  3. Right child


preorder

Applied to our example tree:
preorder_example

So if we use pre-order to traverse the example binary tree, then we would get the values(by order we visited them):
[sourcecode light="true"]
4, 2, 7
[/sourcecode]

In order


Here the path we follow to traverse is:

  1. Left child

  2. Parent

  3. Right child


inorder

Applied to our example tree:
inorder_example

So if we use in-order to traverse the example binary tree, then we would get the values(by order we visited them):
[sourcecode light="true"]
2, 4, 7
[/sourcecode]

Post order


Here the path we follow to traverse is:

  1. Left child

  2. Right child

  3. Parent


postorder

Applied to our example tree:
postorder_example

So if we use in-order to traverse the example binary tree, then we would get the values(by order we visited them):
[sourcecode light="true"]
2, 7, 4
[/sourcecode]

The bigger picture


All this seems simple for a tree with only three nodes. But what happens when we have a huge tree with multiple nodes? Which node would we visit first?

The answers are rather simple but there are not good resources actually to give a good visualization of how a recursive traversing can look like.

So let's start by taking this big tree:
treebin_7nod_spaced

The trick is to start by seeing see the whole structure as a tree with three nodes. In all three traversing methods we start with the node on the top of the tree: the root node. We thus see that as the parent in the beginning of the traversing. All the rest of the nodes on the left is considered the left child and everything on the right of it is considered the right child.
treebin_7nod_spaced_cells_abc
The bigger complex tree has been compressed to a three-node tree. We can now start traversing it with whatever -order traversal method we want.

I will demonstrate how I would go with in-order traversal. Read this line by line.

  1. First I visit the left child: node b

    1. I now get into this subtree and visit the left child: 5

    2. Then I go to the parent node: 2

    3. Then I go to the right child: 9



  2. Then I visit the parent: node a

    1. Here there is no parent or children. The only thing I can do is to return the value of the single node: 4



  3. Then I visit the right child: node c

    1. I now get into this subtree and visit the left child: 6

    2. Then I go to the parent node: 7

    3. Then I go to the right child: 1




Note that 1, 2, 3 are traversal of the a, b, c nodes. All nested traversals are traversals for the nodes inside a, b and c.

An even more complicated tree could look like bellow. However exactly the same principles are valid.
treebin_nod12_cells
This looks a lot like a fractal, doesn't it? That's because fractals are actually based on recursion. The only difference with this example is that the recursion is not endless but instead is made of three different levels: the outer level where we see three cyan circles, the level where we see three green circles and the level where we see three nodes(inside each green circle).

Traversal by Breadth


All methods discussed earlier are actually what is called traversal by height or depth. I am not so sure as to why we call it that instead of traversal by recursion as the real difference between depth traversal and breadth traversal is:

  • Height traversal uses recursion.

  • Breadth traversal is linear, going from one node to the next as you see the whole tree.




Traverse by level


Traversing by breadth or by level(which is more intuitive) is the simplest method to traverse a tree. You can see the nodes of an arbitrary tree grouped into different levels depending on how close to the root they are. In the bellow tree I have numbered the different level of nodes:
treebin_7nod_levels
Node with value 4(the root) belongs to level 1. Nodes 2 and 7 belong to level 2. Lastly, nodes 5, 6, 9 and 1 belong to level 3.

To traverse the tree with traversal by level we just go from left to right on each level jumping from node to node like this:
treebin_7nod_levels_trav1

treebin_7nod_levels_trav2

treebin_7nod_levels_trav3

Thus we traverse the nodes in this order:
[sourcecode light="true"]
4, 2, 7, 5, 9, 6, 1
[/sourcecode]

If the tree would be more complicated or not complete(missing nodes at some level) then we just jump over the missing nodes and get to the next one. An example follows bellow.

treebin_12nod

treebin_12nod_levels

treebin_12nod_levels_trav

The nodes visited in order:
[sourcecode light="true"]
4, 2, 7, 5, 9, 6, 1, 26, 13, 10, 8, 3
[/sourcecode]

Thursday, December 6, 2012

Installing Ubuntu on Samsung 5 (SSD+HDD)



I got some messages on Ubuntu Forums on how about installing Ubuntu on the Samsung 5 and especially the model NP530U3C-A07.
I make this guide to help whoever else gets into this problem as the installation is not as straightforward as it may seems.

Boot from USB


I assume you have a bootable USB with Ubuntu. Then follow these steps:

  1. Make sure you insert the USB stick in the USB2 slot and not the USB3(it has a blue contact)

  2. Disable "Fast BIOS Mode" from BIOS>Advanced

  3. Disable "UEFI" from BIOS>Boot

  4. Reboot, and in BIOS>Boot set your USB stick as the first device to boot from

  5. Save and reboot



Install


The Samsung NP530U3C-A07 and some others don't use hybrid hard discs. What they have is a normal HDD and then a very small SSD of about 4 to 30GB. Both of them are seen as separate devices so it's easy to distinguish which is which by their size.

On the bootup of Linux choose Install Ubuntu(or either Try Ubuntu and then Install from there). When you get to the point where you have to choose where to install("Installation Type"),



choose "Something Else". A new screen will pop out letting you choose where to install Ubuntu, format, make partitions, etc.  Follow carefully the bellow:


  1. Choose and format the smaller disk (SSD) to install Ubuntu

  2. Choose and format the bigger disk (HDD) to as many partitions you want. I format mine as a big ext4 to just store media. The thing to pay attention to is to not reformat this drive in the future as that would probably screw up the bootloader. That happened to me.

  3. On "Device for bootloader installation:" choose the HDD. It doesn't matter if you choose the device itself or the partition on it.


After Install


Not everything works out of the box but luckily for us there are things that can fix most of them. Bellow are several fixes for different problems.

Flickering screen when changing brightness



  1. sudo add-apt-repository ppa:voria/ppa

  2. sudo apt-get update && apt-get install samsung-backlight



Fn keys not working



  1. sudo add-apt-repository ppa:voria/ppa

  2. sudo apt-get update && apt-get install samsung-tools


Monitor doesn't "remember" the brightness after restart


I haven't fixed this but a workaround is to manually set a default brightness value for every restart. You can do that by automatically editing the /sys/class/backlight/acpi_video0/brightness on every boot. For that we add a line on /etc/rc.local a file that runs on every boot of the OS.


Add echo 31 > /sys/class/backlight/acpi_video0/brightness to the file /etc/rc.local just before line "exit 0"

Your rc.local file should look something like this:

[sourcecode light="true"]
#!/bin/sh -e
#
# rc.local
#
# This script is executed at the end of each multiuser runlevel.
# Make sure that the script will "exit 0" on success or any other
# value on error.
#
# In order to enable or disable this script just change the execution
# bits.
#
# By default this script does nothing.

echo 31 > /sys/class/backlight/acpi_video0/brightness

exit 0
[/sourcecode]
You can change the value 31 to what suits you. You can see what current brightness is with

[sourcecode light="true"]cat /sys/class/backlight/acpi_video0/brightness[/sourcecode]

Extras


Mounting hard disc on bootup


Probably your hard disc isn't mounting automatically on bootup as it doesn't have any system files. For this we need to edit the fstab file and set the HDD to be mounted automatically on system startup.


  1. sudo gedit /etc/fstab

  2. Add an entry for your hard disc. To get the UUID of your hard disc, just type blkid. Add a new record with default settings and appropriate type. The fstab should look something like this in the end:

    [sourcecode light="true"]
    #
    proc /proc proc nodev,noexec,nosuid 0 0
    UUID=fdb6fc55-00a1-4ef6-b65b-27e14140f6c2 / ext4 discard,errors=remount-ro 0 1
    UUID=900c5900-225a-4c43-953d-f226b8a4cef4 none swap discard,sw 0 0

    #Hard disc
    UUID=8af90249-881c-4e2a-b55c-85b6a66c3767 /media/Hitachi ext4 defaults 0 0
    [/sourcecode]



Sombolic links(shortcuts) to HDD


If you use the directories Downloads, Movies, etc. in your home directory it should be wise to make shortcuts for them so they point to the hard disc. There are two major reasons for this. First of all, media files are not going to be "faster" if they are on the SSD so why sacrifice space by using the ultra small SSD and not the huge HDD? Something else to consider is that SSD drives have a specific number of write cycles before they die. Therefore it's good to have all kind of files that are going to be written/rewritten all the time, on a HDD.

Symbolic links are the same thing as shortcuts in Windows. They are just files that point to an other place, in our case the hard disc.


  1. First make the apropriate directories on your hard disc. For me the structure for those directories look like this:

    [sourcecode light="true"]
    /media/Hitachi/Downloads/
    /media/Hitachi/Videos/
    /media/Hitachi/Music/
    /media/Hitachi/Documents/
    /media/Hitachi/Pictures/
    [/sourcecode]

  2. Delete the already-there folders in home directory:

    [sourcecode light="true"]
    rmdir ~/Downloads
    rmdir ~/Videos
    rmdir ~/Music
    rmdir ~/Documents
    rmdir ~/Pictures
    [/sourcecode]

  3. Make the symbolic links. BE CAREFULL now. You have to be in the folder where you want your symbolic links to appear in:

    [sourcecode light="true"]
    cd ~
    ln -s /media/Hitachi/Downloads/ Downloads
    ln -s /media/Hitachi/Videos/ Videos
    ln -s /media/Hitachi/Music/ Music
    ln -s /media/Hitachi/Documents/ Documents
    ln -s /media/Hitachi/Pictures/ Pictures
    [/sourcecode]



To check that everything is done correctly type

[sourcecode light="true"]
ls -l | egrep "^l"
[/sourcecode]

That shows all symbolic links in current directory.