Question

Solvability

Think about real-world examples of problems whose solutions do—and do not—scale well. Additionally, think about a problem that is so complex that there is no computational solution to feasibly solve the problem in a reasonable amount of time.

Complete a short written response to the following questions:

1. Identify two real-world examples of problems whose solutions do scale well.

2. Identify two real-world examples of problems whose solutions do not scale well.

3. Identify one problem that is so complex that there is no computational solution to feasibly solve the problem in a reasonable amount of time. NOTE: Wikipedia’s list of NP-complete problems (Links to an external site.) outlines many problems that are currently infeasible to solve computationally. As a general rule of thumb, any problem that can be solved by a human without a computer scales well. These include searching a sorted list or arithmetic calculations. Problems that are infeasible without a computer tend to scale poorly with input. These include sorting (think of massive amounts of database records) or, even more so, enumerating the next n moves in a Checkers game.

Submit Your written response to the questions above. Response in plain English

Answer 1

1. real-world examples of problems whose solutions do scale well.

a) Finding the largest/smallest element in a list of data.

Used when trying to find from a table the person that has the largest attribute, e.g. age, salary, etc. or finding the highest score on a test. This is scalable as it can be done by both machine and humans in same fashion according to problem size.

b) solving simple arithmetic equations.

Solving arithmetic equations can be an easily scaled problem , depending on variables and number of operations in the equations corresponding to daily life situations like counting , adding, finding mean,etc.

2. real-world examples of problems which don't scale well.

a) multiplying matrices for various applications, like solving equations, etc.

b) sorting a large list of numbers does not scale well as the steps required increases as square or more by the increase in size.

3. An example for a problem which is not computationally feasible would be to find the best or optimal way to play chess. It is possible to do a good move but to tell the best move it would be computationally not feasible.