1.1 Algorithms

1.1-1

Describe your own real-world example that requires sorting. Describe one that requires finding the shortest distance between two points.

My school awarded academic awards to students recently (and I got one!). Specifically, one needs to get the top 20% of GPA to receive the award. Therefore, the school needs to sort students by their GPA. To collect my certification, I need to move from the teaching building to the auditorium. It’s summertime so I want to minimize my walking distance outdoors. It would be nice if I could find the shortest walking path.

1.1-2

Other than speed, what other measures of efficiency might you need to consider in a real-world setting?

I would say that the effort required to develop an algorithm - in other words, human resources - is also considerable. Maybe putting dozens of experts into developing for years can optimize the speed of an algorithm for a little bit, but why not just add more machines to run the algorithm?

1.1-3

Select a data structure that you have seen, and discuss its strengths and limitations.

A linked list connects all elements in a chain, which makes it easy to insert or remove an element in the middle. However, finding an element inside the chain may require going through the whole chain, consuming significant time.

1.1-4

How are the shortest-path and traveling-salesperson problems given above similar? How are they different?

The two problems all want to minimize the total travel distances. However, the traveling-salesperson problem requires a path that backs to the starting point and travels through all points, while the shortest-path problem only focuses on minimizing the distance between merely two points. Therefore, the additional complexity makes the traveling-salesperson problem an NP-complete problem, which means there no algorithm can solve it within a reasonable time limit.

1.1-5

Suggest a real-world problem in which only the best solution will do. Then come up with one in which “approximately” the best solution is good enough.

When it involves fairness, such as score ranking, we shall design the clearest and best algorithms to prevent people from getting upset. On the other hand, many scenarios do not have the best solution. For instance, in navigation app, there might be multiple routes that have similar traveling times. But the real transportation is uncertain and chaotic, it’s hard to tell which one is the best. Fortunately, people are satisfied with the approximately best routes.

1.1-6

Describe a real-world problem in which sometimes the entire input is available before you need to solve the problem, but other times the input is not entirely available in advance and arrives over time.

The speech-to-text problem is a good example. Sometimes, the speech may be recorded in advance, such as a video or lecture. In this case, therefore, the entire input is provided before solving the problem. Sometimes, the speech may come from the user in real-time, for example, you are speaking to Siri. In this case, the algorithm solves the problem as the input arrives gradually.