Data Structures and Algorithms

These flashcards cover key vocabulary terms and concepts related to data structures and algorithms as outlined in the lecture.

Data structure

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

Linear or non-linear

Describes whether data items are arranged in sequence (linear) or unordered (non-linear).

Homogeneous or non-homogeneous

Describes whether all data items are of the same type (homogeneous) or of various types (non-homogeneous).

Static or dynamic

Describes whether a data structure has fixed sizes and memory locations (static) or can change size and structure (dynamic).

Array

A data structure that stores a collection of items at adjoining memory locations, typically of the same type.

Stack

A data structure that stores items in a linear order that can be last in first out (LIFO) or first in first out (FIFO).

Queue

A data structure that stores items in a first in first out order.

Linked list

A data structure that stores a collection of items in linear order, where each item contains a reference to the next item.

Tree

A hierarchical data structure where each node is linked to other nodes and can have multiple sub-values.

Graph

A non-linear data structure made up of nodes (vertices) connected by edges.

Trie

A data structure that organizes strings as data items in a visual graph.

Hash table

A data structure that stores items in an associative array, plotting keys to values using a hash function.

Algorithm

A finite sequence of clear, unambiguous instructions that terminates after executing a finite number of steps.

Time Complexity

The amount of computer time an algorithm needs to run to completion as a function of the size of a problem.

Space Complexity

The amount of memory a program needs to run to completion, including instruction and data space.

Algorithm Design Goals

The three basic goals: save Time, save Space, and save Face.

Complexity of Algorithms

A function that describes the running time and/or storage space requirement of an algorithm based on input size.

Worst Case

The maximum value of the complexity function for any possible input.

Best Case

The minimum possible value of the complexity function.

Average Case

The expected value of the complexity function.