CSP Unit 6

iteration

the programming concept of using loops to repeat blocks of code

definite loop

a loop that runs a predetermined number of times

indefinite loop

a loop that runs until a condition is met

infinite loop

a loop in which the ending condition never evaluates to true.

list

ordered sequence of elements.

element

an individual value in a list that is assigned a unique index.

index

a common method for referencing the position of elements in a list or string using sequential natural numbers.

list traversal

traversal through a list means accessing every single element of a list

string concatenation

joining together two or more strings end-to-end to make a new string.

substring

part of an existing string

algorithm

a finite set of instructions that accomplish a specific task.

swap

to exchange two values

Linear search

algorithm that checks each element of a list, in order, until the desired value is found or all elements in the list have been checked. Also known as sequential search.

Efficiency

an estimation of the amount of computational resources used by an algorithm. Efficiency is typically expressed as a function of the size of the input.

Big O()

describes the performance or complexity of an algorithm. It can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.

binary search

an algorithm that starts at the middle of a sorted data set and eliminates half of the data; then repeats this process until the desired value is found or all elements have been eliminated.

problem

a general description of a task that can (or cannot) be solved algorithmically.

Efficiency

an estimation of the amount of computational resources used by an algorithm.

reasonable time

term for run time of algorithms with a polynomial efficiency or lower (constant, linear, square, cube, etc.)

unreasonable time

term for run time of algorithms with exponential or factorial efficiencies

Sequential computing

a computational model in which operations are performed in order one at a time.