COMS1017A Vocabulary Flashcards

Vocabulary practice flashcards covering core concepts of C++, Algorithm Analysis, Searching, Sorting, Arrays, Vectors, and Linked Lists.

Algorithm Analysis

The practice of evaluating the resource requirements of an algorithm, measured primarily in runtime (time complexity) and memory usage (space complexity).

Asymptotic Complexity

The evaluation of an algorithm's runtime or space growth as the input size $n$ becomes very large ($n \rightarrow \infty$).

Big-O Notation ($O$)

A mathematical notation representing an asymptotic upper bound on the time or space complexity of an algorithm.

Big-Omega Notation ($\Omega$)

A mathematical notation representing an asymptotic lower bound on the time or space complexity of an algorithm.

Big-Theta Notation ($\Theta$)

A mathematical notation representing a tight asymptotic bound on an algorithm, bounding its complexity both above and below.

Abstract Data Type (ADT)

A specification of a data structure that defines its interface and supported operations without dictating how the data is stored in memory.

g++

The GNU C++ compiler used to compile and link C++ source files into executable programs from the command line.

Makefile

A text file containing instructions for the make build automation tool to compile and link multi-file software projects.

std::endl

A standard C++ stream manipulator that inserts a newline character into the output stream and flushes the output buffer.

Pointer

A variable that stores the memory address of another object or variable.

Dereference Operator ($*$)

An operator used with a pointer to access or modify the value stored at the memory address to which the pointer points.

Reference

An alias to an existing variable in C++ that must be initialized when declared and cannot be changed to refer to another object or set to nullptr.

Stack (Call Stack)

An automatically managed area of memory that stores stack frames for function calls, local variables, and execution context.

Heap (FreeStore)

A region of memory used for dynamic memory allocation at runtime via the new operator, requiring explicit deallocation using delete or delete[].

Segmentation Fault

A program crash caused by attempting to access memory outside the program's permitted memory segment, such as dereferencing an uninitialized pointer or nullptr.

std::string_view

A lightweight, non-owning reference to a string or character array introduced in C++17 that allows efficient read-only access without copying.

Class

A user-defined type in C++ that encapsulates member variables and member functions into a single logical structure.

Linear Search

A searching algorithm that inspects each element in a container sequentially from index $0$ to $n - 1$, running in $O(1)$ best-case and $O(n)$ worst-case time.

Binary Search

An efficient search algorithm for sorted containers that repeatedly divides the search range in half, running in $O(1)$ best-case and $O(\log(n))$ worst-case time.

Insertion Sort

A sorting algorithm that builds a sorted array section one element at a time by repeatedly shifting elements to insert each unsorted key into its correct position.

Selection Sort

An in-place sorting algorithm that repeatedly finds the smallest element in the unsorted section and swaps it with the first unsorted element, operating in $O(n^2)$ time across all cases.

Bubble Sort

A simple sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they are out of order, bubbling the largest value to the end each pass.

Contiguous Memory

A memory arrangement where all allocated bytes or elements are stored in adjacent, consecutive memory addresses.

Pointer Arithmetic

The computation of element addresses in contiguous memory by adding an index offset multiplied by the data type size to a base pointer address.

std::vector

A dynamic array container in the C++ Standard Template Library stored on the heap that manages item count, buffer capacity, and automatically resizes when full.

std::array

A fixed-size sequence container in C++ allocated on the stack whose size must be known at compile-time.

Amortized Constant Time

The average time per operation over a sequence of $n$ operations, ensuring that rare expensive steps (like array doubling) do not alter the overall $O(1)$ average complexity.

Link (Node)

A node structure in a linked list containing a data value and a pointer to the next node in the sequence.

Singly Linked List

A linear dynamic data structure made up of heap-allocated nodes connected unidirectionally via next pointers.

Doubly Linked List

A linked list structure where each node stores pointers to both its next node and its previous node, enabling bidirectional traversal.

Circularly Linked List

A linked list variation where the next pointer of the final node points back to the first node instead of holding nullptr.

Iterator

A pointer-like object in C++ providing dereference ($*$) and increment ($++$) operators to enable uniform traversal across container elements.

Spatial Locality

The principle that accessing a specific memory address makes adjacent memory addresses likely to be accessed soon, improving CPU cache performance.

Temporal Locality

The principle that a memory location accessed once is likely to be accessed again in the near future, allowing fast retrieval from CPU cache memory.