Greedy algorithm, Google Map vs Map Quest, WiFi vs 3G

Comment 1:

Are there other algorithms to find the shortest path that use recursion or dynamic programming?

Follow-up:

Yes there is one called Floyd-Warshall algorithm that uses dynamic programming to find all-pairs
shortest paths. This algorithm can also handle graphs with negative link weights.

Comment 2:

What happens in the shortest path greedy algorithm (i.e., Dijkstra) when two distances surrounding the node are equal?

Follow-up:

Good observation. We will usually just “randomly” choose one to break the tie.

Comment 3:

Any technical and systematic ways to calculate the time-complexity of an algorithm?

Follow-up:

Yes sure. For more complicated situation, we usually end up having a bunch of summations of series in the counting of number of key steps. Then, we will need to use some mathematical tools to obtain closed-form expressions. These are computer science topics, though.

Comment 5:

If 3G and Wi-Fi on my smartphone are similar things, why do I notice a significant difference between the speed of loading the same page on 3G and Wi-Fi?

Follow-up:

3G and Wi-Fi are similar in that they are both wireless communication technologies. But the similarity ends there. The wireless communication mechanisms used are highly different in many aspects. For example, 3G is based on cellular communication which is designed for longer range and thus, speed is lower (as electromagnetic signals deteriorate significantly over a distance). Wi-Fi is of a much shorter range and can therefore afford to provide a higher speed. There are many other technical differences, which are topics of a wireless communication and networking course.

Comment 6:

The “shortest path algorithm” can be demo-ed on 9 slides with animation instead of using just one slide. It is a bit too small.

Follow-up:

Thanks for the comment! You are right! Will improve this. Sorry for the inconvenience.

Comment 7:

How come MapQuest/Google-Map is so fast on a map that has billions of nodes?

Follow-up:

One trick is that MapQuest/Google-Map generally does not do the computations “on-demand”, i.e., they pre-computed many routes which are then stored in the database. When someone posts a query, majority of the routes are pulled out from the database.

Comment 9:

How to resolve the conflict when there is negative weight in the graph when using Dijkstra’s
algorithm?

Follow-up:

Dijkstra’s algorithm fails when there is negative weight in the graph. We will need to use a different technique, e.g., the Bellman-Ford algorithm. See also Comment 1 above.

Comment 10:

You have mentioned that researchers in the field of computer try to giving everything an unique ID (a unique IP address), for example, a microwave oven. However, I don’t really understand why we are going to do so. What are the purposes? If that applies widely, will there be any privacy problems?

Follow-up:

Yes sure I believe there will be significant privacy problems! Maybe you can consider using this as your survey topic?

Comment 11:

How do we obtain (e + n log n) for Dijkstra’s algorithm?

Follow-up:

A rough sketch as follows: We need to examine all the links (during the updating of the estimated distances labelled on the nodes) so that is why we have the e term. We need to sort the nodes in an increasing order of estimated distances and that is why we have the n log n term.

Comment 12:

Why greedy approach usually results in a fast algorithm?

Follow-up:

This is because as we make a greedy choice in each step, we reduce the problem size by 1. Thus, after making n greedy choices (i.e., n steps), we will finish the problem. Consequently, we usually end up having an algorithm that takes O(n) time, together with the time needed in some pre-processing (e.g., sorting, which takes another n log n time).

Comment 13:

Knapsack problem. It can e applied to daily life. Is it similar to linear programming taught in Maths at cert level?

Follow-up:

Yes it is similar. Wait until Tutorial 3 to find out more details.

Comment 14:

Dynamic programming is a bit difficult to understand. Also the DNA sequence example.

Follow-up:

The theme of Tutorial 3 is about dynamic programming. Hope you would feel better after going
through this tutorial cycle. The DNA sequence example is interesting and I think you can understand at least 70% of it by studying the Web page mentioned in class.

Comment 15:

I am a bit confused of the graph that represent the different representation of running time that results in different value.

Follow-up:

I think you are talking about the “estimated distances” labelled on the nodes in the example graph for showing how Dijkstra’s algorithm works. Those values are NOT running time (of an algorithm). Those are used for representing, for example, the time it takes to travel from one place to another geographically (when we use the graph to represent a map).

Comment 16:

Why “99” is used to represent the information that has not been processed?

Follow-up:

Yes in computer programming we usually use such tricks to ease processing.

Comment 18:

Google-Maps are more developed than MapQuest these days. For example, it can alert that friends are located close by to you.

Follow-up:

Thanks!

Comment 21:

I am not quite clear about how two determinant factors will affect the efficiency of greedy approach.

Follow-up:

The main factors are the “greedy choices”. If you pick the right greedy choice at each step, the
algorithm would end up giving “optimal” result. In terms of speed, please refer to Comment 12 above.

Microblogging: Twitter

Seitzhan Madiyev

The Information Technology industry has been surprising us slightly. After the creation of Google search engine and the “internet bubble” crisis in 2000s, it began developing a little bit slower and in different direction than many expected. People were predicting about future IT industry; how it will change the way we live. As the time has passed trends that were predicted in that time did not achieve their expectations, or simply did not get enough attention from the community. But instead other projects came into place; those which most of the people did not even think about ten years ago, but without which a lot of people cannot imagine their lives nowadays. The top trend of this decade was given to a group of products that can be called “social networks”. And between monstrous creation of Mark Zuckerberg and a huge failure of “MySpace” there was one more invention which I believe will have an even greater impact in the nearest future “Twitter”.

How it works
Twitter is a simple microblogging service which allows users to send and read text-based posts of up to 140 characters. When a user wants to read public messages sent by another user of his interest, he/she simply connects to it through a button named “follow”. And those who follow the user will get all the messages sent by him. It was firstly described by its creators as a service that uses SMS to tell small groups what you are doing. When people create an account there, the site simply asks you to share with others “What are you doing?”.

Socio-political significance
Twitter was often criticized for uselessness since its users were bringing a lot of “rubbish” and meaningless information, like “I ate a sandwich”. However, since 2008 the project took an important socio-political significance. In February 16, 2008 the photographer James Buck was arrested by Egyptian police. He wrote “arrested” in his twitter account which quickly came to the US authorities. The next day he was released. During the U.S. presidential elections Twitter was actively used by both candidates Barack Obama and John McCain for their campaigns. It was blocked in many countries for the purpose of not spreading information of some events.
When the management team understood the importance of their service, they have changed the business model the question has been changed to “What’s happening?”. The society started to realize the importance of the project. It became the fastest media platform to release the latest news and updates on almost all events occurring in the world. Now even media outlets are forced to get the newest information from Twitter with the risk of reporting false information. It has become the most efficient media platform, since all people who have an account there have become the reporters.

A lot of people argue that most of the messages that occur in twitter are so called “Pointless Babble”. So the research has been made to analyze what people actually share with others, and the results were interesting. Pointless Babble won with 40.55% of the total tweets captured; however, Conversational was a very close second at 37.55%, and Pass-Along Value was third (albeit a distant third) at 8.7% of the tweets captured. (Twitter Study) Pass-Along Value is the messages that actually matter; those are the newest news, relevant information and shares of interesting thoughts by famous politicians, business people, etc. Although it is only 8.7%, but it is still large in general terms since around 200 million tweets are sent every day.

New business model
Twitter has created an absolutely new way for businesses to promote their products and for people to promote themselves. Since 2000s marketing has been moving more and more towards the Internet, and just few years ago so called “social networks” helped to create new business models and increase the efficiency of marketing. One of the most important tools created because of social network is the “target marketing”. It simply allows businesses to find the right audience to promote to dividing all the users by different groups. But if social networks like Facebook are efficient platform for targeting adverts, how Twitter has created a new way? It is simple: “Brand Journalism”.

Nowadays adverts don’t get enough attention from public and become less and less efficient, and that is where brand journalism might come in the nearest future. Brand journalism was created as a tool to promote products and companies in an innovative way. A company can hire a professional journalist which can write only about this company, its everyday activities, new products, the chronicles of what has happened. People are interested to hear new stories, and Twitter is an ideal platform to tell those stories, to share photos and links.

I believe that Twitter has not achieved its peak yet, and it has more to come in the future. From being on of the most innovative products of these years, it might become an essential part of our lives.

References

1. MG Siegler. Russian President Medvedev Sends His First Tweet At Twitter. — TechCrunch, 23.06.2010
2. Chris Nuttall. What’s happening? A lot, says Twitter COO. — The Financial Times Tech blog (blogs.ft.com/techblog), 20.11.2009
3. Twitter: "pointless babble" or peripheral awareness + social grooming? — Danah Boyd blog (www.zephoria.org), 16.08.2009
4. Owen Fletcher, Dan Nystedt. Internet, Twitter Blocked in China City After Ethnic Riot. — PC World, 06.06.2009
5. Om Malik. A Brief History of Twitter. — Gigaom.com, 01.02.2009
6. BBC admits it made mistakes using Mumbai Twitter coverage. — The Guardian, 05.12.2008
7. Claudine Beaumont. New York plane crash: Twitter breaks the news, again. — The Telegraph, 16.01.2009
8.  John Brandon. Barack Obama wins Web 2.0 race. — ComputerWorld, 19.08.2008
9. Twitter Study. — Pear Analytics. — August 2009

Whatsapp Messenger

Before the popularization of 3rd generation mobile telecommunications (3G) and Wi-Fi technology, people use Short Message Service (SMS) to text their colleagues, partners, friends and other people. Although handy, SMS has several drawbacks itself. The messaging cost is sometimes a trouble-some problem and the character limit of one message also poses a barrier to people using standard SMS as an exchange of information. Using other types of instant messaging tools on smartphones cannot solve the problem either because of compatibility issues. But now as Whatsapp Messenger (Whatsapp) emerges, these problems seem to be solved. This survey will focus on the working mechanisms of Whatsapp and how it affects the society.

Whatsapp is messaging software available on several popular mobile operating systems, including iOS, Android, Blackberry and Symbian. It makes use of internet connection, instead of cellular connection used by SMS, to deliver messages from one phone to another.

When a person sends a message, Whatsapp will deliver the message to the server. The server will then deliver the message to the destination. No matter what kind of smartphone the user is using, as long as it is installed with the messenger, the messages can be delivered to the phone and can be seen. The compatibility issues do not exist. Other than simple text, Whatsapp message can also be consisted of photos, videos and audios.

As 3G and Wi-Fi technologies are gaining popularity all around the world, and more and more people are replacing their cellular phones by smartphones, the number of Whatsapp users is growing. Its cross-platform feature also enables people to exchange messages between different brands of smartphones. In addition to the basic text messaging functionality, it also supports multimedia messages, which enriches the context of the messages. More importantly, it connects to the server via the Internet, and only requires the user to have a data plan for the 3G services or to have access to Wi-Fi coverage; the cost of messaging is much reduced.

All in all, the emergence of Whatsapp provides a more convenient way for people to send instant messages with enriched context and a lower cost. It can be foreseen that in the future, as the cost of 3G services getting cheaper, Whatsapp Messenger will gradually replace the standard SMS as the major messenger tool in the society.

Microblogging -- Twitter & Sina Weibo

Liu Songling

Introduction

Twitter is an online social networking and microblogging service that enables its users to send and read text-based posts of up to 140 characters, informally known as "tweets", and images.

Sina Weibo (Chinese: 新浪微博; literally "Sina microblogging") is a Chinese microblogging site. Akin to a hybrid of Twitter and Facebook, it is one of the most popular sites in China, in use by well over 30% of internet users, it has a similar market penetration that Twitter has established in the USA.

Rapid Development

Twitter was created in March 2006 by Jack Dorsey and launched that July. Twitter rapidly gained worldwide popularity, with 200 million users as of 2011, generating over 200 million tweets and handling over 1.6 billion search queries per day. It is sometimes described as the "SMS of the Internet."

Sina Weibo was launched by SINA Corporation in August 2009, and now has more than 200 million registered users. A two-year-old block on Twitter setting being accessible in China has allowed Sina’s homegrown Weibo to flourish - and now it’s blossoming in to far more than a Twitter-style microblogging tool.

Social influence

a. Twitter

As one of the most popular social network sites in the world and with more than 10 languages in used, Twitter has an indisputable influence in both the daily life of humans and issues of the society.

Nowadays, people spend an increasing time chatting online or with cell-phones, with great interest in what their friends or some other famous people are doing. Thus as a convenient internet posing wall for users to update their moods, status just via text-based posts, twitter not only provides the commenting and chatting services like Facebook, but also let users become “followers”, which enable users know not only their friends’ status but also other famous people,  their interested companies, organization and so on.

“Followers” in twitter, like fans or supporters, by leaving comments or reply to a status can somehow show their supports or arguments, and can even reflect the public opinion on a certain social event. For example, in August, 2009, when the opponents of Obama’s health care reform plan aggressed the National Health System (NHS) of UK, thousands of the users of NHS used the #welovetheNHS label in twitter to support NHS and refute the campaign of U.S.Right, winning the Prime Minister Gordon Brown’s support and respect.

b. Sina Weibo

Owning similar services with Twitter, Sina Weibo, though established only 2years ago, now also has a great influence in the society. Mainly used by people in China, the impact of Sina Weibo largely focuses on the care of the life of people. People in Sina Weibo not only share some advice and tips of daily life, but also warm-heartedly post some advertisement on emergent need of hospitals and disaster area. For instant, the reason why Yao Chen becomes the Queen of Weibo is not just the humor language she used in her post, but her consistent post for the people in urgent need for help. People love to see that famous Weibo owners take advantage of their large amount of fans to help others with widely advertising instead of promoting products.

Also, like news broadcasting, Weibo users report and describe the real situation of big events and disasters, enable people in the nation get the fastest information. For example, in the disaster of the train crash in Wenzhou China, on 23rd July, 2011, people post the condition of the crash and the people injured in Weibo, which was more informative and timely than TV news report.

Advertising effectiveness

a. Twitter

While hesitation over making purchases for products through the networking sites has abated, what along with the widely use of Twitter, of course, is the great profit from advertisements. While Facebook may take the lion's share of social media marketing budgets, Twitter is fast catching up and eMarketer has estimated that worldwide advertising revenues will rise by 210 per cent by the end of this year. This represents moving from $45 million (£28.7 million) earnings in 2010 to an expected $139.5 million (£88.9 million) by the end of 2011. The marketing analysts also forecast that Twitter's worldwide ad revenues will reach $400 million (£255 million) by 2013.

Also, economic advantages come from the cooperation between mobile phones and Twitter. For example, Samsung announced the launching of Galaxy S, a Smartphone manufactured by Samsung, in Korea in detail via the Twitter. Usages like these certainly helped people in terms of receiving information quickly. This not only enables people to use Twitter with smartphones at anytime in anywhere, but also decrease the cost of communication. It is estimated that over half of Twitter users use their webpage by mobile devices. While other online services such as blogs and MSN Messenger require people to be stationed, Twitter can be accessed while moving. Moreover, other online communication systems such as MSN Messenger ask users to sign in. This means that people have to stay in their seats in order to use the system, which is a huge inconvenience.

b. Sina Weibo

Via such kind of social network, not only companies advertise their products by posting ads, but users publicize the products they love by showing their pictures and comments. Recently, it has become a trend that users would love to post what they have bought and what they have eaten on Sina Weibo, which then cause a great popularity of the product or the restaurant that is appreciated and forwarded by many other users. Since people would rather believe what their peers and friends preferences, thus the effectiveness of such advertising may much more powerful than TV ads. 

Conclusion

Though I just talk about the development, social influence and advertising effectiveness above, there are many other information and benefits of these two social networks. However, apart from their advantages, they also have their respective limitation. For instant, Twitter has no constant, long-term income source, which makes it hard to decide whether to choose the profit from companies’ advertisement or the users’ favors, as it may worsen the perception of users about twitter if it intentional creates a platform for advertisements. Also, Sina Weibo only has Chinese version which greatly limits its development and expansion. 

Reference

1. http://zh.wikipedia.org/wiki/Twitter
2. http://en.wikipedia.org/wiki/Sina_Weibo
3. http://www.equimedia.co.uk/index.php?id=98&article=800744322
4. http://ahnyoungjae.wordpress.com/2010/12/12/economic-benefits-and-limitations-of-twitter-and-the-future/

Influence of Smartphone in the business sector

Thanks to the advanced technology, smartphone has become a new milestone. It is not only improved on the performance but also the functions. According to Vercillo (2010), there has been 96% increase in smartphones sale between the third quarters of 2009-2010, which is a huge number of smartphone sales ever. In reality, smartphone is widely applied in business world. In this essay, how smartphone is influencing the phone company and business firm and how consumers treat smartphone.

Firstly, phone companies will earn more profit. Smartphone has started to replace the mobile phone market. In the past, the smartphone was not as common as today. The improvement of the internet network, the apps and software of smartphone being introduced and so on are the associated factors that contribute to the popularity of smartphone. In Hong Kong, the population of having a smartphone is double than the global rate, which is 48% (TNS Global Telecoms TNS Insights Survey, 2010). As Hong Kong is a business city, it is not surprised that there is a high rate of usage of smartphone. Moreover, the quality of the smartphone is being improved, for example he battery life, increased in memory and speed of loading data. More people will tend to get the smartphone, rather than the traditional mobile phone. Therefore, the sale of smartphone in future will definitely be increased, which means the phone company would have more profit. However, there are disadvantages to the phone company with smartphone being more common. Since there would be more smartphone to be produced, it will increase the competition between them. In order to gain the profit, they have to spend more time and money on inventing the new product or improving the quality of supported service, for instance the apps and updating the software. They may also need to have better marketing strategies on selling their product. The sale of the traditional mobile might be affected by the smartphone. Therefore, the mobile company has to work hard on maintain the competitiveness.

Secondly, smartphone assists business companies in different way. Businessman can easily access internet with a smartphone. In fact, smartphone users normally use email, mobile internet and Microsoft Office (TNS Global Telecoms TNS Insights Survey, 2010). They are no longer limited by the place and time to run their business. Also, the business companies can use smartphone as a channel to promote their company. Most of the banks have made their own apps to serve the customers, like Bank of China, HSBC, and Bank of East Asia. Also, H&M, Chanel, Hugo Boss and Pizzahut Hong Kong allow customers to do the ordering through the Iphone applications. Festival Walk and Langham Place has their own apps as well. In this way, it not only promotes their company, but also increases the sale. Therefore, smartphone is a useful tool for the business company.

Yet, there are technical limitations sometimes. The consumers who use the smartphone would have certain knowledge of using smartphone. The business company would not be able to target the customers who do not smartphone well. So, the business companies need to give clear instructions. Sometimes, even if the business companies provide different services through the smartphone, it might not be used by everyone. The banking application is one of the examples. According to Zetter (2010), there are some banking applications that expose customer data. In order to protect themselves, the customers would not prefer using apps to do any transactions. It is obvious that the technical problems still exits sometimes, regardless of the advanced technology.

Smartphone does bring conveniences to consumers. Consumers can browse all the updated information from the web or apps whenever they need, particular those who are in finance or stock market. They can also contact, send e-mail or even holding video-conferencing through smartphone as it is a reliable tool with high speed. Smartphone’s user is usually businessman (Vercillo, 2010). It can be noted that smartphone does assist customer on their business.
Nevertheless, it is not everyone who would choose to use smartphone. It is more common for people to use smartphone, but it is still more expensive than the traditional mobile phone. Also, consumers do need to be affordable to use some of the services sometimes, like browsing the web or downloading apps. In general, people with older age would not use smartphone since they are lacking of the knowledge or not used to high-tech products. Therefore, financial and age could be the factors which affect people to choose smartphone.

In conclusion, smartphone has become more common and the trend will keep being increased. The sale of phone companies benefited a lot from it. Yet, they still have to spend resources on maintain the competitiveness of their product. Also, smartphone also assists busniess firm in certain extent and the technical problems of using smartphone is still being improved. From the consumers’ side, getting a smartphone or not is still depending on the purchasing power and the background that they come from. Therefore, smartphone is highly related to us nowadays, especially on the business aspects.

Reference

1. TNS Global Telecoms TNS Insights Survey, 2010, Smartphone usage set to dominate Hong Kong mobile market, Retrieved 20 November, 2010 from http://www.tnsglobal.com/news/news-DB5EF16289044655A787385A433A896F.aspx
2. Vercillo,K. , 2010, Nearly 100% Increase in Smartphone Sales in Past Year, Retrieved 20 November, 2010 from http://www.tnsglobal.com/news/news-DB5E F16289044655A787385A433A896 F.aspx
3. Zetter, K. 2010, Smartphone banking apps expose sensitive customer data, Retrieved 21 November, 2010 from http://arstechnica.com/gadgets/news/2010/ 11/smartphone- banking- apps-expose-sensitive-customer-data.ars

Carrying a computer all the time? The Pervasive Use of Smart Phones

Mary McDowell, Executive Vice President for Mobile Phones at Nokia, states that “80% of the world’s population is now within range of a cell-tower – people aren’t going to use PCs to connect [to the Internet], they’re going to use affordable mobile devices”.

Few years back with the inventions of portable, compact computers the business transactions became very convenient. But today this technology is being replaced by smart phones at a rapid pace. When asked 79% of the respondents cited the smart phone as a means of organizing the business than the office PC’s or the laptop. According to another survey 38% of Chinese mobile subscribers access the Internet from their hand.

According to a research by Ypartnership/Harrison Group which involved of 2,524 households, three in ten mobile phones in USA are internet enabled phones. One in five of them (19 %) had downloaded travel-related application. Travel app is a particularly easy and efficient way to get information for the business individuals. Previously laptops were used to access to any information. For example with the invention of TripIt, iPhone travel app that keep routes updated whether one is online, offline or in airplane mode have made the trip for the business individual more feasible. According to a research about 47% travelers use GPS to find the way to destination. Hence the use of laptops is becoming outdated from the lives of the business individual in looking forward for the information about the destiny of their business trip. The maps are available in the phone which can be conveniently accessed.

Business individuals use smart phones to keep track of their daily appointments. Applications such as reminder in the smart phone play the role of a secretary. The functions on the smart phone for example a calendar let the user create a reminder and add details of the meeting. In his busy schedule, the business man might forget but the phone serves as his assistant. In order to run the business successfully, one should show up for the meetings on time. Otherwise this will have an adverse impact on the business. Clients may consider one as non-serious or unprofessional.

The smart phones are further used in organizing the business by pairing them up with the computer. The phone can be connected using a USB cable or via Bluetooth. An individual will stay updated with the information. The data can then be processed in text editing softwares which are easily available in phones. The information can be accessed when offline or immediate access in a meeting. So it gets very convenient to access the information just by clicking few keys rather than to carry a laptop. With the push of a button, one has instant access to a client’s email address, phone number, instant messenger name and much more. This becomes very efficient when contacting a client when one is not at the office. With the smart phone a business individual is always in reach of the co-workers and clients. There are no barriers of internet usage which occur while using e-mail service.

With the data and contacts the individual can work at any place whether he is relaxing at home or travelling in a car. The usage is very convenient too as the personnel just have to carry a small device of negligible weight when compared to laptops.

The next question which arises is “does a smart phone have a fax service?” The fax is not the first priority when a business individual has internet access via his smart phone which allows him to e-mail the important documents. The documents can be saved or read in the portable document format (pdf). Fax services such as “Myfax”, “efax” can be approached which allow the user to send and receive faxes on a smart phone.

The camera in the smart phone is used for video conferences with the clients and workers. The smart phone can be used as a mini copy machine as important document can be captured via camera. Some phone cameras, such as the one on the Omnia/Omnia II, include a Text mode setting to make it easier to photograph a document. In some phones, camera can further be used for the efficient uploading of the directory. For example in Omnia there is a business card reader called Smart Read; with this software we can photograph a card and the information is extracted and directly put in the contacts phone book. It makes use of Optical Character Recognition (OCR) program that converts images to text.

If one is in a field, images of the items can be taken relevant to job and can be mailed to the office. It can even be sent to the client or used in a meeting to give a clearer view to the client rather than describing. Picture of the clients can be taken and later can be assorted in the directory along with their names. In this way it gets very easy to remember the people in future.

Due to the priority given to the smart phones over laptops, the software companies are devising new programs to further increase the efficiency of phones in business organization. One such software is “Google Finance”. It enables fast access to finance data, charts, and reports. With the aid of graphs and charts a person can predict the future trend. This is immensely useful in stock market and in other fields. In stocks a person can evaluate a constant change in stocks rate by device carried in a pocket (smart phones). This enables them to take quick decisions thus decreasing the reaction time. The individual can perform market research. This can in return save a particular company from potential loss as a person can understand the impacts and risks of investment. Furthermore the overall economy will also be strengthened. This is because of the integrated approach of the individuals in managing the capital due to the convenient access to market analysis with the aid of smart phones.

The smart phones on the other hand are not user friendly. They have a small screen of few inches and small keyboard size. It gets tiring while using them for a long time. At the end of the day, the individual may not be able to concentrate on the work and think intellectually. This may further lead to commitments and transaction which may result in a potential loss.

More over from the other aspect I will say smart phones have become essential part of one’s life. A person could not take a day off from using his phone. As a result there is no designated number of hours a person works daily. There is no clear delineation between home life and work life. This further impacts the relationships and give rise to social problems. Additionally this will affect the health of the individual. As the person is under continuous stress and workload with little leisure time, he may suffer from health drawbacks such as psychological problems, diabetes mellitus, cluster headache, blood pressure and heart diseases.

The websites viewed on the smart phones are edited by the software to optimize the web pages for the small screen of the phone. There may be some important data missing. The small size of the screen and the scrolling of the page become exhausting for an individual. As a result a person may ignore some information. This again is an important factor with can have unfavorable consequences.

The cost of using the smart phone for business purposes is relatively higher than using the computers. This is because of the long-term contracts between the users and cell phone providers. According to a research, the internet service provided increases the cost by $70 to $100 for the user. This tells us that small businesses cannot make use of smart phones to organize their business efficiently. So this can be regarded as a drawback. It can be concluded that this technology can only be availed by big enterprises.

Some users find the smart phones complicated. It takes time for them to learn and adjust to new features. As the new technology is emerging this means the user has to spent considerate amount of his time in learning the new programs. Handsets of different companies have unique features and graphics. So as a result it gets difficult for the user when he switches on a new handset. This problem is very frequent as the average life of phone is one year.

The smart phones have several advantages as discussed above but on the other hand there are many setbacks. According to my perspective the unique features of the smart phones outnumbers the drawbacks. The immense importance given to the smart phones can be judged by the sale of the smart phones even during the recession period. According to a research firm NPD Group “the high-end devices, which assemble computer-like features into handheld devices, accounted for 23% of U.S. mobile phone purchases by consumers in the fourth quarter of 2008, up from 4% two years earlier.” Due to the increasing use of the smart phones, the worldwide sales of smart phones grew 30 percent in the fourth quarter of 2009 to 53 million phones. The number of smart phones in use globally is expected to hit 1.7 billion by 2014.

Under the light of the above discussion, the success of smart phones as mobile computing platforms can be attributed to the ‘micro- form’ factor. It is a tremendous benefit for convenience and portability. The smart phone for a business individual provides a dual function of a mobile and as an organizer or a laptop. Due to this psychological factor the use of smart phones for business is increasing at a rapid pace.


Reference

1. http://blogs.techrepublic.com.com/smartphones/?p=1364
2. http://www.allbusiness.com/reports-reviews-sections/polls-surveys/14415704-1.html
3. http://reviews.cnet.com/4321-6452_7-6544038.html
4. http://www.pcworld.com/businesscenter/article/194137/business_professionals_choose_smartphones_over_coffee.html
5. http://www.cioinsight.com/c/a/Trends/9-Reasons-Smartphones-Will-Take-Over-Business-Computing-743743/
6. http://news.softpedia.com/news/Google-Finance-Optimized-for-Smartphones-153641.shtml
7. http://www.pavingways.com/category/statistics
8. http://thenextweb.com/socialmedia/2010/09/23/how-mobiles-will-drive-social-media-in-developing-countries/
9. http://www.cellphone-advertising.com/mobile-applications-revenue-to-reach-32-billion-in-2015/
10. http://www.ehow.com/how_4524176_use-smartphone-organize-business.html
    

Society Impact on Smartphone

Have you thought what you can do on the home PC - such as checking and sending e-mails, doing researches - can now be done on a Smartphone; which is way smaller and can be put into the trousers pocket for daily uses?

“In 2007 iPhone reinvented what we thought of as a Smartphone” (Jobs, 2010), which I totally agree. Nowadays, most of the Smartphone promotes the large number of applications that users can download, for example, Apple’s App Store on iTunes, provides a very organize place for both program developers and users to upload and download over 300,000 Apps to use, and the total number of the Apps that has been downloaded reaches 7 Billion times in October 2010 (Apple Inc., October 20, 2010); however, in the old days, there were no such App Store, the applications were to be installed with a CD via a Computer, and there were very limited choices.

Different purposes applications, such as games, education, finance and medication can be accessed very easily. As they are simple and easy to use, this then increased the interest and attraction of Smartphone to different kind of users. For young adults like myself, I tend to have about six pages of games on my iPhone; for my dad, he uses his Nokia Smartphone to read news on the go; while my mum only uses her phone as her ‘cook book’.

Some applications provide the uses for communication (calling and texting each other), for example Skype. Personally, I used to be an overseas student; I think the function of Skype is very useful and easy assessed. Being able to install the application of "Skype" on the phone allows me to contact my parents and friends more easily while overseas – I do not need to call a connection line and type in about forty digits of user number and password, this has make my life much easier, especially in the case of emergency. Cost wise, using Skype to call for overseas number is much cheaper than traditional international calls; in fact, it is free of charge if both parties have an account on Skype (Skype, 2010).

Also, users can access to internet and even personal e-mail via WiFi or 3G network provide by the Phone Network Service Provider. Using the internet service on Smartphone is believed to be as secure as using PC at home; this proves the convenience of Smartphone.

The tale of writing a letter and posting it has became a history, email has successfully replaced the traditional mail, with no doubt. Being able to send and receive e-mail has simplified the ways of living, in additional to the Push services (MobileMe, Yahoo!, Hotmail, Microsoft Exchange) (Apple Inc., 2010) allow us to get email when it is sent, rather than we need to fetch it about three years ago. Moreover, large attachments, such as photos, can be attached on the e-mails for reference; our life has become way easier.

Have you thought what you can do on the home PC - such as checking and sending e-mails, doing researches - can now be done on a Smartphone; which is way smaller and can be put into the trousers pocket for daily uses?

“In 2007 iPhone reinvented what we thought of as a Smartphone” (Jobs, 2010), which I totally agree. Nowadays, most of the Smartphone promotes the large number of applications that users can download, for example, Apple’s App Store on iTunes, provides a very organize place for both program developers and users to upload and download over 300,000 Apps to use, and the total number of the Apps that has been downloaded reaches 7 Billion times in October 2010 (Apple Inc., October 20, 2010); however, in the old days, there were no such App Store, the applications were to be installed with a CD via a Computer, and there were very limited choices.

Different purposes applications, such as games, education, finance and medication can be accessed very easily. As they are simple and easy to use, this then increased the interest and attraction of Smartphone to different kind of users. For young adults like myself, I tend to have about six pages of games on my iPhone; for my dad, he uses his Nokia Smartphone to read news on the go; while my mum only uses her phone as her ‘cook book’.

Some applications provide the uses for communication (calling and texting each other), for example Skype. Personally, I used to be an overseas student; I think the function of Skype is very useful and easy assessed. Being able to install the application of "Skype" on the phone allows me to contact my parents and friends more easily while overseas – I do not need to call a connection line and type in about forty digits of user number and password, this has make my life much easier, especially in the case of emergency. Cost wise, using Skype to call for overseas number is much cheaper than traditional international calls; in fact, it is free of charge if both parties have an account on Skype (Skype, 2010).

Also, users can access to internet and even personal e-mail via WiFi or 3G network provide by the Phone Network Service Provider. Using the internet service on Smartphone is believed to be as secure as using PC at home; this proves the convenience of Smartphone.

The tale of writing a letter and posting it has became a history, email has successfully replaced the traditional mail, with no doubt. Being able to send and receive e-mail has simplified the ways of living, in additional to the Push services (MobileMe, Yahoo!, Hotmail, Microsoft Exchange) (Apple Inc., 2010) allow us to get email when it is sent, rather than we need to fetch it about three years ago. Moreover, large attachments, such as photos, can be attached on the e-mails for reference; our life has become way easier.

Reference

1. Apple Inc. (October 20, 2010). Apple Special Event.
2. Apple Inc. (2010). iOS Data Management. Retrieved 2010, from Apple Developers: http://developer.apple.com/technologies/ios/data-management.html
3. Jobs, S. (2010). WWDC . Apple Inc.
4. RCR Wireless. (2010, July 14). The smart phone impact on consumer mobile usage habits . Retrieved from Analyst Angle: http://www.rcrwireless.com/ARTICLE/20100714/OPINION/100719994/analyst-angle-the-smart-phone-impact-on-consumer-mobile-usage-habits
5. Skype. (2010). Skype. Retrieved 2010, from Skype: http://www.skype.com/

Cryptography using key

Problem:

(a) Suppose that there are n people who want to communicate with each other securely. How many keys are needed when a symmetric key cryptosystem is used? How about public key cryptosystem? Explain.

(b) Digital signatures cannot be done using symmetric key cryptography. Explain why.

(c) Suppose we produce a “digest” of a message by simply adding up the words (e.g., treating each character as a 8-bit number). What is the problem of this approach?


Follow-up:

(a) Using symmetric keys, the number of keys required for pair-wise communication is nC2 = n (n –1)/2. Using public key cryptosystem, the number 2 of keys require is just 2n (one public key and one private for each user).

(b) One of the most important requirements in digital signatures is non-repudiation—the signer cannot deny that a signature is produced by him/her. Thus, we need a “secret” that is bound to and only to each user. Using symmetric key cryptosystem, a secret key is known to at least two users and, therefore, a digital signature produced with a secret key cannot be bound to a unique user.


(c) The problem is that a message can be easily transformed into an entirely different message with the same digest, by just re-arranging the characters or words. For example, “car” and “arc” have the same digest.

Communication networks design using graph problem

Problem:

In addition to finding shortest paths, sometimes we are also interested in finding the set of links connecting all the nodes with the minimum cost. A real life application of this idea is in the design of communication networks. Here, the nodes of the graph represent sites and the links represent the communication connections between sites. The cost of each connection could be the communication delay. Using the following graph as an example, can you design an algorithm similar to the Dijkstra’s algorithm in solving this problem?

Follow-Up:

To solve this problem using a greedy method, we can use the Kruskal’s algorithm, outlined below.

1. Sort all links in ascending order of costs
2. Start with an empty set of links, so that all nodes are disconnected (isolated)
3. Add the lowest cost link to the set to connect a disconnected node without creating a cycle; this link is not to be considered again
4. Repeat Step (3) until the set has n - 1 links

Further Inquiry:

(a) What is the estimated running time of the above algorithm?
(b) If there are links with negative costs, would this greedy method still work?

Skype system

Comment:

Why the SuperNode in a Skype network can boost the speed of the system?

Follow-up:

Sorry for causing this confusion!

In fact, each SuperNode is mainly responsible for routing calls for other users. In the routing mechanism, sometimes a SuperNode needs to serve as an agent on behalf of another Skype user who is behind a firewall or an NAT router (very commonly used at home or in an organization). Thus, each SuperNode is really helping to enhance the “reachability” of the Skype network, rather than the speed of the system.

Comment:

How can the Skype system enable “computer-to-telephone” calls?

Follow-up:

Good question.

Specifically, there are some Skype servers (not shown in the diagram in the presentation slide) that have connections to some PSTN (Public Switched Telephone Network) gateways. Thus, through such servers we can route our VoIP (voice over IP) calls to reach a landline telephone or a cell phone. As this directly consumes resources in the Skype network (owned and operated by the Skype company), the caller and the callee both need to pay some money to make this happen.

Parallel processing: Amdahl's Law, speed-up and overhead

Comment:

The “speed-up” formula (i.e., Amdahl’s Law) still a bit confusing?

Follow-up:

First of all, it is important to understand that this formula assumes that a program (or a task, or a job) can be divided into two parts, i.e., sequential part (must be carried out by one single processor only), and parallel part. Most importantly, one key component in the assumption is that the parallel part can be perfectly divided into totally independent (i.e., no communication is required) pieces for different processors to work on.

Consequently, given n processors, we can perfectly speed up the computation of the parallel part by n times. Using the terminology in the presentation slide, the Speedup of enhancement is n. Thus, if the original total execution time of the program using one processor is T and the fraction of sequential part is x, then the new total execution time is:

The first term in the above expression is the time required to execute the sequential part. The second term is the time required to execute the parallel part, using n processors simultaneously. Finally, speed-up, which is defined as the ratio of original time to the new time, is given by:

We can see that perfect speed-up, i.e., n , is achievable only when x = 0 . which means that the whole program is perfectly parallelizable into totally independent pieces. This is a situation not likely to happen in a typical computer program (or any daily life task, for that matter).

Comment:

Is the parallel processing formula (speed-up) really works?

As we assume the processor count tends to infinity, the time for communication should also be in a large scale. Should we consider the running time to be larger? Or the formula just neglects the factor of communication time between processors?

Follow-up:

This is another excellent observation. As mentioned in the Follow-Up to the comment above, in deriving the formula, we assume that the parallel part can be divided up perfectly, without any communication. In a real-life parallel program, of course there will be communications. Thus, in deriving a speed-up formula for such a program, we might need an additional term for the total execution time:

In the above expression, the third term denotes the communication overhead time introduced by parallelization, which grows as (n x n) with a multiplicative constant c. This is not an “artificial” example but really represents some real-life communication overhead that you can find in many practical parallel programs.

What new conclusions can you draw from this new expression?

Comment:

Still quite confused about Slide 14?

Follow-up:

Slide 14 illustrates the need for extra communication overhead when we perform parallel processing. Specifically, in the Main Memory, there is a variable u, which has a value of 5. This variable is needed for some parallel computations to be carried out by three different processors as shown. Now, each processor has to read this variable from the Main Memory into its own memory in order to perform the computation. The problem here is that after P1 and P3 have read the variable u, P3 subsequently modifies its value (from 5 to 7), making different copies of u having different values (an inconsistent situation).

Obviously, inconsistency in shared data variables is unacceptable because it will lead to mistakes. Thus, to rectify the inconsistency, some extra communication has to be carried out. For instance, after P3 modifies u, it has to immediately inform every processor that is currently using u (i.e., having u in its own memory).

Can you think of some other way to handle this inconsistent situation?

Dijkstra's shortest path problem

Problem:

We learn about the Dijkstra’s shortest path algorithm in class. Try to apply it to the following graph.

What is the shortest path between s and b?

Follow-Up:

Using Dijkstra and starting from s, the shortest path found is s-a-b. Yet we can easily see that the shortest path should be s-a-c-b. Thus, we can see that greedy method does not always work. Here, Dijkstra is defeated by the existence of links with negative costs.

However, as some of you discovered during the tutorial, the correct shortest path can be found by starting the Dijkstra work from the destination, i.e., b. Please try this yourself.

Indeed, in real-life usage (e.g., in software systems such as MapQuest), a bi-directional approach is used, i.e., the Dijkstra work is done concurrently from both the starting point and the destination. Conflicts are resolved on the way to construct the final shortest path.

Further Inquiry:

Consider that the link costs are multiplied together (e.g., when the links are associated with probabilities) in a path, would Dijkstra still work?