WorksheetsCS Principles Unit 6 Assessment
Total questions: 22
Worksheet time: 16mins
What is the third step using Binary Search to look for the number 32 in this list:
[1, 2, 3, 4, 10, 11, 16, 25, 32, 33, 45, 47, 51, 69, 75]
Compare the number 25 to the given number.
Compare the number 4 to the given number.
Compare the number 33 to the given number.
Compare the number 47 to the given number.
Which of the following is true of two algorithms designed to solve the same problem?
If two algorithms solve the same problem they must have the same efficiency
If two algorithms solve the same problem they must have different efficiency
For any given problem there is a single algorithm that can solve it with a single efficiency
It is possible for two algorithms with different efficiencies to solve the same problem
Which of the follow efficiencies would be considered unreasonable?
2^n
2n
n^2
n^20
A team of programmers is trying to determine the efficiency of a piece of code. They run the code with inputs of different sizes and also record the number of iterations through the core block of code. The data is recorded in the table below.
Based on the data provided, does this algorithm run in a reasonable or unreasonable time? Explain your answer
In which of the following situations is it most appropriate to use a heuristic solution?
The only algorithms that provide exact solutions run in linear time
The problem has been identified as undecidable
The only algorithms that provide exact solutions run in unreasonable time but exact solutions are not necessary
Two different algorithms have been identified that solve the problem in reasonable time
Problems that are undecidable and algorithms that are unreasonable both touch on the limits of the kinds of computing that a computer can accomplish. In your own words, explain the difference between undecidable problems and unreasonable time algorithms.
An algorithm was initially written sequentially. Later it was determined that a parallel solution was possible and so the algorithm rewritten. The times to run each version of the algorithm are included in the table below.
What is the speedup of this parallel solution?
2
3
20 mins
10 mins
Which of the following is true of algorithms?
Algorithms may have an infinite set of instructions
Algorithms must be expressed using a programming language
Every algorithm can be constructed using combinations of sequencing, selection, and iteration
Every problem can be solved with an algorithm
The following algorithm is followed by a person every morning when they get up from bed to go to school. Which concept does this algorithm BEST demonstrate?
Sequencing
Selection
Iteration
Execution
Which of these algorithms will move the robot along the same path as the algorithm below?
A town government is designing a new bus system and are deciding where to put the different bus stops. They want to pick the collection of locations that minimizes the distance anyone needs to walk in order to get to at least one bus stop. What term best defines the kind of problem?
A decision problem
An optimization problem
An undecidable problem
An efficiency problem
The algorithm below is used to find the largest element in a list of numbers.
By modifying one of the lines in the program it is possible to make the algorithm find the SMALLEST element. Which line would need to be modified and how?
Line 01 becomes
target <- list[2]
Line 04 becomes
IF (num < target)
Line 04 becomes
IF (num = target)
Line 01 becomes
list[0] <- target
Which of the following algorithms is the same as the following flowchart?
This graph shows the efficiencies of two different algorithms that solve the same problem. Which of the following is most efficient?
These algorithms are equally efficient
Algorithm A is more efficient than algorithm B
Algorithm B is more efficient than algorithm A
The algorithms have different efficiencies depending on the input size
A school is creating class schedules for its students. The students submit their requested courses and then a program will be designed to find the optimal schedule for all students.
The school has determined that finding the absolute best schedule cannot be solved in a reasonable time. Instead they have decided to use a simpler algorithm that produces a good but non-optimal schedule in a more reasonable amount of time.
Which principle does this decision best demonstrate?
Unreasonable algorithms may sometimes also be undecidable
Heuristics can be used to solve some problems for which no reasonable algorithm exists
Two algorithms that solve the same problem must also have the same efficiency
Approximate solutions are often identical to optimal solutions
Which of the following algorithmic efficiencies would be considered LEAST efficient?
Linear
Constant
Polynomial
Exponential
Which of the following best describes the existence of undecidable problems?
Undecidable problems are problems for which more than one algorithm solves the problem and computer scientists have not yet chosen the algorithm they believe is best
Undecidable problems are problems for which an algorithm can be written that will produce the same output for at least two possible inputs
Undecidable problems are problems for which an algorithm can be written that produces a correct output for all inputs but in an unreasonable time
An undecidable problem is a problem for which no algorithm can be constructed that always produces a correct output
A group of students writes their names and unique student ID numbers on sheets of paper. The sheets are then randomly placed in a stack.
Their teacher is looking to see if a specific ID number is included in the stack. Which of the following best describes whether their teacher should use a linear or a binary search?
The teacher could use either type of search though the linear search is likely to be faster
The teacher could use either type of search though the binary search is likely to be faster
Neither type of search will work since the data is numeric
Only the linear search will work since the data has not been sorted
A computer is performing a binary search on the sorted list of 7 numbers below. What is the maximum number of iterations needed to find the item?
[1, 5, 20, 50, 51, 80, 99]
1
3
6
7
Which of the following are benefits of parallel and distributed computing?
I. Distributed computing improves the speed at which an individual computer executes a program
II. Parallel computing scales more effectively than sequential computing
III. Distributed computing allows larger problems to be solved quicker
I only
I and II
II and III
I, II, and III
A software company used to run an algorithm sequentially on one server. As more users start using their app, the company decided to rewrite the program to be parallel. It is now run on four separate servers instead of one Thanks to the use of a parallel algorithm, the same process that used to take 40 minutes to run now only requires 20 minutes.
The company is considering purchasing additional computers to decrease the time the program runs even further. Which of the following best describes the impacts of running the parallel algorithm on an even larger number of computers
The algorithm will likely require more time since it is now being run sequentially on more computers.
The algorithm will likely require the same amount of time to run because it is processing the same amount of data
The algorithm will likely require less time to run though the improvements in efficiency will not be as significant as before.
The algorithm is unlikely to still run since parallel algorithms are not designed to scale to additional computers
A sequential algorithm is broken into three stages
Sequential Algorithm Time
Download stage: 1 minute
Sorting stage: 6 minutes
Upload stage: 1 minute
A parallel version of the algorithm completes the sorting stage in parallel leading to a new set of times
Parallel Algorithm Time
Download stage: 1 minute
Sorting stage: 2 minutes
Upload stage: 1 minute
What is the speedup of the parallel solution?
6 minutes
4 minutes
2
3
