Week 2 - Unit 3

Question 1

An algorithm’s careful use of time and space resources

Answer 1

efficiency

Question 2

Running a program on many data sets to be sure its performance falls within required limits; timing the same algorithm on two different machines

Answer 2

Benchmarking

Question 3

The study of the efficiency of algorithms

Answer 3

Analysis of algorithms

Question 4

An algorithm that searches for a target value in a random list by checking each list item in turn

Answer 4

sequential search

Question 5

The efficiency classification of an algorithm whose work varies as a constant times the input size n

Answer 5

order of magnitude n

Question 6

The task of finding a specific value in a list of values, or deciding it is not there

Answer 6

searching

Question 7

The task of putting a list of values into numeric or alphabetical order

Answer 7

sorting

Question 8

A sorting algorithm that keeps moving larger items toward the back of the list

Answer 8

Selection Sort

Question 9

The efficiency classification of an algorithm whose work varies as a constant times the square of the input size n

Answer 9

Order of magnitude n^2

Question 10

floating-point operations per second

Answer 10

flops

Question 11

An algorithm that searches for a target value in a sorted list by checking at the midpoint and then repeatedly cutting the search section in half

Answer 11

binary search

Question 12

The efficiency classification of an algorithm whose work varies as a constant times log(n)

Answer 12

Order of magnitude log(n)

Question 13

An algorithm that does less work than some polynomial expression of the input size n

Answer 13

polynomial bounded

Question 14

An algorithm whose work varies as some constant to the power of the input size n

Answer 14

exponential algorithm

Question 15

A problem for which no polynomial bounded solution exists

Answer 15

intractable

Question 16

An algorithm that doesn’t give the exact answer to a problem, but provides a close approximation to a solution

Answer 16

approximation algorithm

Question 17

A sorting algorithm that makes multiple passes through the list from front to back, each time exchanging pairs of entries that are out of order

Answer 17

Bubble sort

Question 18

A variation of the bubble sort that stops when no exchanges occur on a given pass

Answer 18

smart bubble sort

Question 19

A sorting algorithm that breaks the list to be sorted into smaller and smaller lists and then assembles the smaller sorted lists back into larger and larger sorted lists

Answer 19

Mergesort

Question 20

A variation of the sequential search that requires a sorted list and stops once it has passed the place where the target could occur

Answer 20

short sequential search