Category Archives: Intelligent System

Coursera Optimization

Discreet Optimization at Coursera

Discreet Optimization at Coursera

I just finished the Optimization course in Coursera.org and I felt excited about it. I learnt many new computer science concepts that I skipped during my undergraduate time. My postgraduate was more about management, business and finance than a technical one.

This is a quick review of the course to show what I learnt, what I wished to learn more and how I could apply it in my real world problem

What I learnt:
– NP-hard problems
– The basic knapsack problem
– Branch and bound
– Bottom Up Dynamic Programming
– Constraint Programming
– Local Search
– Integer Programming

It is one of the toughest course in coursera so I needed to watch one topic twice, one for the general understanding and the second is when I need to finish my programming assignment. I will summarise what I learnt in the next few posts, and upload my java code so people can learn from it. The code is not good, though.

The difficulty of the assignments increase significantly when you progress through the course. However, you can jump to any assignment and finish it if you feel comfortable. The lecturer has a hilarious style of teaching that I enjoyed. I personally got 256/320, about 80% of the score, enough to get a certificate

P/S: I recently had a discussion with my coworker about the role of the school and what students should expect to learn. Some of the key concepts offer short term benefits while others’ usefulness need years to recognize.I will write about that in another blog post.

Google and Social Network

This was my paper that I submitted to Google for the Associated Product Management job a while ago and it becomes really out of date, after they release Google+. I just publish it here for record. Some of them are implemented by Google already. And I am still not sure if they would go over all of these.

Improve Google +1 and Social Network

Google is now losing the social networking battle to Facebook’s hands. That is undeniable. Although Google try his best to improve and create many social platforms and integrate many social ideas, Google still fails. Look! Google Wave, it disappears after couple of months, Google Buzz, nobody hears about it in the media world now. And what happens to the next Google approach, Google +1.

I keep asking myself what Google + 1 is actually trying to do, is it a better search or a better social network or anything else. At the current state, here is what I see about Google + 1.

  • It is actually not a bookmark or read it later service like the way Delicious works.
  • It is not about sharing when one user likes the page, none of his friends may know.
  • It is not creating any connections or interactions between users.
  • Does it bring more benefits to Google rather than to users with the machine learning algorithms?

I don’t think that in the general strategy, Google integrates +1 button for the machine learning algorithm. It already keeps track of what users click, what users see and what users behave when they do search. The +1 button may help a little bit over the algorithms but not much. So, I believe that Google does this for social networking efforts and to beat Facebook and Twitter.

In terms of social networking, my biggest question for Google + 1 is: how on earth, does a user want to click the +1 button? Look at the Like button of Facebook, I think that button is so successful because everybody wants to share, wants to let people know that they like this page. This acts as a virtual award for them. “Look, friends! I have this page for many of you”. Google +1 needs something like this. The content is created by users and needs to provide to users real or virtual benefits.

In brief, here are some ways or problems I think Google has to do to improve +1:

  • Attract and give users awards for their efforts
  • Attract 3rd party providers to integrate +1 button into their website
  • Boost up Google Buzz and willing to cooperate with other services.
  • Identify the market niche in social networking that Google can come in.

Social – Attract and give users awards
The last time I tested the Google +1, I cannot see any of my friends +1, and only a few from strangers. Here is the problem. In social, we have 2 concepts of friends sourcing and crowdsourcing. However, the friends’ sourcing is always more important than the crowdsourcing. The recent time is also important to let sharing between friends happen. If some of a user’s friends like an article 3 years ago, it does not affect much the current decision of that user.

Look at Facebook and Twitter where timeline is important. It is about if users can see what their friends are doing, liking and working on recently. If we want to improve our Google +1, we have to customize the Google Page Rank algorithms in such a way that can take the time dimension into account. It is also really important that I can see my friends’ rate for page more often when I do search. This is hard because searching is sometimes more random than keep surfing around the timeline of Facebook or Twitter.

Integrate +1 button into their website/chrome/android

Now, if we assume that users are willing to click that button to help their friends. However, will they do it before or after viewing the content of the page? The answer will be after. There is no point for them to rate it good before they actually see the contents of the web page. And we should not expect them to press the “Back” button in the web browser to come back just to rate +1 for the web page they like.

So, we have to take advantage of our current network of effects into users. There are 2 ways, browser and the web page. Browser is actually inside our control and web is not.

Chrome is taking more and more market share in the browser market. This is a huge advantage for us. We can integrate our +1 button somewhere in the browser so that everytime user search and go to a page, they can press that +1 button. Ping! We got data. And we got data not just from searching, we got data from every users enter any web page, any link, any article. We conquer the web.

But not all users are using our Chrome, we have to help them to have a more convenient way to rate our page. Just like facebook, we need to help them to put +1 in websites, a +1 button for every articles and pages inside that web page. We may not beat Facebook in this area but we can use it along with Chrome. Facebook and Twitter do not have this advantage. This button will be a great marketing tool for all websites to have.

Social Network Integrations – Buzz, Orkut and more

There is no doubt that Google Buzz is losing, it is nowhere near a success and nobody talks about it anymore. Orkut is successful in India and Brazil but is losing its market share now (only 38% market share, June, 2010). However, it would be bad idea if we do not try our best to integrate our new +1 into these services. Anybody who login to Google Account and press +1 for the web page or search result will appear on their Buzz and Orkut social network.

This will be where the friends come from. However, that would not be enough. This will be always an egg and chicken problem for Google. Will Google have a big user base first to spread out the +1 button to the whole world? Or will the spread of the +1 button help Google to have a bigger user base? I would suggest Google to use integrate with Facebook. In other words, allow users to post data from +1 to Facebook. That would be a big deal when Facebook can control and can know what Google’s users do. But, we can do it only for a short amount of time, when we need to grow Buzz up to the same level of Facebook.
After all, what are wrong with all Google efforts to go into social network?

  • Google Wave was a success for me at the beginning but then some mistakes like private invitation makes it fail.
  • Aadvark was also good but it can not go up too much.
  • Youtube is an excellent video sharing service, but not much social there.
  • Google Buzz is a nice try to integrate with Gmail, to utilize the current user base, but will fail because it is the wrong market segment. It also serves nothing else a news feed like Twitter.
  • Orkut turns out to be successful in India but then get lost in the battle with Facebook.
  • Android, why Android here? Because we have a strong userbase that can turn out to be a big value for us if we can create a social network there.

What is my thinking is that if Google can integrate and connect all of these platforms that it has in hand to create more connections, it can have some big social network. Imaging that every of its users have an Android phone, connect, chat and share together through Buzz, watch videos, recommend and share to every friends through YouTube. Ask and answer questions in Aadvark in the idle time or while waiting for the bus. If it can do that, this would be huge. Look at Microsoft and Facebook, they tie into each other. Microsoft and Nokia are the same. Facebook will be present in all Microsoft devices and in all Nokia devices. Even though Microsoft does not have a strong market share in smartphone now, it will keep growing up with these things.

Google has to create a bigger ecosystem and +1 should be improved to become a nice fit into the whole picture.

 

 

Robocode New Beta Release

Robocode Logo

Robocode Logo

 

Robocode has released a beta version for 1.7.3.0, I am happy to contribute 1 feature and 1 bug fix in this release. Please download, test it and tell us any bugs you found

 

 

 

Reference:

Robocode in SourceForge

My Career – A year look back and fro

vodkhang's career step

vodkhang's career step

It has been almost one year from my first day into my career (4/11) and since that day I have learnt a lot of things and sharing lots of things in my blog, stackoverflow, facebook and twitter. I will try to summarize and make a general view for my career in the last year. I will also give out my vision for my career for the next year

Web Development
My first work is Scala researching – a still hot technology and growing quickly until now.

Although currently, I do not work much in Web Development, but I will try, for sure, come back to this field again. Why? My vision about this field is still hot, highest and most challenging technology for scalable system is still here with the born of lots of things like Cloud Computing, Google App Engine, Scala, Ruby and Clojure. Maybe my next programming language for the web is Ruby. I already have the intention to jump into here. Hope that my colleagues in KMS can help me to catch up this technology fast.

The good thing about Web Development now is that we have Google App Engine and some App Store for the web is growing. With the born of Cloud OS which will happen soon, I hope that I will have the time and chance to come back, either individually or as a developer in the company.

Artificial Intelligence
This area is cool by its name and it is part of a reason I went to Melbourne last year. I had chance to work full time on it and even it was not a success, I learnt a lot from it. What I think is that I will try to focus on Computer Vision and Machine Learning (and may be Agent system) with the intention to apply them into iPhone someday. Why is iPhone? Because I still need to do something with commercial purpose and dealing with iPhone will at least give me some financial benefit in short term. And with iPhone and client technology, I don’t have to deal with massive amount of database problem which I have no chance to practice.

Related to Artificial Intelligence, I intended to take Phd from years ago. However, my decision now is something industry oriented rather than academic environment. I appreciate the academic environment, which is good to work and learn what you like but for now, I think I do not prefer it.

Mobile Development

I came to this area by luck, I didn’t really intend to jump into. iPhone programming is cool by its design, working in limited environment and dealing with memory management. There is another challenge for building iPhone app for me is how to make it the best for user, in other terms, usability.

I learnt lots of things about usability over last few months after reading some books: “Don’t make me think” and “User Interaction Design”. This viewpoint is a little bit from a designer’s perspective rather than a developer’s one. This is cool and make me understand more about users. To be honest, before I do iphone development, I am scared of designing (both in terms of graphics and interaction) and I don’t get love in it. But now, I think I can do at least interaction design well. The usability lession is a first and perfect one for overcoming scareness in my career.

Other stuff
Working in iPhone let me have time to learn something else that I am scared about. Git in terminal for example. I am scared of terminal and scripting and all those administration stuff before.

I am also trying to do a lot of testing in iPhone, from UI Automation Testing to Unit Testing which make me fall in love. I love the Google Testing Blog’s Term: “If it ain’t broke, you’re not trying hard enough”. Now, I feel so bad for anytime I cannot make a software crashed :). It is also good that I am still looking forward to improving my productivity day by day, automation process, hot keys and dual monitor was what I achieved. The next stuff will be emacs, for example.

My current love in technology can be said: “user, automate and scale”.

PS: To be honest, I hope that this is the first time I can focus 150% into working and researching. For the whole last year, I had to spend so much time in university assignments, exams and then GRE. Those things do not just take off my time but also kill my energy and passion so fast, while those things are either not challenging, boring or just I do not love it.

iPhone App Performance Optimization

iphone performance

iPhone Performance Benchmark

Working in a power limited environment like mobile, and especially, iPhone here, we soon have to face with performance problem in many different kinds. Different than the web model where web front end (javascript) do some (usually not much) processing – also browsers support you a lot, iPhone native application usually has to do quite a lot of processing.

Image Source

For iPhone native app, you cannot add any hardware to help you to have better performance. The only way you can try to deal is to deal with the software code itself. I will list some few problems and solutions that I figure out these days when I really focus on optimization. The list is applicable somehow to other mobile areas like Android or limited environment like embedded device

1/ Benchmark

It is a really traditional advice, but you always have to remember to benchmark your code, even by using simple tools like NSLog or Instrument tool. You should only care about places that is slow in terms of your test rather than trying guess and error possible places.

2/ Test on iPhone device

This is another traditional advice but people usually forget. You have to test on the real iPhone device. Let me give you an example: on my iPhone simulator, a method runs within 1 second, but in my iPhone device, it takes 8 seconds, a huge difference.

So, when you test your app on the iPhone device, don’t just test for UI, memory or features that the simulator doesn’t have. Remember testing the performance as well.

3/ Multithreading and the main thread

Some people may come to you and tell you that iPhone device just has 1 core and you never need to care about multithreading. It is just WRONG.  You still need to do a lot of multithreading to reach a better level of performance.

The main thread will do the user touch event handler and view rendering. Then, if you use the main thread for some calculation that takes a lot of time then your UI just become frozen or not smooth when you scroll.

For UI like UITableView where users scroll between many cells, the runtime will run a loop over visible cells and set the contents. Because this process runs in a row not concurrently, and it will not allow you to view or scroll the UITableView until it returns all cells, you can possibly let some of the cell content run on another thread. (more about performance on UITableViewCell part).

The other reasons for using thread are well-known, heavy IO and network processing, all of them block processing and you need thread so that your main thread is not block. This will help to make users feel your app run with higher performance

But, be CAREFUL, Multithreading comes with its own disadvantages. For rendering the view, you should do it on the main thread or somtimes, your app will just crash randomly. Another traditional reason is that the CPU has to switch too much between threads and it takes more time than usual to finish a task

4/ Use Memory wisely

Some questions on stackoverflow that I sometimes see shows a scare feeling about memory. It is right that iPhone has limited memory but it doesn’t necessarily mean that you should use it as least as you can. Memory and Performance is always a trade-off problem, you must use it smartly

The right mind you need to keep is using that limited memory smartly. We all know the priority of speed is Memory > File and Local IO > Network, the fastest access is always using memory cache for the data. There are some problems for memory caching in iPhone:

    – You have to respond to 1 method in every UIViewController:  (void)didReceiveMemoryWarning. In this method, you have to smartly release some memory cache of data to reduce your memory usage.- Know what/when to cache something in memory. There are lots of Caching algorithms outside from simplest ones like: Random Replacement, Least Recently Used, Most Recently Used. It is also an issue of caching big images or caching lots of small images. It all depends on your app. For my app, my main view contains lots of thumbnail images that need displaying fast and the user can wait for seeing big images. So, we cache a lot of images (60-100) for just 2 MB of memory. Knowing how to balance memory usage and good performance will help you a lot

5/ Algorithms and Data Structure

For my case, I didn’t really need to solve big performance issue with Algorithm and Data Structure, but in a limited environment, a small mistake may lead to a big deal and hard to detect. My case was that I need to merge 2 data arrays from the network using some unique characteristics of elements.

The app works really well in the Simulator for about 50-100 for each array (less than 0.5 second) . However, when I tested on the device, the time surprised  me, 8 seconds (16 times slower). It cost me 1 hour to detect that I use 2 for loops through 2 arrays which means O(n2), and then, I changed it to a dictionary which reduced the algorithm to O(n) and took me back to 1 second. Phew! Finally, performance is up now

What I learnt here is that even we don’t ever need to deal with Massive Data, we still need to be careful about some algorithm and data structure. 50 elements are nothing in a desktop or server scale but can cause a huge issue on limited environments in iPhone. Another lesson is a remind for me that I should always test on the real device to get the real performance

6/ Reuse UITableViewCell to improve Scrolling Performance

This part is quite unique for iPhone but may be good for other people to learn. In iPhone, we have a concept of UITableView for displaying a list and a table can contain a lot of cell.

The problem is that rendering the Cell (or generally the UIView), takes lots of time and can cause the app to look like stuck when it is scrolling. Usually, if you use the default UITableViewController template, the template already gives you the code for reusing the UITableViewCell.

The only problem is when you create a custom UITableViewCell using some usual tutorials like this and this (especially using Interface Builder), they forget to tell you that setting a CellIdentifer in the UITableView is not enough to reuse a cell. What you need to do is to set it in InterfaceBuilder or write a method to return it. I know that many people will forget it and think that they still reuse the cell, but they don’t. I suffer the same problem until I did benchmark and found the problem recently.

Here are 2 good techniques:

Copied from Stackoverflow, this question:

1st way: Just implement a method with the appropriate method signature:

- (NSString *) reuseIdentifier {
  return @"myIdentifier";
}

2nd way:

How to Reuse a Cell in Interface Builder

Cell Reuse in IB

References:

1/ Web Caching, wikipedia

2/ Web Caching, Stanley Luong’s course material

3/ Stackoverflow – reuseable Cell

4/ Stackoverflow – custom UITableViewCell

RoboCode Team Battle (Week 4)

Hi, everybody, the robocode competition goes up to another level, promising more fun and more jobs for you guys. We just released a new rule this morning requiring people to compete in team, 2-2 battle. The era of 1-1 battle ended. This morning is just a practice for a new game. You do not have time to improve your robot a lot, that’s ok now. You just need to have a better communication with your ally.

Now, we just take a look at battles between 2-2. There would only have 4 teams this morning but creating a lot of fun and entertain for people. Poor you guys, the people not joining this morning

The first match:

The Red and the Blue guy on the same team while the White and Black on the other team. The match was quite in the first team when the Black guy use the still strategy, which was good for some robot cases that can not shoot the still robot

The second match:

The 2 yellow guys compete with Gray and Blue guy. The 2 yellows shoot quite correctly but the strategy of the other team is against the Yellow team when they move in line but change direction really fast.

The third match:

We found the anti-Indian guy. Welcome to Yellow guys, you guys did a really well job when running in a spin strategy and the Indian strategy almost dies.

Wait for tomorrow, when we will have a real team battle. Never have the case that we will shoot each other any more. And AWARDS, will officially be given for the first 2 teams tomorrow.

RoboCode Report Week 2

And now, we are already on the week 2. Different than week 1 when I am too busy to write some brief report. I will write some brief report, feedback and evaluation about the second competition.

First, come to the battle between Police and Indian. We can see that Police does not have a big improvement over the last week, while Indian goes into the next level by getting the ideas of running around the opponents from his own opponents (ideas started by Police). We also wait for some peole to kill that suck Indian. Everybody really wants to kill the Indian

Then, we come to the next match between Tester and Rammer. Rammer tried to implements a combining strategy between Rammer, Indian and Spin Bot. But, to be honest, it was an example for what people say : “good idea, bad implementation”. Rammer tried to change the algorithm at the bad times and the RunAway strategy was not good enough. Waiting for the next version when Ramming and Indian shake their hands:D. We also welcome the new comer, a handsome guy, Phan Vo. Hope that we will see a better implementation in the next version

Yeah, now, we see how good Alosa (a loser) is and if it is a real alosa. With a quick implementation in the Web Dev class (Buu will get disappointed for that news), a new version of SweetPo has come into the world. And welcome Huy, another new comer this week. Inherits from the Indian, Huy produced a better implementation. That’s so good and fit exactly what we expect when publishing our source code. I can see a good future for Huy in later versions.

RoboCode Game competition

Hi, I am really happy and excited that we, RMIT students (RMITC), held a good competition. It was just a beginning for a series of RoboCode , game competition as said in previous post. No more talking, I will show you a demo from our students first.

That’s really cool and so simple, and we will have many more AI techniques and Software development there. We will try to add some more intelligence, game strategies in those robots to make it really fun (I already had some ideas in my head). We also have several activities around like tutorials (Instruction 1 and Instruction 2), code review (I did code review for my friends, Khang Nguyen and Phu Hoang) and open some of our source codes (Khang Nguyen, Phu Hoang, Tuan Anh, and Khang Vo). You do not need to be an expert programmer to start programming with RoboCode, the only need is your PASSION. Feel fun, just start. Play and learn. You will become an expert soon

Two more video examples

So, now, how can you join? If you are an RMIT student, it should be extremely easy, just come in. If you are not and you want to join, please contact me: vodkhang@gmail.com so that I can arrange for you to join. Or just wait, I and Youth House also try to operate some robocode competition events.

Online Programming and Software Development Competitions

In my university, it was hard to find chances to go for programming and software competitions (like ACM and Imagine Cup), part of the problem is my fault as well. So, I usually find and join online competitions. Anyway, it is not the main ideas of this post. I want to introduce programming competitions that other people can find fun.

For me, competitions are chances to be fun, to boost skills and to communicate with other people. Fun may be the most important thing, because if it is not fun, interesting and challenging, there is no reason to do it.

1. TopCoder : a lot of kinds of competitions here. This is my favourite one.

A short competition lasts about 1 hour to compete with other people in a 3-problem test with easy, normal and difficult level. You can also do code review, challenge others’ solutions by your own test cases. I love this idea because now, your solution is both validated as well as verified by other people.

It is fun and realistic for software developer. You can even earn money. The only problem is that time to compete is really short, about 2 or 3 days and require in-depth knowledge about J2EE and .NET. I did not have any time to try out with this competition

This is a NP-complete problem competition. You can only find the way to make it better, find the most optimal solution. There are many kinds of problems here: range from encryption, game strategy and image analysis. I love game strategy most. The drawback is you have to spend a lot of time but I think that’s worth and give you a lot of fun

Bug Race will be good for tester, joining, finding bugs. Studio is good for designers. That’s all I know because I never tried this


2. Sphere Online Judge (SPOJ): Pure-algorithm competitions

I think this site is good for beginner and for people who wants to boost algorithms skills and knowledge.  If you are an algorithm lover, this site will be fun; otherwise, it seems quite boring when discussion and sharing ideas are quite limited. People compete with each other to try to get a little bit faster in time to be in the top. That is the disadvantage of this site, people spend too much time for a little performance improve, which is usually not a good practice for a software developer to do so.


 

An algorithm competition, challenging. I tried only once in last year and then this year, I think that I am still not good enough for that. It is a 3-people team competition by solving really tough algorithm problems in 5 hours. If you win, you can go to compete onsite with a wide range of topics: Information Theory, AI, Game Theory, Networking…

4. RoboCode (I think in www.diendantinhoc.org somebody is also interested in)
I am currently doing research and trying with this one for the purpose of RMITC club. RMIT students will try to learn by doing in this challenge. I hope we can learn in many different technologies: Event-Driven, Multi-threading, Agent-Oriented, Game Strategy, Software Design… See the demo below.

For me, that game looks like another agent game that RMIT Melbourne teaches for the course Agent-Oriented Programming and Design

Software Engineering and Algorithms

Algorithms and Data Structure against Software Engineering

Firstly, I want to talk a little bit about algorithms, data structure against software engineering.  Joel’s Article pointed out an excellent point that algorithms, data structure, functional programming is really important to learn, to challenge your mentality. And he is also right that current CS (and maybe IT, SE) degree is not hard enough, simply because if you designed a stupid software, it still WORKS, students will at least get  90+ points in your assignment. I see many not excellent students get 3.8 – 4.0 without any problems, because as Joel already stated, the problem in Software Engineering is when you have to extend, to make the software scalable, not when you create it. He’s all right about that. But he may make people misunderstand.

Algorithms is not the most important skill

For me, algorithm (if we consider it as a specific method to solve a specific problem rather than defined in wikipedia) is important, but it is no longer the most important skill and knowledge software engineer must have. Software engineers, nowadays, should expert about SOLID principles, and write reusable and maintainable code. Software engineers know how to design, architect and integrate between different system to write and maintain a scalable system. Software engineers can work with usability, working directly with client, understand and see the business and users’ world. These things require practice, thinking, learning from failure not just memorize them.  There are now many different jobs that do not require software engineers to become expert in algorithms, and also many great jobs requiring you to become algorithm expert. You may say that they are different jobs (like understand user’s business would be business analysis)) rather than software developers, you are wrong. Software developers now have to understand users’ mind, in general and specific domain to write usable features (read the Usability part in understand and see the business and users’ world for more details).

Algorithms != IT

Another misunderstanding about learning algorithms is that it will give you great mind in thinking in IT. It is right but not that much. In many cases, we work directly with a specific problem, like searching, sorting and computer vision. But that is a specific problem, people tried to solve it under a specific set of constraints. But software architect see the big picture, when to integrate, what to integrate and how to integrate. Both kinds of thinking are really difficult, requires creativity and experiences but hard to go for both. If people go too much into specific problem, it takes time to become an expert in another area. So, if people love one and want to become an expert in one, go for it.

But I like Algorithms

Personally, I do like algorithms so I usually do some algorithms competition in my free time on topcoder. Currently, I am working on this problem (another link if you can not access topcoder), if you want to join, just come. More people, more fun. I will write another entry to introduce about online IT competitions.