Undecided Problems Homework

JavaScript isn't enabled in your browser, so this file can't be opened. Enable and reload.

AP CSP Homework for undecided problems

Email *

Record my email address with my response

What is your name? *

1 point

In proof by contradiction, what is the original assumption? *

1 point

The statement is proven true

The inverse of the statement is proven true

The statement is proven false

The inverse of the statement is proven false

Which pathway will lead to a contradiction

1 point

Yellow Path

Green Path

Neither Path

Both Paths

Clear selection

A 5 year old visits the Computer History Museum and gets excited about everything computers can do. They ask their mother, "Mom, can computers solve every problem?"
*

2 points

There are some problems a computer can't solve, no matter how much time they have.

There are some problems that current computers can't solve, but we hypothesize that more powerful computers in the near future will be able to solve them.

Computers can solve every problem, and do so in a reasonable amount of time

What will the result of this code be?

2 points

Loop Indefinitely

Halt

Clear selection

How do many programming environments avoid running indefinite loops?

3 points

With a HaltChecker

Time Out Feature

Loop Counters

Automatically terminating the program when a loop is detected

Running code in a sandbox environment

A software engineer is developing a new operating system. The operating system has to make a decision when it sees an application taking a long time to finish executing an instruction. Should the operating system force quit the application, assuming it will run forever? Or can the operating system detect that the application will finish processing, if it has a bit more time?

The engineer does some research and discovers that this is an undecidable problem.

2 points

The problem is not solvable in any cases.

The problem is solvable, but will take an unreasonable amount of time.

The problem may be solvable in some cases, but no algorithm will solve the problem in all cases.

The problem can be solved much more quickly with the use of a heuristic that comes up with an approximate solution.

What is an undecidable problem? A decidable problem? *

2 points

Describe the implications of undecidable problems in security-related tasks, such as virus detection in software. Discuss the challenges and limitations imposed by undecidable problems in developing foolproof security measures.

3 points

A security engineer is developing antivirus software that detects when downloaded programs look similar to known viruses. They would like the software to be able to detect viruses that it's never seen before, by predicting whether or not a program will ever execute malicious code.

After a bit of research, the engineer realizes that virus detection is an undecidable problem.

2 points

The engineer can come up with an algorithm that can always correctly predict whether a program will execute malicious code, but it will take an unreasonable amount of time to run.

The problem is impossible. The engineer will never come up with an algorithm that will output a correct prediction for any downloaded files.

There are algorithms that can correctly predict whether a program will execute malicious code, but the engineer can not predict how long those algorithms will take to run.

The engineer might come up with an algorithm that correctly predicts the execution of malicious code in some cases, but the algorithm will not be correct all of the time.

A software engineer at a mapping company is tasked with coming up with an algorithm to solve a new problem. The engineer is nervous about whether they'll be able to solve it. What is least likely to occur?
*

1 point

The engineer may discover that the problem is an undecidable problem, so they will not be able to solve it for all inputs.

The engineer may discover that the problem is solvable, but requires an unreasonable amount of time to find an optimal solution.

The engineer may discover that the algorithm is only solvable in a programming language that their company does not use.

The engineer may invent an algorithm that solves the problem correctly in polynomial time.

Other:

An online news website relies on in-page advertisements to make money. Their article pages have multiple slots for advertisements, and each slot can be used for a full-size ad or multiple smaller ads. Advertisers specify their size and desired display count per day.

A diagram of a webpage. Article text is shown alongside multiple advertising boxes on the page.

The news site uses a scheduling algorithm to determine which advertisements to display in each slot at each time of day. The algorithm's goal is to maximize money earned while not exceeding the display count per day, so it tries out every possible combination and picks the best one.

As the number of advertisers and articles increases, the news site realizes the scheduling algorithm is taking an unreasonable amount of time and costing them valuable server time.

What is the most promising way that they can improve the run time of the algorithm?

2 points

Rewrite the algorithm in a different programming language.

Replace the algorithm with employees that can hand-select the advertisements that give maximal profit.

Use a heuristic-based algorithm that suggests an advertisement schedule that is close to optimal

Rewrite the algorithm in fewer lines of code.

Submit

Clear form

Never submit passwords through Google Forms.

This content is neither created nor endorsed by Google. Report Abuse - Terms of Service - Privacy Policy

Forms