CS 220 - Final Keyterms

Mathematics - study of numbers and their properties

Discrete - at fixed intervals

Sets - is a collection of elements (items or numbers etc)

Cardinality - size or count

Membership - item x an member of the set

Brute-Force Algorithm - checking/searching through all elts. of a set or list

Order Set - when order is imposed for a set

Difference - based on subtraction written as "\" or "-"

Cartesian Product - |A x B| = |A| x |B| and the order of the postions matter

Mappings - A → B, the default is one-directional

Reflexive - if for all elts. a element of S, a → a is related to a for ALL elts. in S

Symmetric - if a→ b then b → a, for all elts. a and/or b; if it goes in one direction it must be able to go the other direction

Transitive - if a → b and b → c, then a → c for all such a,b,c that have such mappings

Transitive Closure - the added connected such a→c for the above enables the transitive property he entire enhanced transitive mapping which is now {a → b, b → c, a → c}

Equivalence Class - a relationship that has all the properties of RST

Relationship - R(A,B) is a subset of A x B

Proper Subset - S1 != S2

Power Set - all possible subsets, to calculate: 2^|S|

Partial Function - any elt. of the first set connects to at most one elt. of the second set

Total Function - any elt. of the first set connects to exactly one elt of the second set

Injective Mapping - every elt. of the first set connects to uniquely one elt. of the second set

Factorial n! - similar to the injective mapping formula; Injective(m,n) * (n-m)!

Pigeonhole principle - you must have the same amount of A’s just as the same amount of B’s

Counting Maps - partial function, total function, & one-one function (injective mapping)

Onto Function - A function where every element in B is mapped by at least one element in A.

ONTO(m,n) Formula - The formula ONTO(m, n) = TOTAL(m, n) - NONONTO(m, n) calculates the number of onto functions.

Singleton - A set with exactly one element

Domain - The set of possible inputs in a function

Codomain - The set of potential outputs (where values could go, even if they don't

Range - The actual outputs a function maps to (a subset of the codomain)

Preimage - The set of A values that reach elements in the range of a function

Inclusion-Exclusion - A formula used to count elements in overlapping sets, ensuring no double-counting |A∪B| = |A| + |B| − |A∩B|

Partitions - A way to divide a set (S) into non-overlapping subsets where every element belongs to exactly one subset

Partition Formula - Partition(m, n) = Onto(m, n) / n!, which removes order from onto mappings.

Bell Number - The sum of all k-partitions of a set, representing the number of ways to partition a set into non-empty subsets

Partition(m,n) Formula - Partition(m, n) = Onto(m, n)/n!

Injective - A function where each elt. in A maps to a unique elt. in B (no two elements in A share the same B value)

Surjective - A function where each elt. in B is mapped by at least one elt. in A(no elements in B are left out)

Partial Inverse - A function where not every B value has a unique inverse back to A, meaning some elements in B may not be retrievable

Bijection - A function that is both injective and surjective, meaning |A| = |B| and every element has a unique pair

Adjacency Matrix - A square matrix used to represent a finite graph, where: 1 means an edge exists between two vertices & 0 means no edge exists

Row-Major Order - A way of storing and reading matrices where elements are accesed by row by row first

Column-Major Order - A way of storing and reading matrices where elements are accessed by column by column first

Transpose of a Matrix - A new matrix formed by swapping the rows and columns of the orginal matrix

Adjacency Matrix - a matrix representing a graph where 1 indicates an edge between two vertices and 0 indicates no connection

Sparse Graph - a graph with significantly fewer edges compared to the possible number of connections (i.e. mostly empty adjacency matrix)

Transitive Closure - the extension of a graph where all possible paths are added to represent connectivity

Strongly Connected Graph - a directed graph where there is a path between every pair of vertices in both directions

Unilaterally Connected Graph - a directed graph where a path exists between every pair of vertices, but not necessarily in both directions

Weakly Connected Graph - a directed graph that becomes strongly connected if you ignore the direction of edges

Degree of Vertex - the number of edges connected to a vertex; split into indegree (edges coming in) and outdegree (edges going out).

Handshaking Theorem - the sum of the degrees of all vertices in a graph equals twice the number of edges (∑ degree = 2|E|)

Clique - a fully connected subgraph where every node is adjacent to every other node

Hamiltonian Circuit - a cycle in a graph that visits every vertex exactly once before returning to the starting point

Matrix Addition & Subtraction - Two matrices can only be added or subtracted if they have the same dimensions.

Matrix Multiplication - Two matrices can be multiplied only if the number of columns in the first matrix matches the number of rows in the second. (AB ≠ BA in general)

Identity Matrix (I) - A square matrix with 1s on the diagonal and 0s everywhere else. Multiplying any matrix by the identity matrix does not change the matrix.

Scalar Matrix - A matrix that is a scaled version of the identity matrix, meaning all diagonal elements are multiplied by a constant.

Vector - A one-dimensional matrix, where either the number of rows or columns is equal to 1 (can be row or column vector).

Transitive Closure - The process of adding all possible paths to a matrix representation of a graph, written as: A* = A^1 + A^2 + A^3 + A^4

Pre-Order Transversal - A tree traversal method that processes nodes in (D → L → R) order, meaning it visits the data first, then the left child, then the right child. (Prefix Notation)

In-Order Transversal - A tree traversal method that processes nodes in (L → D → R) order, meaning it visits the left child first, then the data, then the right child. (Infix Notation)

Pre-Order Transversal - A tree traversal method that processes nodes in (L → R → D) order, meaning it visits the left child first, then the right child, then the data. (Postfix Notation)

BFS (Breadth-First-Search) - A graph traversal method that visits nodes level by level, moving horizontally before going deeper into the graph.

Tree - a connected acyclic graph, meaning it has no cycles and all nodes are connected

DAG (Directed Acyclic Graph) - a graph where edges have a direction and there are no cycles

Binary Tree - a tree where each parent node has at most two children

Perfect Binary Tree - a binary tree where every level is completely filled with nodes

Complete Binary Tree - a binary tree where all levels are filled except possibly the last, and nodes in the last level are as far left as possible

Balanced (AVL) Tree - a self-balancing binary tree that uses rotations to keep height balanced when nodes are added or deleted

Linked List - a linear data structure made of nodes stored in non-contiguous memory, where each node points to the next

Expression Tree - a binary tree used to represent mathematical expressions, where operators are internal nodes and operands are leaf nodes

Binary Operator - an operator that takes two operands (e.g., +, -, *, /)

Unary Operator - an operator that takes one operand (e.g., cos(x), sin(x), -x)

Expression Tree - a binary tree used to represent mathematical expressions, where operators are internal nodes and operands are leaf nodes

Inorder Traversal - method of traversing trees in the order Left → Data → Right (LDR). Most common for expression trees

Preorder Tranversal - method of traversing trees in the order Data → Left → Right (DLR), used in LISP processing

Decision Tree - a tree where only leaves store data, and internal nodes are placeholders guiding the search

Binary Search - a search algorithm that repeatedly divides a sorted list in half until the target value is found

Minimum Spanning Tree - a subset of edges in a weighted graph that connects all vertices with minimum total edge weight and no cycles

Kruskal's Algorithm - a greedy algorithm for finding the MST by sorting edges by weight and adding them one by one without forming cycles

Huffman Encoding - a variable-length encoding method used for data compression, where frequent symbols get shorter codes

Fixed-Length Encoding - method where every character is represented by a fixed number of bits (e.g., ASCII uses 8-bit codes)

Prefix Rule in Huffman Encoding - a rule that ensures no encoded character is a prefix of another to avoid ambiguity in decoding

Morse Code - a system of encoding text using dots (left) and dashes (right)

Morse Code Tree - a binary tree used to represent Morse Code, where left branches are dots (0) and right branches are dashes (1)

Walk - a sequence of vertices in a graph where each consecutive pair is connected by an edge

Trail - a type of walk where no edges are repeated

Path - a sequence of edges where no vertex or edge is repeated

Lattice/Grid - a network of evenly spaced horizontal and vertical lines, forming structured squares or rectangles

Node - a basic unit of data structures like linked lists, trees, or graphs

Parent Node - a node with at least one child node in a tree structure

Amortized Complexity O(n) - the average time complexity across multiple operations, ensuring that even expensive operations balance out over time

O(n log n) Complexity - a complexity class used in sorting and tree-based searches, where the total accumulated complexity is O(n log n)

Algorithm - a finite sequence of well-defined instructions to solve a problem

Turning Machine - a theoretical machine that processes data using an internal tape and halts when it reaches an output

Daemon Process - a background process that runs indefinitely, common in operating systems

Time Complexity - the number of steps or operations an algorithm takes to complete based on input size

Space Complexity - the amount of memory required by an algorithm, including temporary storage and variables

Garbage Collection - a process in computing that reclaims memory occupied by objects that are no longer needed