Algorithm for Finding Eulerian Paths (Python)

Udacity has excellent courses on computer science. I’m now taking my third course, Algorithms (CS215). One of the assignments of this course asked students to write a script that would find an Eulerian path in a given graph.

This topic greatly interests, so I’ve decided to research more about it. There are several solutions to the problem; I’ve implemented one based on Hierholzer’s algorithm, with some modifications to also support graphs with two nodes of odd degree. The script below successfully solved the assignment’s problem. I’ve also added comments to make it clearer.

 

Posted in Programming | Leave a comment

Mobile Web vs. Mobile Apps: A solution?

iphones

Will apps remain leaders of the mobile market, or will they be replaced by the mobile web? This question is nowadays producing one of the most heated discussions among mobile developers.

Last week, Fred Wilson encouraged readers of his blog to discuss this topic. I was going to comment on the post, but I realized that it’d be possible to expand it into a blog post. There is no consensus about this topic, and I’m not giving a definitive solution. Instead, I’ll point out some characteristics of each of these technologies and leave the conclusion to the reader. In fact, I believe that the optimal solution depends on the product. As pretty much anything else, the mobile web has positive and negative elements.

Positive:

Fast, seamless updates

Websites usually can be updated by simply uploading new files to the server. However, if you need to update an app, it needs to be submitted for review again. For instance, this often takes 1-2 weeks in Apple’s App Store. In fact, some updates get rejected and it’s necessary to resubmit the app for review. By removing the need for external review, you can push updates much faster. When a product is still under development, this perk is especially helpful.

If there’s a bug on your product, the update delay of an app review might cause you to lose users and get bad reviews. Also, I personally hate when apps ask to be updated frequently. However, web products don’t need this.

(Theoretical) reduction of development costs and time

If you want your app to be available for different devices (thus expanding the potential market), you’ll need to create multiple versions of the product. However, websites are accessible by any modern phone with internet access. By reducing the need for multiple versions, development costs and time would be reduced significantly.

I know this point is debatable, since mobile browsers aren’t equal. The website will probably be rendered differently in each device. This may be acceptable in may cases, but in some this must be avoided.

No guidelines (almost)

Apps need to conform with the App Store’s guidelines. However, if your product is on the web, it won’t be reviewed, so there are no guidelines (as long as the product is legal, of course).

 

Negative:

Phone features

Apps can access the phone’s accelerometer, contacts, dialing, etc. However, websites don’t have access to these features. Thus, if they are required for your product, mobile web is a no-no for you.

Speed

Apps will have a lot of information stored on the phone, so they’ll usually run much faster than a website. Where mobile internet connections are notoriously slow, e.g. in developing countries, this might make your product unusable. If your product takes minutes to load, the user will probably give up before he or she starts using it.

Accessibility

When a user downloads an app, his phone will automatically add an icon to the home screen. However, this does not happen with websites, which are thus more likely to be forgotten. It’s possible to bookmark the pages, but there’s no guarantee that users will do it (and it adds complexity to the process). Therefore, apps will probably have a much higher user retention rate than websites.

Technology adoption

Users are getting used to download apps, but they aren’t to the mobile web. If your target audience is tech-friendly, this is no problem. However, if you are dealing with people who aren’t inclined to adopt new technologies, this might increase the difficulty in getting users.

App store promotion

When an app becomes featured on the App Store, thousands of users will download it for this reason. Although this is rare, it has helped some obscure apps to become well-known. For now, there is no replacement (that is popular enough) for this, so you might lose some promotion (if you were lucky enough to be featured).

 

The Solution:

I believe there is no definitive solution. This will depend on the needs of the product. However, an interesting approach would be mixing these technologies. For instance, you could create an app that loads most of its content from the web. In this way, you’d get the benefits of fast, seamless updates of a website, while maintaining some functions of an app, such as app store promotion and accessibility. In fact, development costs and time would be relatively low, since part of the product will be compatible with multiple devices.

Developers should consider these points before choosing a platform. Depending on the product, certain platforms will be more beneficial. There isn’t only one general optimal solution.

Picture credit to Ricky Romero, licensed under the CC terms.

Posted in Technology | Leave a comment

Finding the Period of the Decimal Expansion of 1/n

When I was solving Project Euler’s problem 26, I had to find a way to obtain the period of the the decimal expansion of 1/n for various integer values of n. I first thought of comparing strings of digits along the decimal expansion to see if they repeated; however, this solution was neither clever nor efficient. With this in mind, I set out to find a better method for this problem.

After some research, I came across something I had never heard about in my high school math classes. The smallest integer exponent e such that b^e \equiv 1 \ (\textrm{mod} \ n) is called the multiplicative order of b \ (\textrm{mod} \ n).

This value has an interesting property. The multiplicative order of 10 \ (\textrm{mod} \ n) is equal to the period of the decimal expansion of 1/n. Note that this only works when n is relatively prime to 10, i.e. when n is not divisible by 2 or 5.

Consider a few examples:

n
1/n
Period
Multiplicative Order of 10 (mod n)
30. \overline{3}110^1 \equiv 1 \ (\textrm{mod} \ 3) \therefore e=1
70. \overline{142857}610^6 \equiv 1 \ (\textrm{mod} \ 7) \therefore e=6
90. \overline{1}110^1 \equiv 1 \ (\textrm{mod} \ 9) \therefore e=1
110. \overline{09}210^2 \equiv 1 \ (\textrm{mod} \ 11) \therefore e=2
130. 0\overline{769230}610^6 \equiv 1 \ (\textrm{mod} \ 13) \therefore e=6

Honestly, I don’t know why this property works, but it allowed me to solve the problem using an algorithm that was much faster (and clever) than my previous. If you want to look deeper into it, check the links below.

References & Further Resources

Posted in Mathematics | Leave a comment

Why Ask.com Will Fail in Brazil

Ask.com has launched a landing page for Brazilian users in order to get a share of the 80 million Brazilian internet users. However, Ask.com’s operations targeted at Brazilian users is severely flawed. Unless Ask.com changes how it operates, it is very likely to fail in Brazil, which, as mentioned before, has a huge market.

The first major problem is Ask.com’s landing page for Brazilian users. The image below shows the American landing page and the Brazilian landing page.

The American landing page (above) and the Brazilian landing page (below)

The differences between both pages are clearly visible. The American page is filled with valuable content, including an interactive quiz. However, the Brazilian version is not even related to questions, which should be one of the most important features of the other page. The Brazilian page is very weak and not likely to be competitive with Google for general searches. The main twist, which could be a great feature, was left aside.

Even Ask.com’s search feature is poorer in the Brazilian version. It has no internal QA system, no search terms suggestions and no search options such as image search. Moreover, the amount of ads in the Brazilian page is higher than in the American version. But most importantly, most results are generally not relevant. A search for Olimpíadas (Olympics in Portuguese) gives poor results, excluding two Wikipedia pages in the middle. Therefore, the only feature that the Brazilian version has is also greatly flawed.

The Brazilian version is not under construction, for Ask.com is advertising their page for Brazilian users. Nonetheless, their ads are also faulty. Refer to the ad below, which I saw on Youtube in July 2012:

This ad appeared on Youtube in July 2012

The sentence “Onde foi Marisa Monte nasceu?” is grammatically incorrect. It is a word-by-word translation from “Where was Marisa Monte born?”, but the correct version should be “Onde nasceu Marisa Monte?” (or other correct variation). Moreover, the call-to-action used in this ad is written in English. It would be much more effective to write it in Portuguese (“Descubra”) since many Brazilian do not speak English. It is also strange that part of the ad is written in Portuguese, while another part is written in English. At last, the picture in the background is from an American birth certificate, which may also not be familiar to many Brazilian users (a Brazilian birth certificate could be used instead). These changes would greatly increase the quality (and thus the conversions) of this ad.

Therefore, the Brazilian version of Ask.com’s website is much weaker than the original version. The only feature it has, search, is also worse than in the American version. Furthermore, Ask.com’s ads are faulty and contain translation problems. Therefore, unless Ask.com changes how it operates in Brazil, it is very likely to fail in attracting Brazilian users.

Posted in Business | Leave a comment

4 Lessons from Stanford’s Online Technology Entrepreneurship Course

Stanford UniversityIn March 2012 I started to participate in an online Technology Entrepreneurship course by Stanford University. Before joining this course, I had little experience in entrepreneurship and it has helped to learn much about this. Here are the most important lessons I learned during this course:

 

1. The importance of a motivated team

This was the first thing I learned. The teams for the first two assignments were not chosen by the students, so I was assigned to a team of 10 random people. All the other members of my team did not really want to participate in this course. Some had signed up for curiosity, some did not have enough time anymore, and some were unreachable. I tried to engage them into discussion for the activities, but I was unsuccessful.

The deadline was near, so I finished the project by myself and submitted it. I learned from doing it, but I am sure that I could have learned much more if the other team members had participated. Luckily, my team for the startup project (the most important part of the course) is very active. Although our product is not finished (I will write about this in another post), I have learned much from these interactions.

 

2. International teams are a double-edged sword

My team for the startup project initially had 8 members from different countries: Brazil, China, Equador, India, Ireland, Latvia, Singapore, and United States. Having an international and multicultural team has many benefits, but it can be problematic too. The most evident issue is communication; it is hard for me, located in Brazil, to chat in real-time with someone from Asia. Moreover, being unable to talk face-to-face to other team members (except in Skype) makes the project more complicated. In order to overcome this communication problem, we are using many tools, such as Facebook Groups (chatting and messaging), Trello (task management) and Skype (real-time conversation).

However, this feature of our team has positive aspects too. Most notably, each of us have knowledge and experience that others do not have. We can learn much from others in this way. Also, this allows us to be at different parts of the world without big costs – which is especially helpful for an early-stage startup. It was a very interesting experience for me to work in such a group.

 

3. Startups can avoid costs with creativity and determination

As an early-stage startup without funding, it is fundamental to be able to cut costs. There are times when this is hard. But with creativity and determination, many costs can be avoided. For example, we needed a tool for task management and messaging. The most popular tool for this is probably Basecamp by 37signals, but it would cost us at least $20/month. Therefore, we decided that we should search for other tools. In the end, we found Trello, which is free and managed to solve our problem efficiently. The only cost that we had so far was the domain name, which costs less than $10/year.

 

4. Learning by doing is very efficient

The lectures by Prof. Eesley were superb and filled with relevant content. However, I feel that most of what I have learned did not come from there, but from the projects and assignments. Trying something by yourself is very rewarding and I feel that I learned much about entrepreneurship by trying to launch a startup. The best way of learning something is by trying to do it, even if you fail at first.

Posted in Entrepreneurship | Leave a comment