Linear Merge Sort

Linear Merge Sort

I probably just blew your mind with the title, right? :D But no, I'm not kidding. Today it suddenly occurred to me that I can do a linear merge sort. However, there's a catch. I've shifted from serial programming to parallel programming.

Yesterday, I started learning about parallel programming on the GPU using CUDA, through an online course at Udacity (https://www.udacity.com/course/cs344). If you haven't heard of Udacity, it's an amazing website where you can learn a whole lot about computer science for the beautiful price of Free.

Now, here's my algorithm:

1. Lets say my initial list is [a0, a1, ..., aN]
2. The CPU then runs N/2 threads on the GPU that do the merging step of merge sort on pairs of elements of the list. a0 & a1, a2 & a3, ...
3. Then the CPU runs N/(2^2) threads on the GPU that merge lists of size 2. [a0, a1] & [a2, a3], [a4, a5] & [a6, a7], ...
4. Then the same with N/(2^3) threads on the GPU that merge lists of size 3.
5. And so on until N/(2^(lg N)) threads on the GPU that do the final merging.

Efficiency Analysis:
The CPU sends commands to the GPU lg N times. On the time it takes for the "i"th run of the GPU is at most the time it takes for 2*2^(i) comparisons since all of the merges happen at the same time. Hence, the time complexity of the entire program (disregarding the constant time it takes to copy array values from the CPU to the GPU and vice versa) can be calculated using the following equation:

Hence, the algorithm is of order O(N) AKA LINEAR.

Regular Expressions

Regular Expressions

Assignment 2 was about a simplified version of Regular Expressions. Being curious, I studied a bit more on regexes. Regexes are mainly used in pattern matching with strings, or string matching ie. checking to see if a string matches the format of a valid email address.

Here, I want to provide a list of the most common meta-characters that are used in regexes:

• ".":  Despite what you might think after having completed assignment 2, the dot does not represent the joining of two expressions. It means any character except a new line ( a literal dot would be [.]). If you want to show the joining of two expressions, you just put them one after the other without anything in between.
• "( )": Groups a series of pattern elements to a single element.
• "+": Matches the element or pattern preceding it one or more times.
• "?": Matches the element or pattern preceding it zero or one times.
• "*": Matches the preceding pattern or element zero or more times.
• "{M,N}": Matches the preceding pattern or element at least M times and at most N times.
• "[...]": A set of possible character matches.
• "|": Alternate possibilities.
• "\b": I'm not sure what this one means. This is what Wikipedia is telling me, "Matches a zero-width boundary between a word-class character (see next) and either a non-word class character or an edge."
• "\w": Matches an alphanumeric character.
• "\W": Matches a non-alphanumeric character.
• "\s": Matches a whitespace character.
• "\S": Matches anything but a whitespace.
• "\d": Matches a digit.
• "\D": Matches a non-digit.
• "^": Matches the beginning of a line or string.
• "$": Matches the end of a line or string.
• "\A": Matches the beginning of a string.
• "\z": Matches the end of a string.
• "[^...]": Matches every character except the ones inside the brackets.

So, no you can understand what the following regex means:

• \b[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,4}\b

Lets go through this step by step:

1. Start of regex
2. Any alphanumeric character or one of the following: ., _, %, +, -
3. 2 repeated 1 or more times
4. The "@" character
5. Any alphanumeric character or the "-" character
6. The "." character
7. An alphabet
8. Step 7 repeated from 2 to 4 times
9. End of regex

As you might have guessed, this regex checks if a string has the format of a valid email address. WOOHOO! WE ROCK! :D

A Few Nice References

A Few Nice References

I had a difficult time trying to figure out what to write about this week. I decided to share a couple of references that I've found quite useful (and that I'm hoping to have time using).

Street name: CLRS

• Written by 4 MIT computer science professors, this is one of the best references for studying algorithms. This (fairly large) book teaches you about the foundations of algorithms, sorting, data structures, advanced design and analysis techniques, advanced data structures, graph algorithms, and even some interesting special topics. This book is definitely worth the $90 you spend. (http://mitpress.mit.edu/books/introduction-algorithms)

• Another book that I really want to start reading is Artificial Intelligence: A Modern Approach. This book is one of the most widely used books on the topic of AI. If you guys are also interested in artificial intelligence, U of T has an amazingly large number of AI course for undergraduates. (http://aima.cs.berkeley.edu/)

• Time for a few cool websites. These websites all have amazing tutorials in so many different topics (and some of them not only in CS).
• Udacity.com:  This website has all CS tutorials. Web design, algorithms, AI, ... I've started taking the parallel programming course, and I have to say, the videos are very well made. There are also mini quizzes throughout the lectures that help grasp the topic.
•  edX: All the best universities put up free courses on this website. Anything from psychology at Harvard, to electrical at MIT. One course that I highly recommend is MIT's introduction to electrical engineering.

The Master Theorem

The Master Theorem

When doing various sorting algorithms in class, we talked a little about the order of an algorithm. Some of these analyses were straightforward, such as selection sort and insertion sort. But other sorting algorithms such as merge sort and quicksort are harder to analyze due to their recursive structure. When analyzing the runtime of recursive functions, we are often faces with a recursive identity that we need to solve. The master theorem provides a solution to many of these recurrences.

Lets say the following is our function:

def T(n):

     if n>1:

          f(n) operations done here

          T(n/b)

          T(n/b)

          ..... called a times .....

          T(n/b)

          T(n/b)

The recurrence formula for this method will be: (a & b constants, a >= 1, b > 1)

T(n) = aT(n/b) + f(n)

Now the master theorem says that:

1. If   where , then 
2. If  where  then 
3. If  where  then 

When faced with one of the above cases, the master theorem provides a mechanical way to solve the recurrence.

Example:

• T(n) = 9T(n/3) + n:
• a = 9
• b = 3
• f(n) = n
• Since f(n) = O(n^(log{9}{3} - 1), it is case 1
• Hence, T(n) = 0(n^(log{9}{3})) = 0(n^2)

Sources:

1) Introduction to Algorithms, 3rd edition, MIT Press

2) http://en.wikipedia.org/wiki/Master_theorem