Pocket Solver

Greetings.

For the past few days, I have been busy working on an iPhone Application. I will let you know the details later, but first let me narrate my journey in the mysterious and interesting world of iPhone application development.
    Being a generally Windows/Linux guy, I had no way to get my hands on a Mac. I wasn't willing to spend in the excess of $600 for a Mac(Mini). But thanks to the hacker community, I had a cheaper option. I used VMware Workstation and bought a copy of Mac OS 10.6. Then I proceeded to create a .iso file of the 10.6. Using a preconfigured Virtual Machine along with with custom built audio and video drivers and my Mac OS 10.6, I was able to run 10.6 on a virtual machine on Windows! I will create a blog post explaining how to do this, but tutorials can be found online.
    Once I got my "Mac" up and running, it was only a short while before I downloaded Xcode and the iOS SDK and started working on my app. It is a simple app that solves math equation AND outputs the full written solution. It is thus called Pocket Solver. It is a free application that my company Affordable Software Solutions released.  You can download it later find out about its features. Until then, here are some pics.

Anyway, this post is not to discuss the various features of my app or to promote it. Okay, maybe a little. But in this post, I will share some of the algorithms I  came up with to solve linear equations in two and three variables that will make your life much easier (if your life consists of solving linear equations...)

1) Linear Equation in two variables

Suppose you have a system of two equations that are in the form:

ax  + by = c    
dx + ey = f

then your x value will be equal to:

((c*d)-(f*a))/((b*d)-(e*a))

and your y value will be equal to:

(c*d-(x*b*d))/(a*d)

where x = ((c*d)-(f*a))/((b*d)-(e*a)).

looks complex, doesn't it?  All these algorithms actually do is eliminate the y variable and solve for x, and solve for y by substituting the newly found value of x in the equation.

If that didn't explode your head, here is another one...

2) Linear Equation in three variables

Suppose you have a system of three equations that are in the form:

ax  + by + cz = d    
ex  + fy + gz = h    
ix  + jy + kz = l 

Let us create six variables that contain a certain series of functions that we will use the most.
Let

    ae1 = (b*e)-(f*a)
    be1 = (c*e)-(g*a)
    ce1 = (d*e)-(h*a)   
    ae2 = (b*i)-(j*a)
    be2 = (c*i)-(k*a)
    ce2 = (d*i)-(l*a)

Now we will use these substitutions to find out the values of x, y and z.

So now, your z value will be equal to:

((ce1*ae2)-(ce2*ae1))/((be1*ae2)-(be2*ae1))

and your y value will be equal to:

((ce1-(z*be1))/ae1)

where z is equal to the equation above.

And your x value will be equal to:

(d-(z*c)-(b*((ce1-(z*be1))/ae1)))/a

where z can be found using the first equation.

Once again, I systematically eliminate x, create two equations with only y and z variables, eliminate y, find the value of z, substitute for z in one of the two newly created equations and find y, and substitute for y and z in the given equation and find x.

Wow, that was a lot! I am sure that you can further simply the algorithms, but  I haven't tried to do so. I encourage you to tinker with the algorithms, simplify them and make them more elegant. You have permission to use this algorithms in your projects, but with proper credit given to Aravind Rao.

This is not the end....

Open CVhat I can do!

Greetings:

I have decided to take a short break from Lego building(let us just say that I stepped on one too many Lego bricks) and decided to learn something new. I always wanted to incorporate vision in my programs, so I decided to learn a little bit of OpenCV. I actually want to use OpenCV with Lego Mindstorms, but since I am using OpenCV for c++, I would have to use JNI to get my LeJOS Mindstorms to successfully communicate with my C++ OpenCV program. (EDIT: I just found out that a Java Wrapper for OpenCV exists, so I may be able to give my Mindstorms "vision" after all!) Anyway, What I really was interested in was to use OpenCV to track eyeball movement. I will tell you why in the next post. Now how OpenCV tracks face and eye movements is relatively complex. I do not understand all of it, just enough to make my small eye tracking program work. Pretty much the face detection algorithm scans an image for Haar like Features, and if the image satisfies the condition of having a face, the algorithm further subdivides the face into many categories. For example in a typical face, the eye is darker than the cheek, and so when the algorithm compares the intensities of the pixels that make up the eye and cheek, it finds the difference in intensities and is able to distinguish between the eye and a cheek in a face.
          This is a very watered down explanation of what is *really* happening behind the scenes, and in reality, the face and eye detection algorithms in openCV are clunky at best without proper optimization. So I decided to create  small c++ program that takes in input from a webcam ans tracks the face and eyes in real time. It also superimposes images over the face. Face detection was pretty much straightforward. But the eye detection algorithm required further optimization. How it worked was that it all eyes that it discovered in an image(or video frame) it would store in a array. But the problem was that it detected 6-7 eyes at once! Now I only have 2 eyes(4 with glasses, but that not the point), so I had to make the algorithm pick only two eye objects from all that it had discovered. The optimization that I used was to pick the two eye objects with the largest area, and see how their x and y coordinates match up relative to themselves and the face(This is better explained in the annotated code posted below). After hours of tinkering, I have a created a program that tracks human eyes with movement in all 3 dimensions with ~85% accuracy in real time. It is good enough to start out with, but I figure I will have to do much more of optimization if I want to carry out a certain project(more on this later).
              I have posted the links to the annotated code below which explains how my optimizations work. They are no work of art, but they work satisfactorily. Also here is short video of the eye tracking in progress in real time.

Link to download the folder with code, .exe, classifiers and the other good stuff.

This is not the end......

Prim's Algorithm

Greetings

Sometime back, I wanted to dive into a programming topic called graph theory. Graph theory is an extremely interesting topic in the sense one needs to use their brains to solve graph problems. Also many problems, such as the traveling salesman problem have only been partially solved at yet, making it a NP hard problem. I decided to start my dive with a lesson in Prim's Algorithm. However after countless hours of scourging the web, I could not find the code, nor an explanation simple enough for me to understand the algorithm. Thanks an awesome video I found on YouTube(I don't have the link, but I find it, I will post it here) on the Prim's Algorithm I was able to write my own interpretation of the Algorithm. This code makes use of arrays and simple vectors and is extremely easy to understand. I though of posting this code because I wanted anybody else in my position to be able to understand Prim's algorithm without having to resort to complex, unnecessary code. So what is the Prim' algorithm? Ever heard of problems such as the length of road required to connect all cities? or the cabling needed to form a network of computers, but some computers acting as proxies for the others? Well for all these problems, the MST or the minimum spanning tree has to be found. Imagine a group of cities (A to E) to be the nodes in a graph. Now imagine the distance between them to be the edges in a graph. Here is a pic.

An Example Graph

So the DIRECT distance from A to B is 10, A to E is 34, etc. However what is the least length of road to be constructed so that all the cities are connected? It is certainly not 106, the sum of all the distances. It happens to be 22 or the MST of the graph of cities. Try it out. cross out the distances of 33, 34 and 17 and you should still be able to travel from any city to any other city! Solving such problems require MST which can be found using the Prim's algorithm.The code I release for Prim's algorithm will have a detailed explanation on how it works. Here is a gist: start from any node, mark it visited. Choose the shortest path from all paths available and the add the path length to your MST counter. Get the node at the other end of the chosen path and mark that visited as well. Now considering the paths from all visited nodes, choose the shortest path and mark the node on the other end as visited. Continue to do this until all nodes are visited and once done you have the MST! The Prim's algorithm is great for finding the MST, although a little bit slower than other algorithms. However it is a simple algorithm to learn and is fun to work with. Links for the code and explanation down below. Once again you are free to modify and distribute the code with proper credit given.

Link to .exe file.
Link to code.

This is not the end...

Aravind Rao

Intelligent Code

Greetings

Every problem in Computer Science can be solved by accounting for every possible permutation that the program might encounter. Naturally this is not an efficient practice, especially when  the number of possibilities can grow exponentially, reaching billions in no time. To effectively solve such problems, we need to implement  a kind of logic, based on our own thinking while problem solving. This inherent 'common sense' of humans can help create powerful algorithms to solve computer problems, without the aid of brute force. An example of such a problem is a computer game (Source .cpp, and .exe), where a computer tries to guess a users' choice within a given range. If the users' choice is >= the computers' guess, the user inputs 0. If the user's choice is < than the computer;s guess, the user inputs 1. Naturally, the computer can iterate through all numbers in the range from lowest to highest and check whether the computers' guess matches the users' choice and arrive upon the answer when the user inputs one(the users' choice will be the current computers' guess - 1). However what if the range extended from 1 to 2^10? Does it make sense to loop through all those numbers, check for user input and output the answer? This method is not time or user friendly. However, if we implement an algorithm that imitates the way we think when solving such a problem, we can arrive upon an extremely efficient solution for this problem. Consider the range 0 to 16. The user's choice is 11. Now lets add 1 to 0 and 1 to 16, to make the range 1-17. This is done because we will than have 2 nice halves of the range: 1-8 and 9-17. This idea of dividing the range into half will be central to out algorithm. You will get why I do this later. Now the computer has 1\16 or 6.25 % chance of guessing the right user's choice. If it iterated through all the values of the range and checked it against the user input, the probability of the program guessing the right choice will be increased to 6.67% -> 7.14 %...etc.(Not really, but for the time being, let us consider the case to be true). What should the program do to arrive upon the answer faster and in fewer tries? It should try to increase the probability of getting the right answer in each successful turn by a greater rate. For example in the range 1-17, the computer programs' first guess has to be (1+17)/2 = 9 or the average of the range extremes. Why? Because if the user inputs 1, the users' guess is less than 9, so it is in the range 1-8. Alternatively, if the user inputs 0, the users' guess will be greater than or equal to 9, and thus in the range 9-16. What have we achieved here? We have increased them probability of the computer guessing the right answer in the next turn to a whooping (1/8)% = 12.5%, which is the double the probability of guessing the right answer of the programs' first turn. Compare this with the 6.67% probability while iterating through all values!Now since the user's choice is 11, he will input 0, and now the computer program will carry out the same operation, although this time on a different range, that is 9-16. After this turn, the probability of guessing the answer right will increase to 25%, then to 50% and finally to 100% When it reaches 1000%, the program will have the answer! his method only works on ranges whose higher extreme can be expressed as:
Log2(Higher Extreme) = some Natural Number.
Therefore 16 works(log2(16) = 4), so does 8. 32 and 4096. The number of guesses the program will make is log2(higher Extreme). In the case of the higher Extreme being 16, the program will make 4 guesses, in the case of 32, it will make 5 guesses and so on.
I have provided the links to the source code and .exe file of this 'game'. Feel free to edit it, distribute it and use it, although with proper credit!

Link to .cpp source file.
Link to .exe playable game file.


This is not the end

Aravind Rao