7. Algorithms

Question 1

Algorithm

Answer 1

• Sequence of steps that solves a problem
• Sequence of steps for accomplishing a task
• Generating correct output for any valid input values
• Sequence of steps to solve a computational problem or perform a calculation

Question 2

Algorithm Time Efficiency

Answer 2

• The number of calculations required to solve a problem
• Typically measured by the algorithm’s computational complexity

Question 3

Computational Problem

Answer 3

• Specifies an input
• A question about the input that can be answered using a computer
• The desired output
• (Input/Question/Output)
• Describes concept of an algorithm can be written in plain English

Question 4

NP-complete Problems

Answer 4

• A set of problems for which no known efficient algorithm exists
• No efficient algorithm has been found to solve an NP-complete problem.
• No one has proven that an efficient algorithm to solve an NP-complete problem is impossible.
• If an efficient algorithm exists for one NP-complete problem, then all NP-complete problems can be solved efficiently.
• By knowing a problem is NP-complete, instead of trying to find an efficient algorithm to solve the problem, a programmer can focus on finding an algorithm to efficiently find a good, but non-optimal, solution.

Question 5

An algorithm with a polynomial runtime is considered efficient.

Answer 5

An efficient algorithm is generally one whose runtime increases no more than polynomially with respective to the input size. In contrast, an algorithm with an exponential runtime is not efficient.

Question 6

Computational Complexity

Answer 6

• The amount of resources used by the algorithm.
• Allows different algorithms to be compared.
• Complexity analysis is used to identify and avoid using algorithms with long runtimes or high memory usage.

Question 7

Runtime Complexity

Answer 7

• A function, T(N), that represents the number of constant time operations performed by the algorithm on an input of size N.

Question 8

Best Case

Answer 8

The scenario where the algorithm does the minimum possible number of operations

Question 9

Worst Case

Answer 9

The scenario where the algorithm does the maximum possible number of operations.

Question 10

A best case or worst case scenario describes contents of the algorithm’s input data only. The input data size must remain a variable, N. Otherwise, the overwhelming majority of algorithms would have a best case of N=0, since no input data would be processed. In both theory and practice, saying “the best case is when the algorithm doesn’t process any data” is not useful. Complexity analysis always treats the input data size as a variable.

Question 11

Space Complexity

Answer 11

• Function, S(N), that represents the number of fixed-size memory units used by the algorithm for an input of size N.
• Ex: The space complexity of an algorithm that duplicates a list of numbers is S(N) = 2N + k, where k is a constant representing memory used for things like the loop counter and list pointers.

Question 12

Linear Search

Answer 12

• Search algorithm that starts from the beginning of a list, and checks each element until the search key is found or the end of the list is reached.
• May require searching all list elements, which can lead to long runtimes

Question 13

Runtime

Answer 13

• The time the algorithm takes to execute.
• If each comparison takes 1 µs (1 microsecond), a linear search algorithm’s runtime is up to 1 s to search a list with 1,000,000 elements, 10 s for 10,000,000 elements, and so on.
• Ex: Searching Amazon’s online store, which has more than 200 million items, could require more than 3 minutes.

Question 14

Binary Search

Answer 14

• Faster algorithm for searching a list if the list’s elements are sorted and directly accessible
• Binary search first checks the middle element of the list.
• If the search key is found, the algorithm returns the matching location.
• If the search key is not found, the algorithm repeats the search on the remaining left sublist (if the search key was less than the middle element) or the remaining right sublist (if the search key was greater than the middle element).

Question 15

Sorting

Answer 15

• Process of converting a list of elements into ascending/descending order.
• The challenge is that a program can’t “see” the entire list to know where to move an element.
• Instead, a program is limited to simpler steps, typically observing or swapping just two elements at a time. So sorting just by swapping values is an important part of sorting algorithms.

Question 16

Heuristic

Answer 16

• A technique that willingly accepts a non-optimal or less accurate solution in order to improve execution speed.

Question 17

Heuristic Algorithm

Answer 17

• Algorithm that quickly determines a near optimal or approximate solution