Triangle

http://oj.leetcode.com/problems/triangle/

The problem statement is deceptive by mentioning path from “top” to “bottom”. I was fooled at first and tried to compare all the ways from the top to the bottoms. However, it is impractical since there are O(2^(n-1)) such paths.
I think this is a typical demonstration of the difference between bottom-up and top-down dynamic programming. It would be remarkably easier if we start from bottom and do upward. The solution is very short when the idea is set.

class Solution{
public:
    int minimumTotal(vector<vector<int>>& triangle ){		
		int N = triangle.size();
		if(!N)
			return 0;
		vector<int> r = triangle[N-1];
		for(int i= N-2; i>=0; i--){
			for(int j=0; j<=i; j++){
				r[j] = triangle[i][j]+min(r[j],r[j+1]);
			}
		}		
		return r[0];
	}
};

Sum Root to Leaf Numbers

http://oj.leetcode.com/problems/sum-root-to-leaf-numbers/
Another problem from Leetcode that I came up with two different solutions.
The first solution idea is to get paths from root to leaves first, compute the sum later. Those paths can be easily discovered by depth first search, while each path can be transformed to integer easily.
The second solution is much more elegant. There is no need to keep track of any paths, we calculate the sum as we go deeper from root to leaves. It runs a lot faster than the previous solution (12ms vs 36ms).

Second solution

class Solution {
public:
    int sumNumbers(TreeNode *root) {
       return sumNumbers(root,0);
    }
    int sumNumbers(TreeNode* root, int curr){
        if(!root)
            return 0;
        curr=curr*10+root->val;
        if(!root->left && !root->right)
            return curr;
        return sumNumbers(root->left,curr)+sumNumbers(root->right,curr);
    }
};

First solution

class Solution {
public:
    vector<int> pow10;
    int sumNumbers(TreeNode *root) {
        if(!root)
            return 0;
        pow10.resize(10);
        pow10[0]=1;
        for(int i=1; i<pow10.size();i++){
            pow10[i]=10*pow10[i-1];
        }
        list<int> path{root->val};
        return sumNumbers(root,path);
    }
    
    int sumNumbers(TreeNode *root, list<int> &path){
        if(!root->left && !root->right){
            return calculateSum(path);
        }
        int sum = 0;
        if(root->left){
            path.push_back(root->left->val);
            sum+=sumNumbers(root->left, path);
            path.pop_back();
        }
        if(root->right){
            path.push_back(root->right->val);
            sum+=sumNumbers(root->right, path);
            path.pop_back();
        }
        return sum;
    }
    
    int calculateSum(list<int>& path){
        int sum = 0;
        int n = path.size();
        int i =0;
        for(int p:path){
            sum+=p*pow10[n-1-i];
            i++;
        }
        return sum;
    }
};

Flatten Binary Tree

LeetCodeLink
I have solved this problem weeks ago, but today I completely forgot how I had solved it. As I tried to simulate the interview, I started to think and finally came up with a solution, which is interestingly different from the previous one. That’s what I want to write about this problem, not because it’s difficult or intriguing itself, but because it encouraged me to think twice from different perspective.

My first solution idea is that the problem can be solved by tweaking DFS: inorder traversal. We just need to keep track of the current pointer and the next one.

    void dfs(TreeNode* root, TreeNode* next){
        if(!root){
            return;
        }
        if(!root->left && !root->right){
            root->right = next;
            return;
        }
        else if(root->left){
            if(root->right){
                dfs(root->left, root->right);
                dfs(root->right, next);
            }
            else{
                dfs(root->left, next);
            }
            root->right = root->left;
            root->left=NULL;
        }
        else{
            dfs(root->right,next);
        }
    }

The other solution I came up today involve return the result as a pair of pointer.

    Pair flatten(TreeNode* root){
        if(!root){
            return Pair(NULL,NULL);
        }
        if(!root->left && !root->right){
            return Pair(root,root);
        }
        else if(root->left){
            Pair left=flatten(root->left);
            Pair right=flatten(root->right);
            root->left=NULL;
            root->right=left.first;
            left.second->right=right.first;
            if(right.second)
                return Pair(root,right.second);
            else
                return Pair(root,left.second);
        }
        else{
            Pair right = flatten(root->right);
            return Pair(root,right.second);
        }
    }

The two solutions are essential the same, but the point of practicing this problem is thinking path, not memorizing. There are tons of interesting problems come from binary tree, the more I solve, the more intuitive my thinking is.

Bellman-Ford’s Algorithm

Dijkstra’s algorithm is fast, but limited to non-negatively weighted graph. It also does not applicable for distributed system. Bellman-Ford’s algorithm is the solution for the two problems. It is asymptotically slower than Dijkstra’s algorithm as its complexity is O(EV). However, it can solve shortest path in negatively weighted graph, and it is highly distributed. In fact, it is the basic foundation for modern internet routing.

The code is extremely simple

vector<int> bellmanford(Graph &g, int start=0){
	vector<double> distance(g.V(),INF);
	vector<int> parent(g.V(),-1);
	distance[start]=0;
	parent[start]=0;
	for(int cnt=1; cnt<g.V(); cnt++){	
		for(int from=0; from<g.V(); from++){
			for(auto e:g.adj[from]){
				double dis=e.weight()+distance[from];				
				if(dis<distance[e.to()]){
					distance[e.to()]=dis;
					parent[e.to()]=from;					
				}
			}
		}
	}
	return parent;	
}

Dijkstra’s Algorithm

2014/3/5: How stupid I was for not recognizing Dijkstra as a special case of A* without heuristic cost. It makes the algorithm much easier to understand and implement. We only need to consider vertices as states and put them to a priority_queue.

Furthermore, I did not know that we need to implement Dijkstra’s differently in case of dense graph. The below code runs in O(E log(V))~O(V^2 log(V)) in dense graph. However, there is another implementation with O(V^2) complexity.
Let s be the source and (S,V-S) is a cut of graph G. The pseudo code

for v in V: distance[v]=INFINITY
S={s}
distance[s]=0;
while(S!=V){
   u:= argmin distance[u] for u in (V-S)
   for v adjacent to u:
       if(u in (V-S) && distance[u]+weight(u,v)<distance[v])
           distance[v]=distance[u]+weight(u,v)
   S=S+{u}
}

If we can determine if a vertex u in (V-S) in O(1) time, then the above code will run in O(V^2) time as there are V iterations in each one of V loops. This can be done by an bool array. This method is easier to understand than the below code.

2014/03/03: I have heard and read about single source shortest path problem in graph theory dozens of time, but it’s the first time I have ever actually write a program to solve it. The algorithm follows greedy paradigm to update the shortest distance from source to each of every other vertices.
The dijkstra function is quite simple as follows

#define INF numeric_limits<int>::max()
vector<int> shortestPath(Graph &g, int start=1){
	vector<int> parent(g.V(),-1);
	vector<double> distance(g.V(),INF);
	vector<bool> done(g.V(), false);
	parent[start]=start;
	distance[start]=0;	
	
	MinPQ pq;
	pq.init(g.V());
	
	pq.push(Pair(0.0,start));
	while(!pq.empty()){		
		Pair curr = pq.pop();
		if(done[curr.second])
			continue;
		done[curr.second]=true;
		for(auto e:g.adj[curr.second]){
			if(done[e.to()])
				continue;			
			double dis = e.weight+distance[e.from()];
			if(dis<distance[e.to()]){
				int index=pq.find(e.to());
				if(index==-1)
					pq.push(Pair(dis,e.to()));
				else
					pq.decrease(Pair(dis,e.to()), index);
				parent[e.to()]=e.from();
				distance[e.to()]=dis;
			}
		}
	}		
	return parent;
}

The most important and difficult part is to build MinPQ. Default priority_queue in C++ does not support find and decrease methods, which are vital to dijkstra’s algorithm. At first I implement find in O(V) time, it works but not so efficient. I then use an additional array mapindex to hold the index of vertices in MinPQ, which makes both find and decrease O(1) operations.

class MinPQ{
private:
	Pair *data;
	int* mapindex;
	int MAX;
	int size;
public:
	MinPQ():size(0),MAX(0),data(NULL),mapindex(NULL){		
	}
	~MinPQ(){
		delete[] data;
		delete[] mapindex;
	}	
	void init(int max){
		if(data)
			delete[] data;
		if(mapindex)
			delete[] mapindex;
		MAX=max;
		size=0;
		data=new Pair[max];
		mapindex= new int[max];
		
		for(int i=0; i<max; i++)
			mapindex[i]=-1;		
	}			
	void heapify_up(int child){
		int parent=child/2;
		while(parent && data[child].first<data[parent].first){
			swap(data[child],data[parent]);			
			updateindex(child);
			updateindex(parent);
			child=parent;
			parent/=2;
		}
	}	
	void heapify_down(int parent){
		int child=2*parent;
		while(child<=size){
			if(child<size-1 && data[child+1].first<data[child].first) child++;
			if(data[child].first<data[parent].first){
				swap(data[child], data[parent]);
				updateindex(child);
				updateindex(parent);
				parent=child;
				child*=2;
			}
			else
				break;
		}			
	}
	void updateindex(int index){
		mapindex[data[index].second]=index;
	}		
	bool push(const Pair& x){
		if(size>=MAX) return false;
		data[++size]=x;
		updateindex(size);
		heapify_up(size);
		return true;
	}	
	Pair min() const{
		assert(!empty());		
		return data[1];
	}		
	Pair pop(){
		assert(!empty());
		Pair value = data[1];
		data[1]=data[size--];
		updateindex(1);		
		heapify_down(1);

		mapindex[value.second]=-1;
		return value;
	}
	bool empty() const{
		return size==0;
	}
	int find(int id){
		return mapindex[id];
	}	
	bool decrease(const Pair& t, int index){
		data[index]=t;
		heapify_up(index);
	}
};

Time complexity is O(E logV) and space complexity is O(V).
Tested on data from this website. http://algs4.cs.princeton.edu/44sp/
References
Algorithms, Robert Sedgewick

Max points on a line

I have been preparing for the coming technical interview for two weeks and Leetcode is my main source for practicing. I already solved over 80% problems, but I find it difficult to review my solution by merely looking at the source code. Therefore, I want to write down my thinking process for several interesting problems on my blog, which can be useful in the future.

The first problem I would like to share is as follows

Problem: Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Having knowledge on Computer Vision, I instantly recognized the resemblance of this problem with Hough Transformation which detects shapes such as lines, circles in pictures by voting method. The basic idea of my solution is:
1. First count occurrences of each point and remove duplicate points.
2. Go over all possible pairs of point n(n-1)/2, put respective lines into an unordered_map<line,unordered_set>
3. Go over all lines in the hashtable and count the total number of points lying on each line based on the counting done in (1)
Hashing is the center idea to make the algorithm run fast. My code is a bit lengthy but easy to understand. No problem if encountering this one in an interview.
To be continue.

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
#define INF numeric_limits<double>::max()
#define SMALL 0.0000001

hash<double> hash_double;
hash<int> hash_int;

// y = ax+b 
struct Line{
    double a,b;
    Line(double a_, double b_):a(a_),b(b_){}
    bool operator==(const Line &other)const{
        return fabs(a-other.a)<SMALL && fabs(b-other.b)<SMALL;
    }
};

struct hashLine{
    size_t operator()(const Line &l) const{
        return hash_double(l.a)^hash_double(l.b);
    }
};

bool pointLess(const Point& p1, const Point& p2){
    return p1.x==p2.x ? p1.y<p2.y : p1.x<p2.x;
}

bool pointEqual(const Point& p1, const Point& p2){
    return p1.x==p2.x && p1.y==p2.y;
}
class Solution {
public:
    int maxPoints(vector<Point> &points) {
        unordered_map<Line,unordered_set<int>,hashLine> count;
        int n = points.size();
        if(n<=2) return n;
        
        sort(points.begin(), points.end(), pointLess);
        vector<int> countEach(n);
        fill(countEach.begin(),countEach.end(),0);
        
        vector<Point> ps;
        ps.push_back(points[0]);
        for(int i=0; i<n; i++){
	        if(pointEqual(points[i],ps.back())){
	            countEach[ps.size()-1]++;
	        }
	        else{
	            ps.push_back(points[i]);
	            countEach[ps.size()-1]=1;
	        }
        }
        
        n=ps.size();
        if(n==1) return countEach[0];
        
        for(int i=0; i<n; i++){
            for(int j=i+1;j<n; j++){
                double dx = ps[i].x-ps[j].x, dy =ps[i].y-ps[j].y;
                double a,b;
                if(dx){
                    a = dy/dx;
                    b = ps[i].y-a*ps[i].x;
                }
                else{
                    a = INF;
                    b = ps[i].x;
                }
                Line l(a,b);
                count[l].insert(i);
                count[l].insert(j);
            }
        }
        
        int maxP = 0;
        for(auto i:count){
            int size = 0;
            for(auto j:i.second){		
                size+=countEach[j];
            }
            maxP=max(maxP,size);
        }
        return maxP;
    }
};

How did I get MEXT!

I have recently received many questions regarding to my experience of studying abroad from students from my old high school Instead of enumerating those questions and answering them, I want to share my experience of getting Japanese Government Scholarship (MEXT). I hope that after reading this entry, you can figure out a realistic plan to realize your own dreams.

I got the information about MEXT through my sister who was studying at Hanoi University of Science and Technology. A friend of her, whose grade was among the highest at HUST, got MEXT and came to Japan to study. I was impressed by her story and instantly attracted by MEXT. I heard the story when I was high school’s senior, and I started planning to get MEXT since then. The plan was quite simple, I just forced myself to study English, Maths, Physics and Chemistry harder. Nonetheless, the plan did not go well. I loved mathematics too much to stay focus on other subjects. I gradually stopped studying physics, chemistry and English. I thought I would be able to review them before the tests in Japanese Embassy. It turned out that I had thought too much, because in fact, there was nothing I could do in high school to prepare for MEXT.

After entering HUST, I knew I had to overcome the most challenging part of my plan, which was to get in the top ten students with high grades in the first semester. Because I studied in the centre of gifted education, my classmates in university was far superior than my classmates in high schools. Most of them came from some gifted high schools, more than half got prizes in National Olympiad in maths, physics or informatics. Some of them even attended International Olympiad in physics or maths. To be honest, at the beginning of my freshman year, I thought it was almost impossible to be in the top ten of my class, let alone my university. However, my plan looked much more plausible after the first half of the semester. Finally, I got the highest GPA in my class, and was in the top 5 in university. I was proud and quite sure that I will be elected as a MEXT’s candidate.

I started studying English and reviewing chemistry and physics from the beginning of the second semester. It was very boring to learn those subjects which I had no interest in. However, I did it anyway, because in order to accomplish my plan, I had to learn whatever necessary. After a semester, I thought I was quite ready for the tests. I did not do them as good as I expected. I made many rueful mistakes. Fortunately, I passed the exams and got an interview. The interview lasted only 10 minutes and was fun. After 6 months, the result came out, and I was happy as hell.

That was my experience written a very unorganized way. After taking TOEFL, I feel that my writing skill has gotten worse day by day. 🙂

First TOEFL test coming

Unlike most friends, I don’t like vacation so much. It kills my ambition and subdue my brain activities. After a long trip home, I am going to face arguably the hardest test I have ever taken in my life, TOEFL Ibt. I am notorious for preparing tests too seriously. Those tests normally turned out to be not as hard as I had thought. I seem to be more anxious this time about the test. This is the first time for me to take the TOEFL, so I do not expect that will be any huge success. I just hope I will pass the exam will an acceptable score. I did not take this test for any practical purpose such as applying for scholarship, universities or hunting jobs. I desperately want to know, though roughly, which English level I am in now, instead of staying at home and guess. Eventhough I am very confident about my ability, I am afraid of being complacent, which may be literally harmful to me. I hope this test will help me know my English level, so that I will be able to make more specific plan for English study.

Wish me luck!

On board

2013/2/9 JAL 751

I did not think much when writing this entry!

I am on the plane bounding for Vietnam and it is expected to land in nearly three hours. I am reading Pattern Recognition & Machine Learning by C.Bishop to kill the ever-lasting time. I am always proud at Maths, but reading that book really gives me headache. There are so many mathematical formulas which I can hardly understand. However, I am still able to grasp core concepts and ideas. By the way, when waiting for boarding, I talked with a guy who asked me about my study. When I mentioned “machine learning” phrase, and translated it into “may hoc”, his response showed that he had never heard about that phrase before. Unlike Artificial Intelligence which has gained popularity around the world, Machine Learning is still an ambiguous concept. I hope people will know more about it in the future, just knowing what it is is enough.

The flight is unsurprisingly crowded today. I met two Kohais at the waiting area. It was quite fun chatting with them. One of them has a similar major with me by the name, mine is mechano-informatics, his seems to mechanical control. Nothing more to say.

I want to write about my plans for TET. This is the first time in four years I have been able to celebrate TET in my home country with my family and friends. Therefore, I have been making plans for next week right after I booked flight seat. The first day, I will go back to my father’s mother place as a Vietnamese tradition. All my life, that has been the most boring part of TET holiday for me. Even though I have so many relatives there, I don’t particularly get along with anyone because I used to go there only three or fours time a year. More importantly, I share no common things with my relatives there. Fortunately, I gradually feel less miserable about the trip as I grow up. I now see it a kind of duty, which I know I should do.

The second day, I will go to see a friend of mine for a while. I have waited such a long time for that moment. My schedule will follow with dinner in Nhan’s place, with Thu, Duong, Trang B, Dung 9, Giang Beo. I am not sure Giang coi can make it because of her restriction to go outside. I also want to visit two of my favorite teachers in junior high school. One is my maths teacher who likes me a lot. My maths knowledge was not come much from her, but I think she played an important role in my burgeoning devotion for maths. I vividly remember I was the only one getting the perfect points in the first exam in 8th grade. It was very important one, because at that time, I do not think my classmates had any idea about my ability. In fact, I guess I was referred as a incompetent student who needed to be transferred from the best school to the second best one, where my father worked. After two months in the new class, I think my friends already had a pretty good idea about me. I recalled this memory to emphasize the fact that I am grateful because she discovered and appreciated my maths’ ability, which all previous teachers failed to notice. The other teacher, whom I did not have much interaction, but I like her a lot because of her strictness and fairness. I got myself into trouble at times in a class full of bad students. The class was separated to two halves, one consisted of decent students who did study, the other gathered bad students with no intention of study and worse, no intention of treating classmates like friends. The problem arose when a group of bad students attack my best friend who was twice as big as me but he could not fight against a bunch of arrogant and stupid people. I interfered but soon was left out of the way. They did not dare to attack me because of my father’s presence. After that incident, I could not tolerate anymore. I started to verbally make fun of them, which I truly enjoyed. They had a group, but I had my father, so I thought I could have fun like that as much as I wanted. However, inevitably I had a fight with one of them. I cannot remember the exact cause of that fight, but I think it was a good fight. Neither of us won, I think we were equally hurt. However, the fun is yet to come :)). The following day, Mrs Hien, the teacher in question, knew about our fight. At the beginning of her lesson, she asked few questions about it. She first came to my seat and asked me something, I answered quickly. The class expected her to give a cliche’s lecture for both of us about friendship or good behavior in school. However, after quick Q&A with me, she moved to the other one in the fight place. What she said to him was unimportant, because suddenly, she raised her hand and slapped him. You would never know my feeling at that time. :)) She was protective of me, and I guess she knew about the existence of a group of bad students in our class, and her distinguished respond to a member who fought against me made them think twice before attacking other classmates in the future (not happened again that year, i think). I became like her a lot more after then. We went to visit her twice after graduation, and both were full of funny stories, some of which had not been told before. I really looking forward to seeing my favorite teachers.

The third day, I am going to Lang Giang to have a party with my high school’s group. High school’s friends are always the best ones. We have party whenever I come back. I have no doubt that we will have a lot of fun.

I am a little bit tired and will stop writing now. Many friends ask me how to learn English effectively. My answer is that try to interact with the world by English as much as possible. Things like writing blog, Facebook’s status, diary or listening to music, radios or watching movies help a lot. Making mistake is a part of study. I normally review my writings a few times before or after publish them in order to find mistakes which can make people laugh but help me to improve my skills. Hopefully all of us will escalate our English skills!
…. To be continued.

2012- A Remarkable Year

I have been living in Japan for nearly 4 years, but this year is truly special to me. The most important point is that I finally knew exactly what to study. During high school, mathematics was my world, was the one I loved. However, I had been lost after high school’s graduation about my major. There were too many choices while I had too little knowledge to decide.
Fortunately, everything has happened to me in 2012 helps me make up my mind. Now I know Machine Learning, Artificial Intelligence and related fields are the ones for me for the rest of my life.

After high school, I directly got into Hanoi University of Technology (HUT). Since I wanted to learn about robotics, I chose Automatic Control with the hope of learning about controlling real robots. However, I soon found out that my department in general, and my major in particular had very little thing to do with robot. I was baffled at first, but then that problem became unimportant as I would have a chance to choose my major again when coming to Japan. I am happy that I made a right decision this time, even though the outcome is not what I expected.

I spent the first year in Japan at Japanese Language Center for International Students with other MEXT’s fellowships. Not until December 2009, were my major and university decided. Therefore, I took a lot of advices from my Sempai by listening to their experiences and preferences. I still had an affection for robotics, so I opted for Mechano-Informatics which would satisfy my quest for robotics’ study. Up until now, I can say that that was the right decision, but I could never predict what I have become now. My study now is hardly related to robot’s control theory, instead, I focus on Artificial Intelligence and Machine Learning, which involve lots of probabilistic mathematics and algorithms’ design.

The funniest thing was that I chose Mechano-Informatics not purely because I was interested in robotics but also because I was told that my study would require a tiny amount of programming. I seriously hated programming and anything related to IT at that time. This sounds strange, because many people assume that people being good at maths would automatically are good at programming. That should have been true for me, but because I did not pay enough attention to my first programming class (first semester at HUT), I became afraid of it. That hatred feeling lasted until last summer vacation when I spend two months in Vietnam. I would have never spent time studying during homecoming trip, but that was a special occasion. As I mentioned above, I had an programming class in Vietnam before, which adversely made me hate programming. However, after knowing that there would be numerous programming classes in my department’s curriculum, I got worried. My original intention was very plain, I planned to study fundamental algorithms and programming concepts during two months in Vietnam in order to “survive” those classes. I was that scared!!! Before coming back to Japan, I finished the most well-known Vietnamese programming book (the only Vietnamese one I have read) for beginners written by Quack Tuan Ngoc. It was helpful, and I thought I was quite ready for class in the following semester. My caution turned out to be excessive, since the Software I class was very good class for beginners. It was quite easy, even if the previous vacation had not existed. My interest toward programming had been growing over time, especially after I started play with micro controllers.

I was suddenly attracted by low level programming for micro controllers in two months, last November and December. Even though it was fleeting, it did play an important role in luring me to the world of programming and algorithms. I soon gave up low-level programming as the result of taking Software II class by professor Hitoshi Iba. The Software I class of my department was good, but it was basically about practicing programming, which could not satisfy a maths “nerd” like me. Consequently, I sought another programming class from Electronics-Informatics department. The class started from the middle for the semester, when I already had a quite solid background in programming. Prof Hitoshi’s teaching method was great in my opinion. Software II was totally different from Software I, the later taught me programming technique while the former taught me algorithms. Programming only is boring, but with the companion of algorithms’ design, it becomes great. I mastered all fundamental abstract data structures (ADTs) and C language after finishing the final report. Thankful to Software II class, I got rid of low-level programming and totally switched to high-level design. I am taking Artificial Intelligence class by professor Hitoshi Iba (will take another class of him next semester). This class sums up my programming and algorithms’ study. I spend about 10 hours per week on average on weekly reports, from essential graph search to genetic programming. It does make me tired, but it never bored me. The feeling of 10 continuous hours for maths has come back to me. I am at my best when I study with passion.

My story about my growing affection for programming ends here. From this April, the time I have spent for algorithms’ study is on par with the time I spent for mathematics during high school. Reading algorithms’ book has become my hobby now, which certainly will make me a better programmer. I believe by the time of graduation, my confidence in programming will be far stronger.

Programming and Algorithms alone obviously could not make 2012 such as special year to me. The other one is my current and future study focus, which are Artificial Intelligence and Machine Learning. My affection for those fields of study is naturally ignited by my first Neural Network’s implementation. When I first heard about Neural Network, I thought it was cool from the name to the implementation. I had no theoretical knowledge about Neural Network at that time, so I quickly read about it and grasp its core ideas. I followed several tutorials to make back propagation neural network as well as self organizing map. Implementation neural network was really, really fun.

The event that played the most important role in pushing me closer to ML and AI was the summer internship at Microsoft. It was so far the best summer of my life. Details about my internship can be found here:

http://www.bing.com/community/site_blogs/b/jp/archive/2012/12/06/2012-msd-2-l.aspx

The bottom line is that I have seen how important and fascinating Machine Learning is during my internship. Additionally, I am taking 4 classes that related to AI and ML this semester, which makes them even more appealing to me. I have planned to make Machine Learning the theme for my thesis next year, and I am really looking forward to it. When I was thirteen, Maths found me, and I am now very happy to meet another inspirational subject, Machine Learning.