CSS100 - CHAPTER 3

searching

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

sorting

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

selection sort algorithm

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

order of magnitude (n^2)

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

shuffle-left algorithm

It is space efficient because it only requires four memory locations to store the quantities n, legit, left, and right in addition to the memory required to store the list itself.

copy-over algorithm

It scans the list from left to right, copying every legitimate (nonzero) value into a new list that it creates. After this algorithm is finished, the original list still exists, but so does a new list that contains only nonzero values.

copy-over algorithm

The best case for this algorithm occurs if all elements are 0

The worst case occurs if there are no 0 values in the list.

shuffle-left algorithm

The best case occurs when the list has no 0 values because no copying is required.

The worst case occurs when the list has all 0 values.

converging-pointers algorithm

The best case for this algorithm is a list containing no 0 elements.

The worst case is a list of all 0 entries.

binary search algorithm

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

polynomially bounded

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

exponential algorithm

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

intractable

A problem for which no polynomially bounded solution exists

approximation algorithms

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

bubble sort

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

smart bubble sort

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

mergesort

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

benchmarking

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