Breadth-First Search

Breadth-first search is a search algorithm to find something in an tree. This search algorithm utilizes a queue to keep track of all the nodes that the algorithm will explore. If you're not sure what a queue is then you should take a look at it here.

What basically happens:
The search algorithm starts at the root node(A), and looks at each node of its children before going on.

What specifically happens:
Let's say that the goal is to find E.
The search tree starts at the root node(A) added into the queue then popped, and adds it's children into the queue. If the node it is at is not a goal, it enqueues its children into the queue. If it is the goal then the algorithm returns and stops. Here are some of the steps:

1. We start with A dequeued from the queue. Since A is not the goal and it has children, A's children are enqueued. Queue = [B, C]

2. B is dequeued from the queue and its children are enqueued. Queue = [C, D, E]

3. C is dequeued from the queue and its children are enqueued. Queue = [D, E, F, G]

4. D is dequeued from the queue and its children are enqueued. Queue = [E, F, G, H, I]

5. E is dequeued from the queue and it is our goal, so we stop.

Think about if we are searching for M. What would our path be and what would happen?

Why don't we need an explored list compared to Depth-first algorithm?
Because we search everything level by level, there is no need to keep track of explored nodes, whereas Depth-first has to go back up the tree.

Read More

Depth-First Search

Depth-first search is a search algorithm to find something in an tree. This search algorithm utilizes a stack to keep track of all the nodes that the algorithm will explore. If you're not sure what a stack is then you can read about it here.

What basically happens:
The search starts at the root node(A), and continues to travel down until it reaches a leaf node. Once it hits a leaf node, it goes a step until it can travel downwards again. This continues until it has either found what it was looking for, or until it has explored all of the nodes and found nothing. The path happens this way: (A, B, D, H, I, E, J, K, C, F, L, G)


What specifically happens:
Let's say our goal is to find G.
The search starts with the root node(A) and pushed into the stack, and continues to travel down until it reaches a leaf node. A leaf node is a node that does not have any children. At every step it checks to see if the node has already been explored. If it has been explored, it is simply ignored and continues looking in the stack. If the node has not been explored, it adds any children(that have not been explored) into the stack and adds itself to the explored list. If it hasn't found the goal, then it continues to search until it has found the goal or that the tree is all explored. Here are some of the steps:

1. A goes down B, D, and stops at H.  Explored list = [A, B, D, H]  Stack = [C, E, I]

2. H is a leaf so it doesn't add any children to the stack, I is popped off and added to the explored list.
    Explored list = [A, B, D, H, I]  Stack = [C, E]

3. I also doesn't have any children to add to stack, E gets popped off. It's added to explored and its children added to the stack.
    Explored list = [A, B, D, H, I, E]  Stack = [C, K, J]

4. J is popped off the stack. Because it is a leaf no children are added to the stack. Same thing happens with K.
    Explored list = [A, B, D, H, I, E, J, K]   Stack = [C]

5. C is popped off the stack and any of its unexplored children are added to the stack.
    Explored list = [A, B, D, H, I, E, J, K, C]  Stack = [G, F]

6. F is popped off the stack and, any unexplored children added.
    Explored list = [A, B, D, H, I, E, J, K, C, F]   Stack = [G, L]

7. L is popped off the stack and there are no children to add to the stack.
    Explored list = [A, B, D, H, I, E, J, K, C, F, L]   Stack = [G]

8. G is popped off the stack and because our goal was to find G, we stop our search.

Imagine that there is a search for M. What would happen? The algorithm should return something that signifies nothing was found.

Why do we need an Explored list?
The reason that we would need an explored list is to prevent already traversed nodes from being rechecked, and prevent its children from being added back into the stack. Without the explored list the algorithm would end up in a loop forever.
Just like looking for something in the grocery store, you wouldn't want to go back to an aisle you already looked in, because you remember that you've looked there already.

I hope this clears up any muddy ideas you have about this search algorithm. Feel free to let me know if I've made any errors, grave or not.

Read More

Database Concepts - A Short Post about the Relational Database Model

via Wikipedia

Relational Database Model:
The relational database model, different from the entity relation model, shows specific data and information about a database table. A relational database model contains two parts: An instance, and a Schema.

Schema:
The schema is specific name of the relation, or the name of each column. If you think back to the Entity-Relationship Diagrams, there are names that have relationships to each other, these names would be the part of the schema. In the above picture, the schema would be the part that says "login", "first", and "last."

Instance:
The instance are the rows of data that pairs with the schema. In the above picture, the instance would be the rows of names.

Relations:
As you can see from the image above, the specific row of information for "Mark" is linked to another table that contains the specific key's phone number. This, is what the Entity Relationship Diagram has drawn out; the connection between one login key to a foreign key.

Usage:
With the Relational Database, we can use query language to query for data. Although our queries can be efficient, the DBMS is mostly responsible for making queries efficient.

Read More

Setting Up MySQL

Hi Everyone!

I know I haven't been posting much these past few months, I was busy with many other things and I decided to take a breather with blogging. However, things have cleared out of my way now, and I will start again with posts.

Installing:

For Linux users, type the following into your command line:

shell>sudo apt-get install mysql-server
shell>sudo apt-get install mysql-client

For Mac and Windows users, you have to download the installer here. Make sure you check 32 or 64 bit! Follow the steps that the install gives, and you should be fine!

Using MySQL:
To start up MySQL:  type the following commands in the terminal:
shell>mysql -u root -p
It would ask you for your password, since you need to be the root user. The installation should ask for you to set a password for MySQL, which is optional. If you do not wish to set a password, you can just click enter when it prompts you to type in a password.

If you did not set a password for MySQL, you can disregard the "-p" part. You can also just type it and click enter when it asks for a password. If you get in, you should see something like this:
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 1
Server version: 5.6.27 MySQL Community Server (GPL)
Copyright (c) 2000, 2015, Oracle and/or its affiliates. All rights reserved.
Oracle is a registered trademark of Oracle Corporation and/or its
affiliates. Other names may be trademarks of their respective
owners.
Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.
mysql>

For Windows users, here's the way to start it up. I haven't tried this but I hope it helps.

To create a database: type the following in the MySQL command line:

mysql>create database database_name;

Notice here that you need a semicolon to show that you're done talking. We'll see later how that semicolon can be changed to something else.

To go into a database: type the following in the MySQL command line:

mysql>use database_name;

type in "mysql --help" in you're computer terminal to see many, many other commands.

Changing MySQL Password:

In order to change your MySQL password you will need to log onto MySQL first. After that you type the following:

mysql>grant all privileges on *.* to root@localhost identified by "new_password";

Here, the new_password should be in the quotes.

Changing the Terminator Symbol:

The semicolon at the end of each command is usually called the terminator, which tells MySQL that you're done with a statement. But what if you wanted to paste a big chunk of commands? Or paste in a function? You can change the terminator symbol before you paste code, and change it back to semicolon afterwards. Here's how to change it:

mysql>DELIMITER YOUR_TERMINATOR

example: mysql>DELIMITER done

In this example, assuming you don't have the word "done" in your code, will end your set of commands when it find the word "done." To change it back to semicolon you would do the same except with a ";"

That's it! Pretty Simple huh? If you have any problems look it up, many people may have the same problem. You can also feel free to post a comment here, and please do so if my post here helped you! I really appreciate knowing that I have helped! 'Til next time.

*It also seems that the spacing of this post is really odd, I'm trying to fix it but I haven't figured out the cause so far.

Read More