Data Structures and Algorithms Overview

These flashcards provide key vocabulary and definitions related to data structures and algorithms.

Data Structure

A specialized format for organizing, processing, retrieving, and storing data.

Algorithm

A finite sequence of instructions that produces an output based on given inputs.

Linear Data Structure

A structure where data items are arranged in a sequential manner, like arrays.

Non-linear Data Structure

A structure where data items are not arranged in a sequential manner, such as graphs.

Homogeneous Data Structure

A structure where all data items are of the same type.

Static Data Structure

A data structure with fixed sizes and memory locations at compile time.

Dynamic Data Structure

A data structure that can change in size and structure during execution.

Array

A collection of items stored at contiguous memory locations, allowing easy access.

Stack

A linear collection of items where the last added item is the first to be removed (LIFO).

Queue

A linear collection of items where the first added item is the first to be removed (FIFO).

Linked List

A collection of items where each item points to the next, forming a sequence.

Tree

A hierarchical data structure where nodes are linked in a parent-child relationship.

Graph

A non-linear structure consisting of nodes (vertices) connected by edges.

Trie

A data structure that stores strings in a visual tree-like format.

Hash Table

An associative array that maps keys to values using a hash function.

Time Complexity

The amount of computer time needed by an algorithm as a function of problem size.

Space Complexity

The amount of memory needed by a program to run to completion.

Best Case Complexity

The minimum possible running time of an algorithm for any input.

Worst Case Complexity

The maximum running time of an algorithm for any possible input.

Effectiveness

every instruction must be sufficiently basic that it can in principle be carried out by a person using only pencil and paper. It is not enough that each operation be definite, but it must also be feasible.

Finiteness

if we trace out the instructions of an algorithm, then for all cases the algorithm will terminate after a finite number of steps.  

Definiteness

each instruction must be clear and unambiguous

Input

there are zero or more quantities, which are externally supplied.

output

at least one quantity is produced

Operation of heap tree

Insertion

Deletion

Merging

Instruction space

the space needed to store the compiled version of the program instructions.

Data space

space needed to store all constant and variable values. Data space has two components:

Average Case

The expected value of f(n).

Try to save Time

Try to save Space

Try to save Face

Algorithm Design Goals The three basic design goals that one should strive for in a program are:

Performance of a program

the amount of computer memory and time needed to run a program.