Binary Search

Binary search is one the simplest search algorithms(most are pretty simple) to implement. However, first it assumes an important property of an array that isn't always true; the array is sorted. This search is based on the number of elements(length), and we fold the array in half each time, which makes search time logarithmic.

First, you see in the diagram above that the list is already sorted. Next, we label the first index as the lowest number(LO), the last index as the highest number(HI), and the middle index as the index between lowest and highest(MID). Keep in mind that these are just markers for indices and we aren't moving any of the array elements around.

In the diagram that's searching for the number 16 and we realize that the number 16 is smaller than the number in index MID. As a result, we move the high index right before the mid index, and we reorganize the mid index as the middle of lo and hi again. This is what cuts the array in half, and in another half every time it checks MID. The resulting indices is represented in the second row of the diagram.

The last row of the diagram, just shows that when we check MID again here we find that it matches our search number, and thus re return the MID index and we are doneeeeee!!!!

In the case that the number we are searching for is higher than MID, then we'd move LO right after MID and re-position MID. Also, in the case that we don't find any numbers, we'd just return -1.

We repeat these steps several times, folding HI and LO in halves until we've either found our number or we've looked through all the possible index elements.

Here's how it would look in java:

import java.util.Arrays;

class BinarySearch{
.
.
.
    public static int rankIndices(int key, int[] a){
        //assume here that the array is sorted already
        int lo = 0; //index 0 is lowest
        int hi = a.length - 1;                      //and the last index is highest
        while(lo <= hi){                         //stop when hi and lo have become the same index number
            int mid = lo + (hi - lo) / 2;           //find the middle of hi and lo
            if (key < a[mid]) hi = mid - 1;      //key is between mid and lo, move hi before mid
            else if (key > a[mid]) lo = mid + 1; //key is between mid and hi, move low after mid
            else return mid;                        //The middle number is the number we look for
        }
        return -1;
    }
}

And here's some python:

def binarySearch(key, a):
    ## assume that the array is already sorted
    lo = 0
    hi = len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2  ##postion mid, integer division
        if key < a[mid]:
            hi = mid - 1           ##key is between mid and low, move hi before mid
        elif key > a[mid]:
            lo = mid + 1           ##key is between mid and hi, move lo after mid
        else:
            return mid             ##mid is where our number resides
    return -1                      ##number is not found


print binarySearch(2, [0, 1, 2, 3, 4, 5, 6, 7]) ##just a test

Read More

Relational Algebra - An Intro of it's Use and Operators

Consider the following database scenario:
You are planning a high school graduation party for the school. You keep data on those who have registered to be present on that day. We have students(S), teachers(T), staff members(SM), parents(P), and siblings(C) of the students, followed by relatives(F), and a list of registered people for the party(R). We also have information about food allergies(A). If we were asked to find out the group of people who is a 25 years old or older and a parent of a student who has a peanut allergy, what would you query?

SELECT S.name
FROM S
WHERE S.allergy='peanut' and S.parent=
               (SELECT P.name
                FROM P
                WHERE P.age >= 25)

As we can see here this is not the simplest query. Imagine if we had to query for something way more complex than this. Would you sit there and try things out until you got the right query? Would a database always have someone behind it entering queries? Not always(Probably not). It can be done of course, but there's a better solution for this.

Relational Algebra: relational algebra is a way of expressing relations. Just like algebra is a way of expressing numbers and their relations, relational algebra is a way of expressing things in a database with their set of operators. It can also be used to describe constraints of a database, though we'll elaborate on that in another post.


Relational Operators: relational operators are analogous to arithmetic operators; they operate on a certain operand and describes the operands' relationship to each other. Below we will jump into some of the basic operators.

1. Selection(σ): Like in SQL queries we are selecting a subset of rows from a relation(operand)
2. Projection(π): Keeps certain column(s) of a relation, I don't think this has an SQL counterpart
3. Cross-product(×): Also called Cartesian product. This takes relations and combines them
4. Join(⋈): Connects two relations with some sort of condition
5. Set-difference(−): an existing tuple(s) in one relation but nonexistent in another relation
6. Union(∪): Tuples that exist in one relation OR another relation. Realize that the "or" I'm talking about is logical or.
7. Intersection(∩): Tuples that exist in both of two relations
8. Renaming(): renames a relation or an attribute.

Operator Examples:
1. Selection(σ) & Projection(π): All of those who have a peanut allergy from the student list(S)
π_S.name(σ _{allergy='peanut'}(S))

3. Cross-product(×): All of those who have peanut allergy and are a student or teacher
π_S.name(σ _{allergy='peanut'}(S × T))

4. Join(⋈) All of those who have peanut allergy and are a student or teacher
π_S.name(σ _{allergy='peanut'}(S ⋈ T))

5. Set-difference(−): find the students who have an allergy but did not reserve a place for the party
π_S.name(σ _{allergy='peanut'}(S)) - π_S.name(R)

6. Union(∪) & Renaming(): The list of students and teachers that have a name of "Sara"
π_R.name(σ _{R.name='sara'}((R , (S ∪ T))))

7. Intersection(∩) & Renaming(): The list of people who's name is "sara" and is both a parent and a teacher
π_R.name(σ _{R.name='sara'} ((R , (P ∪ T))))

Read More

MySQL Queries and commands

In this post I hope to go through some MySQL commands that would help users get started and used to using it. Remember that semicolons are default used to show end of command/queries.

Creation/Deletion Commands

USE <database name>:
This is used to enter an existing database.

CREATE DATABASE <database name>:
This is used to create a database.

CREATE TABLE <table name> <name of variable, variable type>:
This is really similar to database creation, although it has many more entries for each attribute. Here are some commonly used ones:

• CHAR(N), where N is length between 1-255. Default is 1
• VARCHAR(N), where N is length between 1-255. Unlike CHAR, you must define a length.
• INT, an integer entry. The number should be between -2147483648 and 2147483648. If you need a bigger number, you can use
• BIGINT the integer max depends on signed or unsigned.

SHOW TABLES:

Shows all available tables in a database

SHOW DATABASES:

Shows all existing databases in MySQL

DESCRIBE <table name>:

This shows how you've defined the table, what variables and types.

DROP TABLE <table name>:

This totally deletes the table, if it exists of course.

DROP DATABASE <database name>:

This deletes an existing database

Query Commands

SELECT * FROM <table name> WHERE <some condition>:
Select *  means it finds some table and return everything. If you want to find something specific you would do SELECT <attribute name> FROM <table name>  and if you want to return pairs of things you can specifiy the attributes with commas.
Ex.  SELECT name, age FROM attendees WHERE age > 20;

FROM describes where you are searching/querying.
WHERE is specifying conditions, you can specify several conditions in separated AND or OR.

AND:
The and keyword is used to specify that the combined conditions must all be satisfied.
Ex.  SELECT name, age FROM attendees WHERE age > 20 AND age < 30;

OR:
The or keyword is used to specify that one of the combined conditions must be satisfied.
Ex.  SELECT name, age FROM attendees WHERE age > 20 OR age < 10;

These are just the few basic commands/queries that you can do, and I hope that this helps you get started with building a database! I also plan to publish a post that goes into more queries, since most database management concepts are about these queries.

Read More