CC4 Chapter 1

These flashcards cover the fundamental concepts of Data Structures and Algorithms, including design goals, algorithm definitions, complexity analysis, classifications, and implementation strategies.

The algorithm design goal that ensures the logic produces the correct output for every valid input is _________.

Correctness

The goal that an algorithm should use as little time and memory as possible is known as _________.

Efficiency

A program that continues to work properly during unexpected situations, such as invalid input or runtime errors, demonstrates _________.

Robustness

The implementation goal that makes software easy to modify or extend when requirements change is _________.

Adaptability

Code written so it can be reused in other programs or projects expresses the goal of _________.

Reusability

An algorithm is defined as a _________ sequence of instructions that can be performed with a finite amount of effort.

finite

The algorithm characteristic that requires zero or more quantities are externally supplied is _________.

Input

The algorithm characteristic that requires at least one quantity is produced is called _________.

Output

The algorithm characteristic that requires each instruction to be clear and unambiguous is _________.

Definiteness

The algorithm characteristic that ensures the process terminates after a finite number of steps for all cases is _________.

Finiteness

The characteristic of _________ states that every instruction must be basic enough to be carried out by a person using only pencil and paper.

Effectiveness

Because potential inputs are often infinite in theory, we need _________ to ensure an algorithm satisfies its specification.

correctness proofs

The space needed by a program is the sum of the _________ part (independent of input characteristics) and the _________ part.

fixed; variable

Instruction space and space for constants are part of the _________ component of space complexity.

fixed

Recursion stacks and variables whose size depends on inputs are part of the _________ component of space complexity.

variable

Physical execution time in time complexity analysis is denoted by the symbol _________.

$$TP(n)$$

The algorithm type designed to arrange items in ascending or descending order is _________.

Sorting

Algorithms for digital signal processing are known as _________.

Fast Fourier Transforms

A _________ algorithm fragments a problem into sub-problems which are solved partially and then terminated when further sub-division is impossible.

Divide-and-Conquer

A _________ algorithm chooses an immediately available best solution at each step.

Greedy

The classification where all possible solutions are explored until the end is reached and then steps are traced back is _________.

Back tracking

Flowcharts are graphic representations of algorithms usually reserved for _________ algorithms.

small and simple

In asymptotic notation, _________ represents the upper bounding function.

Big-O notation

In asymptotic notation, _________ represents the lower bounding function.

Ω Notation(omega)

The rate at which running time increases as a function of input is called the _________.

rate of growth

The _________ running time of an algorithm is an upper bound on the running time for any input.

Worst case

A _________ is a way of solving a problem in less time by using more storage space, or vice versa.

space-time tradeoff

Data types defined by the system, such as int, float, char, and bool, are called _________ data types.

Primitive

Accessing each record exactly once so that items may be processed is an operation called _________.

Traversing

Data structures like Array, Stack, Queue, and Linked List are categorized as _________.

Linear Data Structure

Data structures like Tree and Graph are categorized as _________.

Non – Linear Data Structure

Mathematical models of classes of data structures defined only by the operations that can be performed on them are _________.

Abstract Data Types (ADTs)

The practice of hiding implementational details from the user and protecting them from outside access is known as _________.

encapsulation

Proven algorithm structures that provide a general structure for algorithms but leave specific details to be added are called _________.

Design patterns