Data Structures and Algorithms Lecture Practice Flashcards

Comprehensive practice flashcards covering basic data structures, search and sort algorithms, complexity analysis, and advanced tree and graph concepts as outlined in the SIMATS School of Engineering curriculum.

Data

Raw facts, figures, or information typically in the form of numbers, text, or multimedia.

Data Object

In computer science and programming, an instance of a data structure used for organizing and storing data efficiently.

Abstract Data Type [ADT]

A type for objects with a well-defined interface that consists of a set of values and operations while hiding implementation details.

Data Structure

A way of organizing and storing data in a computer that defines the relationship between the data and the operations performed on it.

Linear Data Structure

A structure where data elements are arranged sequentially or linearly, such as stacks, arrays, queues, and linked lists.

Non-linear Data Structure

A structure where data elements are not arranged sequentially or linearly, such as trees and graphs, utilizing computer memory efficiently.

Algorithm

A set of steps used to process an input to obtain an expected output.

Time Complexity

A measure of the amount of time an algorithm takes to complete as a function of the input size, commonly expressed using Big O notation, such as $O(f(n))$.

Space Complexity

A measure of the amount of memory an algorithm uses relative to the input size, including program space and data space.

Primitive Data Structures

Basic data types that classify how data is stored, such as Integer, Float, Character, and Boolean.

Non-Primitive Data Structures

Complex data structures constructed using primitive data types, including arrays, stacks, and linked lists.

Recursion

A programming concept where a function calls itself in its own definition to solve a problem.

Linear Search

A sequential search algorithm that traverses an array from the start until the target element is found; applicable to unsorted lists.

Binary Search

An efficient search algorithm for sorted arrays that uses the Divide and Conquer method by comparing the target to the middle element ($mid = \frac{low + high}{2}$).

Singly Linked List (SLL)

A linear data structure consisting of a collection of nodes where each node contains a data field and a single address field pointing to the next node.

Doubly Linked List (DLL)

A collection of nodes connected in two directions where each node contains a data field and two addresses (previous and next node).

Stack

A linear Abstract Data Type (ADT) that follows the Last In First Out ($LIFO$) principle, where all insertions and deletions occur at the 'Top' end.

Infix Notation

An arithmetic notation where the operator appears between two operands, such as $(op1 \text{ operator } op2)$ or $a + b$.

Prefix Notation

Also known as Polish Notation, it is an arithmetic notation where the operator appears before the operands, such as $+ab$.

Postfix Notation

Also known as Reverse Polish Notation, it is an arithmetic notation where the operator appears after the operands, such as $ab+$.

Queue

A linear data structure following the First In First Out ($FIFO$) principle, with insertion at the 'Rear' (Enqueue) and deletion at the 'Front' (Dequeue).

Circular Queue

A queue where the last node points back to the first node, often referred to as a 'Ring Buffer.'

Priority Queue

A queue where elements are assigned a priority and higher priority elements are processed before lower priority ones.

Binary Tree

A non-linear data structure where each node can have at most two children ($\text{Degree Max} = 2$).

Binary Search Tree (BST)

A specific binary tree where for every node, the left subtree contains values less than the root and the right subtree contains values greater than the root.

AVL Tree

A balanced search tree named after Adelson-Valskii and Landis where the Balance Factor (Height of Left Subtree minus Height of Right Subtree) is $-1$, $0$, or $1$.

TRIE

A special kind of tree used to store dictionaries and strings where nodes with common prefixes share ancestors.

B-Tree

A self-balancing search tree used to reduce the number of disk accesses; an order $m$ B-Tree can have $m$ children and $m-1$ key values.

Red-Black Tree

A Binary Search Tree where every node is colored either red or black, with specific properties to maintain balance during insertions.

Splay Tree

A self-adjusting binary search tree where every operation rearranges the tree to place the accessed element at the root.

Hashing

An implementation of hash tables mapping keys into table indices using hash functions to manage data storage and retrieval.

Collision

A situation in hashing when a hash function returns the same hash key or index for more than one record.

Separate Chaining

A collision resolution technique (Open Hashing) that uses linked lists at each index of the hash table.

Open Addressing

A collision resolution technique (Closed Hashing) that tries alternate cells in an array using strategies like Linear Probing, Quadratic Probing, or Double Hashing.

Heap

A tree-based data structure used for priority queues that satisfies either the Max-Heap (parent greater than children) or Min-Heap property.

Merge Sort

A Divide and Conquer sorting algorithm that recursively divides an array into halves, sorts them, and then merges the results with a time complexity of $O(n\text{ log }n)$.

Radix Sort

A non-comparative integer sorting algorithm that sorts data digit-by-digit starting from the least significant digit.

Quick Sort

A Divide and Conquer sorting algorithm that partitions an array into sub-arrays based on a chosen pivot element.

Bubble Sort

An internal sorting algorithm that repeatedly compares and swaps consecutive elements, moving the largest element to the right in each pass.

Topological Sort

A linear ordering of vertices in a Directed Acyclic Graph ($DAG$) where for every directed edge $u \rightarrow v$, vertex $u$ appears before vertex $v$.

Dijkstra's Algorithm

A single-source shortest path algorithm for weighted graphs used to find the minimum cost from a source vertex to all other vertices.

Minimum Spanning Tree (MST)

A subgraph containing all vertices of a connected weighted graph with the minimum total edge cost and no cycles.

Breadth First Search (BFS)

A graph traversal method that explores nodes layer by layer using a Queue ($FIFO$) concept.

Depth First Search (DFS)

A graph traversal method that explores nodes depth-wise (top to bottom) using a Stack ($LIFO$) concept.