Deck 3: The Efficiency of Algorithms

ملء الشاشة (f)
exit full mode
سؤال
Sequential search is an order-n algorithm in the average case.
استخدم زر المسافة أو
up arrow
down arrow
لقلب البطاقة.
سؤال
No one has yet found a solution algorithm that works in polynomial time, but neither has anyone proved that such an algorithm does not exist.
سؤال
The selection sort algorithm can recognize whether or not the list is already sorted at the beginning.
سؤال
The study of the efficiency of algorithms is called the ____ of algorithms.

A) design
B) analysis
C) implementation
D) testing
سؤال
If we were to run the sequential search algorithm many times, with random input values occurring at various places in the list, we would find the average number of comparisons done to be approximately n/2.
سؤال
First and foremost, we expect elegance from our algorithms._________________________
سؤال
With sequential search, the bigger the list of items, the more work that must be done to search it._________________________
سؤال
In the sequential search algorithm, the worst case occurs when the value being searched for is the first value in the list._________________________
سؤال
In the sequential search algorithm, the minimum amount of work is done if the value being searched for is the ____ value in the list.

A) first
B) second
C) middle
D) last
سؤال
A collection of nodes and connecting edges is called a(n) vector._________________________
سؤال
The properties that make better algorithms are very similar to the properties we look for when purchasing a car.
سؤال
____ involves the fixing of errors that are uncovered through repeated usage with different input values.

A) Program maintenance
B) Recycling
C) Data cleanup
D) Garbage collection
سؤال
If an Θ(n2) algorithm and an Θ(n) algorithm exist for the same task, then for large enough n, the Θ(n2) algorithm does more work and takes longer to execute, regardless of the constant factors for peripheral work.
سؤال
The sequential search and selection sort algorithms are different methods to get the same thing done.
سؤال
The shuffle-left algorithm is not space-efficient._________________________
سؤال
____ are useful for rating one machine against another and for rating how sensitive a particular algorithm is with respect to variations in input on one particular machine.

A) Time trials
B) Benchmarks
C) Comparison times
D) Intensive tests
سؤال
The time an algorithm takes on a particular machine is the best way for comparing two algorithms that do the same task.
سؤال
Given a sorted list, the sequential search algorithm is more efficient than the binary search.
سؤال
____ is the algorithmic equivalence of style.

A) Efficiency
B) Elegance
C) Aesthetics
D) Complexity
سؤال
Binary search uses significantly more space than sequential search.
سؤال
Sequential search is a(n) ____ algorithm in the worst case.

A) Θ(1)
B) Θ(n)
C) Θ(2n)
D) Θ(n2)
سؤال
The worst case in binary search occurs ____.

A) when the object to be searched is in the middle of the list
B) when the object to be searched is at the end of the list
C) when the object to be searched is at the beginning of the list
D) when the object to be searched is not in the list
سؤال
The ____ sort algorithm performs the task of sorting a list by growing a sorted subsection of the list from the back to the front.

A) selection
B) sequential
C) shuffle-left
D) binary
سؤال
The copy-over algorithm is ____ in time efficiency in the worst case.

A) Θ(1)
B) Θ(n)
C) Θ(2n)
D) Θ(n2)
سؤال
An ____ algorithm is called an exponential algorithm.

A) Θ(lg n)
B) Θ(n)
C) Θ(n2)
D) Θ(2n)
سؤال
Part of the job of program ____ is to make clear any assumptions or restrictions about the input size the program was designed to handle.

A) design
B) implementation
C) documentation
D) maintenance
سؤال
The converging-pointers algorithm is Θ(n) in the ____________________ case.
سؤال
In the sequential search algorithm, the worst case occurs when the value being searched for is the ____ value in the list.

A) first
B) second
C) middle
D) last
سؤال
Binary search does ____ comparisons in the worst case.

A) Θ(1)
B) Θ(lg n)
C) Θ(n)
D) Θ(n2)
سؤال
The shuffle-left algorithm is a(n) ____ algorithm in the worst case.

A) Θ(1)
B) Θ(n)
C) Θ(2n)
D) Θ(n2)
سؤال
____________________ is the term to describe an algorithm's careful use of resources.
سؤال
A(n) ____________________ is a path through a graph that begins and ends at the same node and goes through all other nodes exactly once.
سؤال
The ____ case of an algorithm requires the least work.

A) best
B) worst
C) smallest
D) largest
سؤال
____________________ problems are solvable, but the solution algorithms all require so much work as to be virtually useless.
سؤال
Θ(lg n), Θ(n) and Θ(n2) are ____ in the amount of work they do as n increases.

A) restricted
B) useful
C) polynomially bounded
D) exponential
سؤال
Problems for which no known polynomial solution algorithm exists are sometimes approached via ____ algorithms.

A) alternative
B) intractable
C) polynomial
D) approximation
سؤال
The number of comparisons done by the selection sort algorithm does not grow at the same rate as the problem size n, instead it grows at approximately the ____________________ of that rate.
سؤال
Placing a list of items into alphabetical or numerical order is called ____.

A) simplifying
B) searching
C) sorting
D) pattern matching
سؤال
Selection sort is a(n) ____ algorithm in all cases.

A) Θ(1)
B) Θ(n)
C) Θ(2n)
D) Θ(n2)
سؤال
A surprising number of problems fall into the "____" category.

A) suspected intractable
B) approximation algorithm
C) bin-packing
D) declared intractable
سؤال
If an algorithm is more time efficient and less space efficient, what is this called?
سؤال
Discuss at length the measurement of the time and space consumed by an algorithm in order to determine its efficiency.
سؤال
Explain the sentence: The selection sort algorithm not only does comparisons; it also does exchanges.
سؤال
How do you approach problems for which no known polynomial solution algorithm exists?
سؤال
Explain the term "brute force" as it applies to algorithms.
سؤال
Given the data cleanup problem described in the text, write the pseudocode for the converging-pointers algorithm for data cleanup.
سؤال
What is the definition of order of magnitude n?
سؤال
Discuss at length both the best and worst case of the pattern-matching algorithm.
سؤال
Discuss at length the "people aspect" of the practical considerations for the development of algorithms.Include the concepts of program maintenance and ease of understanding in your response.
سؤال
What is the logarithm of n to the base 2?
فتح الحزمة
قم بالتسجيل لفتح البطاقات في هذه المجموعة!
Unlock Deck
Unlock Deck
1/50
auto play flashcards
العب
simple tutorial
ملء الشاشة (f)
exit full mode
Deck 3: The Efficiency of Algorithms
1
Sequential search is an order-n algorithm in the average case.
True
2
No one has yet found a solution algorithm that works in polynomial time, but neither has anyone proved that such an algorithm does not exist.
True
3
The selection sort algorithm can recognize whether or not the list is already sorted at the beginning.
False
4
The study of the efficiency of algorithms is called the ____ of algorithms.

A) design
B) analysis
C) implementation
D) testing
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
5
If we were to run the sequential search algorithm many times, with random input values occurring at various places in the list, we would find the average number of comparisons done to be approximately n/2.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
6
First and foremost, we expect elegance from our algorithms._________________________
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
7
With sequential search, the bigger the list of items, the more work that must be done to search it._________________________
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
8
In the sequential search algorithm, the worst case occurs when the value being searched for is the first value in the list._________________________
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
9
In the sequential search algorithm, the minimum amount of work is done if the value being searched for is the ____ value in the list.

A) first
B) second
C) middle
D) last
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
10
A collection of nodes and connecting edges is called a(n) vector._________________________
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
11
The properties that make better algorithms are very similar to the properties we look for when purchasing a car.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
12
____ involves the fixing of errors that are uncovered through repeated usage with different input values.

A) Program maintenance
B) Recycling
C) Data cleanup
D) Garbage collection
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
13
If an Θ(n2) algorithm and an Θ(n) algorithm exist for the same task, then for large enough n, the Θ(n2) algorithm does more work and takes longer to execute, regardless of the constant factors for peripheral work.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
14
The sequential search and selection sort algorithms are different methods to get the same thing done.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
15
The shuffle-left algorithm is not space-efficient._________________________
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
16
____ are useful for rating one machine against another and for rating how sensitive a particular algorithm is with respect to variations in input on one particular machine.

A) Time trials
B) Benchmarks
C) Comparison times
D) Intensive tests
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
17
The time an algorithm takes on a particular machine is the best way for comparing two algorithms that do the same task.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
18
Given a sorted list, the sequential search algorithm is more efficient than the binary search.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
19
____ is the algorithmic equivalence of style.

A) Efficiency
B) Elegance
C) Aesthetics
D) Complexity
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
20
Binary search uses significantly more space than sequential search.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
21
Sequential search is a(n) ____ algorithm in the worst case.

A) Θ(1)
B) Θ(n)
C) Θ(2n)
D) Θ(n2)
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
22
The worst case in binary search occurs ____.

A) when the object to be searched is in the middle of the list
B) when the object to be searched is at the end of the list
C) when the object to be searched is at the beginning of the list
D) when the object to be searched is not in the list
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
23
The ____ sort algorithm performs the task of sorting a list by growing a sorted subsection of the list from the back to the front.

A) selection
B) sequential
C) shuffle-left
D) binary
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
24
The copy-over algorithm is ____ in time efficiency in the worst case.

A) Θ(1)
B) Θ(n)
C) Θ(2n)
D) Θ(n2)
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
25
An ____ algorithm is called an exponential algorithm.

A) Θ(lg n)
B) Θ(n)
C) Θ(n2)
D) Θ(2n)
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
26
Part of the job of program ____ is to make clear any assumptions or restrictions about the input size the program was designed to handle.

A) design
B) implementation
C) documentation
D) maintenance
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
27
The converging-pointers algorithm is Θ(n) in the ____________________ case.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
28
In the sequential search algorithm, the worst case occurs when the value being searched for is the ____ value in the list.

A) first
B) second
C) middle
D) last
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
29
Binary search does ____ comparisons in the worst case.

A) Θ(1)
B) Θ(lg n)
C) Θ(n)
D) Θ(n2)
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
30
The shuffle-left algorithm is a(n) ____ algorithm in the worst case.

A) Θ(1)
B) Θ(n)
C) Θ(2n)
D) Θ(n2)
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
31
____________________ is the term to describe an algorithm's careful use of resources.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
32
A(n) ____________________ is a path through a graph that begins and ends at the same node and goes through all other nodes exactly once.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
33
The ____ case of an algorithm requires the least work.

A) best
B) worst
C) smallest
D) largest
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
34
____________________ problems are solvable, but the solution algorithms all require so much work as to be virtually useless.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
35
Θ(lg n), Θ(n) and Θ(n2) are ____ in the amount of work they do as n increases.

A) restricted
B) useful
C) polynomially bounded
D) exponential
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
36
Problems for which no known polynomial solution algorithm exists are sometimes approached via ____ algorithms.

A) alternative
B) intractable
C) polynomial
D) approximation
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
37
The number of comparisons done by the selection sort algorithm does not grow at the same rate as the problem size n, instead it grows at approximately the ____________________ of that rate.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
38
Placing a list of items into alphabetical or numerical order is called ____.

A) simplifying
B) searching
C) sorting
D) pattern matching
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
39
Selection sort is a(n) ____ algorithm in all cases.

A) Θ(1)
B) Θ(n)
C) Θ(2n)
D) Θ(n2)
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
40
A surprising number of problems fall into the "____" category.

A) suspected intractable
B) approximation algorithm
C) bin-packing
D) declared intractable
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
41
If an algorithm is more time efficient and less space efficient, what is this called?
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
42
Discuss at length the measurement of the time and space consumed by an algorithm in order to determine its efficiency.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
43
Explain the sentence: The selection sort algorithm not only does comparisons; it also does exchanges.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
44
How do you approach problems for which no known polynomial solution algorithm exists?
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
45
Explain the term "brute force" as it applies to algorithms.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
46
Given the data cleanup problem described in the text, write the pseudocode for the converging-pointers algorithm for data cleanup.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
47
What is the definition of order of magnitude n?
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
48
Discuss at length both the best and worst case of the pattern-matching algorithm.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
49
Discuss at length the "people aspect" of the practical considerations for the development of algorithms.Include the concepts of program maintenance and ease of understanding in your response.
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
50
What is the logarithm of n to the base 2?
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.
فتح الحزمة
k this deck
locked card icon
فتح الحزمة
افتح القفل للوصول البطاقات البالغ عددها 50 في هذه المجموعة.