Font size
WorksheetsAlgorithms Study Set
Total questions: 70
Worksheet time: 59mins
Speedup is when programs run in order, one command at a time.
True
False
Sequential computing is a type of computation where many calculations are carried out simultaneously.
True
False
A computer scientist is analyzing four different algorithms used to sort a list. The table below shows the number of steps each algorithm took to sort lists of different sizes.
Based on the values in the table, which of the algorithms appear to run in reasonable time?
A
B
C
D
Which algorithm will be most useful to guess the number that someone has in their head spanning from 1-100?
Binary
Linear
If one would like to read through a large list of names and read every name on the list, which big O notation would you use?
O(nlog n)
O(nlog n)
O(n!)
O(n)
A sorted list of numbers contains 200 elements. Which of the following is closest to the maximum number of list elements that will need to be examined when performing a binary search for a particular value in the list?
8
10
2
200
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
Which of the following best describes the ability of parallel computing solutions to improve efficiency?
Any problem that can be solved sequentially can be solved using a parallel solution in approximately half the time.
Any solution can be broken down into smaller and smaller parallel portions, making the improvement in efficiency theoretically limitless as long as there are enough processors available.
The efficiency of parallel computing solutions is rarely improved over the efficiency of sequential computing solutions.
The efficiency of a solution that can be broken down into parallel portions is still limited by a sequential portion.
A company is developing a new algorithm to recommend personalized movies and TV shows to users based on their viewing history and preferences. They realize that creating a perfect recommendation algorithm that satisfies every user's preferences is practically impossible due to the vast diversity of tastes and preferences among users. Instead, they decide to implement a heuristic approach that provides satisfactory recommendations for the majority of users in a 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
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
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
I and II
II and III
I , II and III
A programmer for a weather website needs to display the proportion of days with freezing temperatures in a given month.
Their algorithm will operate on a list of temperatures for each day in the month. It must keep track of how many temperatures are below or equal to 32. Once it's done processing the list, it must display the ratio of freezing days over total days.
Which of these correctly expresses that algorithm in pseudocode?
The flow chart below visualizes an algorithm to generate the Fibonacci numbers, a famous mathematical sequence.
If the variable max is set to 5, what would be displayed as a result of executing this algorithm?
1 1 2 3 5 8
1 1 2 3 5
1 2 3 5 8
1 2 3 5
[1, 4, 7, 8, 5, 2, 9]
[1, 2, 4, 5, 7, 8, 9]
Which graph has an efficiency that is considered unreasonable?
green
yellow
orange
red
Which graph is most efficient for a large number of inputs?
green
yellow
orange
red
Why might someone use a heuristic?
some problems cannot be solved in a reasonable amount of time
some problems require multiple devices to solve
some problems are unsolvable
some problems are too difficult to be solved without a computer
Which is true about a binary search?
The data must be sorted in order to use a binary search
It has a polynomial efficiency
It cannot be completed in a reasonable time
It can only be used on a list of numbers
A computer is performing a LINEAR search on the sorted list of 11 numbers below. What is the maximum number of iterations needed to find the item?
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
(a)
Distributed computing improves the speed at which an individual computer executes a program
True
False
Distributed computing allows larger problems to be solved quicker
True
False
Which statement about parallel computing is true?
Parallel computing takes twice as long as sequential computing.
Parallel computing can only be used when the devices are on different servers.
Parallel computing takes the same time as sequential computing to complete a task.
At some point, adding parallel portions will no longer increase efficiency.
A sequential algorithm takes a total of 15 minutes to complete while a parallel version of the algorithm takes a total of 5 minutes to complete.
What is the speedup of the parallel solution?
1.5
2
3
10
Which graph has a polynomial efficiency?
green
yellow
orange
red
Which graph has a linear efficiency?
green
yellow
orange
red
What is the difference between a decision problem and an optimization problem?
decision problems are solved by just one computer, optimization problems use multiple computers
decision problems have a linear efficiency, optimization problems have an exponential efficiency
decision problems have a yes/no answer, optimization problems cannot be answered
decision problems have a yes/no answer, optimization problems look for the best solution
Which of these algorithms will move the robot along the same path as the algorithm below?
MOVE_FORWARD()
TURN_RIGHT()
MOVE_FORWARD()
TURN_RIGHT()
MOVE_FORWARD()
TURN_RIGHT()
MOVE_FORWARD()
TURN_RIGHT()
REPEAT 2 TIMES
{
MOVE_FORWARD()
MOVE_FORWARD()
TURN_RIGHT()
MOVE_FORWARD()
TURN_RIGHT()
}
What is iteration?
completing steps in order
executing a portion of an algorithm based on a given condition
repeating a portion of an algorithm
running a program on multiple devices
The time used to complete a task sequentially divided by the time to complete a task in parallel is called (a)
A (a) provides a "good enough" solution when it is impractical or impossible to find an actual solution.
A (a) search checks each element until the correct value is found.
A (a) search repeatedly cuts a sorted list in half until a desired element is found.
Instruction that use sequencing, selection, and iteration is called an (a) .
Programs are broken into small pieces, some of which are run simultaneously.
Sequential Computing
Parallel Computing
Distributed Computing
Speedup
The time used to complete a task sequentially divided by the time to complete a task in parallel
Sequential Computing
Parallel Computing
Distributed Computing
Speedup
Programs run in order, one command at a time.
Sequential Computing
Parallel Computing
Distributed Computing
Speedup
A problem for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer.
Heuristic
Undecidable Problem
Unreasonable Time
Reasonable Time
Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.
Reasonable Time
Unreasonable Time
Algorithms with a polynomial efficiency or lower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time.
Reasonable Time
Unreasonable Time
Any algorithm whose efficiency includes an 2n, 3n, 4n … is called ______________.
Problem
Polynomial
Exponential
Efficiency
Any algorithm whose efficiency includes an n2, n3, n4 … is called ___________.
Problem
Polynomial
Pseudocode
Efficiency
A measure of how many steps are needed to complete an algorithm.
Problem
Algorithm
Pseudocode
Efficiency
A general description of a task that can (or cannot) be solved with an algorithm
Problem
Algorithm
Sequencing
Iteration
What should be considered when designing an algorithm?
If there is more than one way of solving the problem
If the correct hardware is being used
If the correct software is being used
What is important to remember when designing an algorithm?
whether to use a flowchart or pseudocode
the instructions are in the correct order
that it must be easy to read
How are symbols connected together in a flowchart?
Symbols do not get connected together in a flowchart
With lines and an arrow to show the direction of flow
By numbers
Which of these is the correct symbol for a process in a flowchart?
A diamond
A rectangle
A parallelogram
What is the symbol for a decision in a flowchart?
A parallelogram
A diamond
A circle
What are the two main ways that algorithms can be designed?
Images or videos
In pseudocode or as a flowchart
By hardware or software
What does sequence mean?
To create a pattern
To do something in order
To do something randomly
To repeat something over and over again
What does selection mean?
Selection is following instructions in order.
Selection is to repeat something over and over again
Selection is when you have a choice of options
Selection is choosing the best option
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
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
The algorithm shown 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
