Tag Archives: computer science

Programming by Optimization

In today’s increasingly computer-oriented world, the development of software must also keep up with achieving certain tasks to meet demands. During the creation of such software, however, developers often explore different methods or paths in order to achieve a desired task. A problem that often arises though is that during the development of this “desired task”, alternate solutions that are thought to be nearly impossible to use gets thrown away, when in reality these methods might have worked later on.

Fortunately, Dr. Holger Hoos along with his research team at the University of British Columbia are working on introducing a type of design called Programming by Optimization (PbO) that directly prevents this premature toss of solutions. This has been proved to be incredibly beneficial to the development of software and leads to huge increases in software efficiency.

This is excellent news for the computer world as one of the biggest goals of large companies is increasing processing speeds and reducing running costs by, for example, using better organizational and scheduling procedures. This is where PbO shines!

PbO allows users to locate mistakes that weren’t noticed at first – this is the debugging process. PbO debugs all problems of each step in creating software separately by using interchangeable codes and provides a more efficient way of finding the correct problem. Dr. Hoos and his research team have already found a bug in a widely used commercial software using PbO and the company expressed their gratitude for it.

Although PbO is still in the research process, it has gathered a lot of attention from major companies around the world. Among others, Google showed great interest in PbO and the research team is currently working with IBM as well.

YouTube Preview Image
A component of PbO that makes it so amazing and attractive to companies is its flexibility and adaptability to software and data centers. The video above mentioned university exam timetabling as an example. Since exam periods involve many students and courses, it is very difficult to put together exam times that fit every student’s schedule. This is complicated further with the limited number of rooms available during an exam period that only lasts a couple weeks.

Now, if we were to compare the Spring semester to say, the Summer semester, you can imagine that each semester will have entirely new courses. With PbO, the scheduling of these diverse timetables comes at ease. This also works across universities, so optimization can generalize the different situations so that it can be applied to scheduling at UBC Vancouver as well as UBC Okanagan.

Data center. Image by The Ark.

The following podcast is a short talk by Dr. Hoos explaining how PbO can help data centers run better:

Audio clip: Adobe Flash Player (version 9 or above) is required to play this audio clip. Download the latest version here. You also need to have JavaScript enabled in your browser.

As more and more software get developed, programmers need a general plan to guide them through the designing process, so we can all continue to benefit from the efficiency and creativity that optimized software bring to us everyday.

References & further reading:

Hoos, H. 2012. Programming by Optimization. Magazine Communications of the ACM, 55(2). http://cacm.acm.org/magazines/2012/2/145402-programming-by-optimization/fulltext

Let’s Play Some Mario!!!

Do not think Mario games are easy because it is old and many kids are playing it. Mario is actually difficult. You think other people have no problem playing it? You are wrong.

NP-hard (non-deterministic polynomial-time hard) means problems that are at least as hard as the hardest problems in NP. Mario and and many games such as Zelda, Pokemon, and  are considerred as NP-hard. It meas it can be very hard for a player. Here are some examples of Pokemon and Zelda problems.

According to Jacob Aron. Each game can be transformed into a logical puzzle called Boolean satisfiability problem. It is used to determine if variables of a given Boolean  formula can be assigned in such a way as to make the formula evaluate to TRUE. For the games, elements suchs as enemies and mushrooms are assigned as variables in formulas to deteremine if they allow a game level to complete and produce true or make a game level impossible and produce false. In the result, games like Super Mario Bro. are proven to be NP-hard.

Mario games are also NP-complete. Many difficult problems can be classified into the NP-complete catogory. For examples, Salesman and knapsack problems are NP-complete; they require of finding the shortest route between series of points, and  how to allocate resources.

Here is just an example of very hard Mario game. (video contains coarse language. Viewer discreption is advised)

YouTube Preview Image

It is not common to run into Goomba or not be able to jump over the bottomless pit. Since Mario is proven to be a very hard game, dont feel bad to see “GAME OVER” many times.

Reference

1. NewScientist. Jacob Aron. Mario is hard, and that’s mathematically official. [Accessed March 14, 2012. ]

2. Kotaku.  Luke Plunkett. Science Proves Old Video Games Were Super Hard. [Accessed March 14, 2012. ]

2. Wikipedia. [Accessed March 14, 2012. ]