メインコンテンツまでスキップ

09 - Programming Concepts & Paradigms

Software Design & Architecture​

Relevant DSS-P Skills
  • 3. Technology > 3.1 Software Development > Software Design Methodology

Design Principles​

  • Orthogonality and DRY principle - The principle that every piece of knowledge must have a single, unambiguous, authoritative representation within a system
  • Separation of concerns - A design principle for separating a computer program into distinct sections
  • Design by Contract - An approach for designing software that prescribes formal, precise and verifiable interface specifications for software components
  • Law of Demeter - A design guideline for developing software, particularly object-oriented programs
  • SOLID - The principle of OOD - A mnemonic acronym for five design principles intended to make object-oriented designs more understandable, flexible, and maintainable
    • Single responsibility
    • Open–closed
    • Liskov substitution
    • Interface segregation
    • Dependency inversion
  • The Reactive Manifesto - A coherent approach to systems architecture where applications are responsive, resilient, elastic and message driven
  • Unix philosophy - A set of cultural norms and philosophical approaches to software development
  • KISS principle - A design principle which states that most systems work best if they are kept simple rather than made complicated

Design Best Practices​

  • Resource acquisition is initialization (RAII) - A programming idiom where the life cycle of a resource is bound to the lifetime of an object
  • Rob Pike's 5 Rules of Programming - A set of rules about where to focus optimization efforts, emphasizing measurement and the importance of data structures
  • The Zen of Python - A collection of 19 guiding principles for writing computer programs that influence the design of the Python programming language
  • The twelve-factor app - A methodology for building software-as-a-service apps that are suitable for deployment on modern cloud platforms

Design Patterns​

  • Software design pattern - A general, reusable solution to a commonly occurring problem within a given context in software design
  • Entity–control–boundary - An architectural pattern used in software design and analysis that helps in structuring the responsibilities of classes in an object-oriented system
  • Command Query Responsibility Segregation - A pattern that separates read and update operations for a data store
  • Fluent interface - A method for designing object-oriented APIs based on method chaining with the goal of making the readability of the source code close to that of ordinary written prose
  • Model-view-controller pattern - A software design pattern commonly used for developing user interfaces that divides the related program logic into three interconnected elements
  • Dependency injection - A design pattern in which an object or function receives other objects or functions that it depends on

Architectural Styles​

  • Three-tier architecture - A client–server architecture in which presentation, application processing, and data management functions are logically separated
  • Microservices architecture - An approach to developing a single application as a suite of small services, each running in its own process and communicating with lightweight mechanisms
  • Event-driven architecture - A software architecture paradigm promoting the production, detection, consumption of, and reaction to events
  • Resource-oriented architecture - A style of software architecture and programming paradigm for designing and developing software in the form of a network of resources
  • Background processing - The execution of tasks in the background, allowing the main application to remain responsive

Architecture Description​

  • System - A group of interacting or interrelated elements that act according to a set of rules to form a unified whole
    • Systems architecture - The conceptual model that defines the structure, behavior, and more views of a system
      • 4+1 architectural view model - A view model used for "describing the architecture of software-intensive systems, based on the use of multiple, concurrent views"
      • The C4 model - An easy to learn, developer friendly approach to software architecture diagramming
      • UML - The graphical language for visualizing, specifying, constructing, and documenting the artifacts of a software-intensive system
      • Flowchart - A type of diagram that represents a workflow or process
    • Conway's law - An adage stating that organizations design systems that mirror their own communication structure
  • Related Standards

Domain-Driven Design (DDD)​

  • Domain-driven design - A major software design approach, focusing on modeling software to match a domain according to input from that domain's experts
  • Object-oriented analysis and design - A technical approach for analyzing and designing an application, system, or business by applying object-oriented programming, as well as using visual modeling throughout the software development process
    • Use case - A list of actions or event steps typically defining the interactions between a role (known in the Unified Modeling Language as an actor) and a system to achieve a goal
  • Ontology - A representation, formal naming and definition of the categories, properties and relations between the concepts, data and entities that substantiate one, many or all domains of discourse
    • Semantic network - A knowledge base that represents semantic relations between concepts in a network
      • WordNet - A large lexical database of English
  • Database design - The organization of data according to a database model

Core Programming Concepts​

Relevant DSS-P Skills
  • 3. Technology > 3.1 Software Development > Computer Science

Language Mechanics & Execution​

  • Source code - A collection of code, possibly with comments, written using a human-readable programming language, usually as plain text
  • Statement - A syntactic unit of an imperative programming language that expresses some action to be carried out
  • Expression - A syntactic entity in a programming language that may be evaluated to determine its value
    • Operator and Operand
  • Literal - A notation for representing a fixed value in source code
    • Template string or literal
    • Heredoc - A file literal or input stream literal representing a section of source code that is treated as if it were a separate file
  • Constant - A value that cannot be altered by the program during normal execution
  • Variable - An abstract storage location paired with an associated symbolic name, which contains some known or unknown quantity of information referred to as a value
  • Scope - The region of a computer program where the binding of a name to an entity (name binding) is valid
  • Data type - A collection or grouping of data values, usually specified by a set of possible values and allowed operations
    • Primitives - A data type provided by a programming language as a basic building block or one not defined in terms of other data types
    • Nominal type system - A major class of type systems, in which compatibility and equivalence of data types is determined by explicit declarations and/or the names of the types
    • Structural type system - A major class of type systems in which type compatibility and equivalence are determined by the type's actual structure or definition
    • Duck typing - An application of the duck test determining type compatibility based on the presence of certain methods and properties
    • Union type - A data type definition that specifies which of a number of permitted primitive types may be stored in its instances
    • Type variance - The relationship between subtypes of a composite type and the subtypes of its components
    • Type safety - The extent to which a programming language discourages or prevents type errors
  • Reference - A value that enables a program to indirectly access a particular datum in the computer's memory or other storage device
    • Null pointer - A value saved for indicating that the pointer or reference does not refer to a valid object

Memory Management​

  • Reference counting - A programming technique of storing the number of references, pointers, or handles to a resource
  • Garbage collection - A form of automatic memory management where the collector attempts to reclaim memory occupied by objects no longer in use
  • Smart pointer - An abstract data type that simulates a pointer while providing added features, such as automatic memory management or bounds checking
  • Memory safety - The state of being protected from various software bugs and security vulnerabilities when dealing with memory access

Control Flow Structures​

  • Control flow - The order in which individual statements, instructions or function calls of an imperative program are executed or evaluated
  • Continuation - A data structure that represents the rest of a program's computation at a given point
  • Exception handling - The process of responding to the occurrence of exceptions during the execution of a program
  • Finite-state machine - A mathematical model of computation representing an abstract machine that can be in exactly one of a finite number of states at any given time

Foundational Techniques & Properties​

  • State - The stored information, at a given instant in time, to which a computer program or system has access
  • Function - A sequence of program instructions that performs a specific task, packaged as a unit
    • Parameter - A special kind of variable used in a subroutine or function to refer to one of the pieces of data provided as input
    • Anonymous function - A function definition that is not bound to an identifier
  • Immutable object - An object whose state cannot be modified after it is created
  • Generic Programming - A style of computer programming in which algorithms are written in terms of types to-be-specified-later that are then instantiated when needed
  • Assertion - A statement that a predicate (a Boolean-valued function) is expected to always be true at that point in the code
  • Autovivification - The automatic creation of a new variable or data structure as required when it is first used

Module Structure & Organization​

  • Cohesion - The degree to which the elements inside a module belong together
  • Coupling - The degree of interdependence between software modules, a measure of how closely connected two routines or modules are, and the strength of the relationships between modules

Programming Paradigms​

Relevant DSS-P Skills
  • 3. Technology > 3.1 Software Development > Computer Science

Object-oriented Programming​

  • Object-oriented Programming - A programming paradigm based on the object - a software entity that encapsulates data and function(s)
    • Abstraction - The process of hiding the complexity of a system by modeling classes appropriate to the problem and working at the most relevant level of detail
    • Encapsulation - The bundling of data with the methods that operate on that data, or the restricting of direct access to some of an object's components
    • Polymorphism - The provision of a single interface to entities of different types
      • Dynamic dispatch - The process of selecting which implementation of a polymorphic operation (method or function) to call at run time
    • Inheritance - The mechanism of basing an object or class upon another object or class, retaining similar implementation
    • Class - An extensible program-code-template for creating objects, providing initial values for state and implementations of behavior
    • Interface - An abstract type that contains no data, but defines behaviors as method signatures
    • Method - A procedure associated with an object, and implicitly acting upon that object
    • This keyword - A keyword used in many object-oriented programming languages to refer to the object associated with the current function or method call
    • Prototype-based programming - A style of object-oriented programming in which behavior reuse is performed via a process of reusing existing objects that serve as prototypes

Functional Programming​

  • Functional Programming - A programming paradigm where programs are constructed by applying and composing functions
    • Algebraic data type - A composite data type formed by combining other types
    • Pattern matching - The act of checking a given sequence of tokens for the presence of the constituents of some pattern
    • First-class function - The property of a programming language that treats functions as first-class citizens (e.g., assignable to variables, passable as arguments)
      • Map - A higher-order function that applies a given function to each element of a sequence, returning a sequence containing the results
      • Filter - A higher-order function that processes a data structure to produce a new data structure containing only those elements for which a given predicate returns true
      • Reduce - A higher-order function (also known as fold) that reduces a data structure to a single value by recursively applying a combining operation
    • Referential transparency - A property of expressions such that an expression can be replaced with its corresponding value without changing the program's behavior
    • Closure - A function together with a referencing environment for the non-local variables of that function
    • Side-effect - An observable effect of an operation, function, or expression that modifies state variable values outside its local environment
    • Monad - A software design pattern with a structure that combines program fragments (functions) and wraps their return values in a type with additional computation
    • Currying - The technique of converting a function that takes multiple arguments into a sequence of functions that each takes a single argument

Reactive Programming & Others​

  • Reactive Programming - A declarative programming paradigm concerned with data streams and the propagation of change
    • Functional Reactive Programming (FRP) - A programming paradigm for reactive programming using the building blocks of functional programming
    • Languages & Frameworks
      • RO - A library for streams and reactive programming for Go
      • ReactiveX - An API for asynchronous programming with observable streams
      • Elm - A delightful language for reliable web applications
  • Aspect-oriented Programming - A programming paradigm that aims to increase modularity by allowing the separation of cross-cutting concerns
    • Cross-cutting concern - An aspect of a program that affect several modules, without the possibility of being encapsulated in any of them

Scripting Languages​

Relevant DSS-P Skills
  • 3. Technology > 3.1 Software Development > Computer Science

Python​

  • Python - A programming language that lets you work quickly and integrate systems more effectively
    • Core Features
      • Python import system - The mechanism that organizes Python code into modules and packages, facilitating code reuse and structuring large applications
      • Special method names - The methods, identified by leading and trailing double underscores, that allow classes to implement operations invoked by special syntax
      • Type Hints - A standard syntax for type annotations of variables, function parameters, and return values, used for static analysis
        • typing module - The standard library module providing runtime support for type hints
        • Mypy - An optional static type checker for Python that aims to combine the benefits of dynamic typing and static typing
      • f-string - A type of string literal, prefixed with 'f' or 'F', which allows embedding expressions inside string constants using minimal syntax
      • with statement - A statement that simplifies exception handling by encapsulating standard uses of try/finally statements for resource management
        • contextlib - A module that provides utilities for common tasks involving the with statement
      • Generators - A simple and powerful way to create iterators, defined using a function with the yield statement
      • Decorators - A syntax using the '@' symbol for transforming functions and methods, often used for modifying or enhancing them non-intrusively
      • Coroutine - A specialized generator function, defined with async def, that can suspend and resume its execution, enabling cooperative multitasking
      • Lambda - A small anonymous function defined using the lambda keyword, restricted to a single expression
      • Data Classes - A module and decorator providing a concise way to create classes primarily used to store data, automatically generating special methods
      • Pattern Matching - A feature providing functionality similar to switch statements, allowing matching of values against complex patterns including sequences, mappings, and object structures
      • Unpacking Operator - The extended usages of the * iterable unpacking operator and ** dictionary unpacking operators to allow unpacking in more positions, an arbitrary number of times, and in additional circumstances
    • Key Libraries
      • pathlib - The module offering classes representing filesystem paths with semantics appropriate for different operating systems
      • dotenv - A library that reads key-value pairs from a .env file and can set them as environment variables
      • Pydantic - A data validation and settings management library for Python
      • Tenacity - A general-purpose retrying library for Python
    • Development Tools
      • IPython - A rich interactive interface to Python with a history mechanism, tab completion, and special magic commands

JavaScript & TypeScript​

  • JavaScript/ECMAScript - The standard that defines the ECMAScript Language
    • Module System
      • CommonJS - A project with the goal of specifying an ecosystem for JavaScript outside the browser
      • ES modules - The official standard format to package JavaScript code for reuse
      • UMD - The patterns for Universal Module Definition for use in the browser, and in AMD and CommonJS-based systems
    • Core Features
      • Event-driven - A programming paradigm in which the flow of the program is determined by events such as user actions, sensor outputs, or messages from other programs
      • Spread and rest operators - The syntax that allows an iterable such as an array expression or string to be expanded in places where zero or more arguments or elements are expected
      • Generator - An object returned by a generator function and it conforms to both the iterable protocol and the iterator protocol
    • Key Libraries
      • Lodash - A modern JavaScript utility library delivering modularity, performance & extras
      • dax - Cross-platform shell tools for Deno and Node.js inspired by zx
      • Bun Shell - A built-in shell-like interface for running shell scripts
      • zx - A tool for writing better scripts
      • Zod - A TypeScript-first schema validation with static type inference
      • yup - A schema builder for runtime value parsing and validation
    • Typescript - A strongly typed programming language that builds on JavaScript, giving you better tooling at any scale
      • Union Types - A way to combine multiple types into one
      • Type Aliases - A name for any type
      • Type Assertions - A way to tell the compiler 'trust me, I know what I'm doing'
      • Mapped Types - A generic type which uses a union of PropertyKeys to iterate through keys of another type to create a new one
      • Nominal typing techniques - A way to simulate nominal types in TypeScript, which by default has a structural type system
      • Declaration Files - The files where you define the types for a library
      • Decorators - A special kind of declaration that can be attached to a class declaration, method, accessor, property, or parameter
    • TS Type Utilities
  • Tutorials & Practices
    • 33 JS Concepts - A repository with articles about 33 concepts every JavaScript developer should know
    • JS Project Guidelines - A set of best practices for JavaScript projects
    • Callback Hell - The nesting of callback functions when dealing with asynchronous logic
    • NodeSchool - A set of open source workshops that teach web software skills
    • Node.js Best Practices - A summary and curation of the top-ranked content on Node.js best practices

Ruby, Perl & Others​

  • Ruby - A dynamic, open source programming language with a focus on simplicity and productivity
    • Core Features
      • Percent notation - A concise syntax for generating various literal types, such as strings, arrays, and regular expressions, using a percent sign and delimiters
      • Fiber - A lightweight concurrency primitive that allows for cooperative multitasking by pausing and resuming execution
      • proc - A mechanism to encapsulate a block of code into an object that can be stored, passed, and executed
      • lambda - A specialized block object that enforces strict argument checking and localized return behavior
      • then - A method that yields the object itself to a block and returns the result, facilitating functional-style method chaining
      • define_method - The ability to create and register methods at runtime using define_method, enhancing code flexibility and reducing repetition
      • instance_eval - A method that evaluates a block or string within the context of a specific object instance, granting access to its internal scope and private methods
    • Libraries
      • io-event - The low level cross-platform primitives for constructing event loops
      • Async - A composable asynchronous I/O framework for Ruby based on io-event
    • Development Tools
  • Perl - A family of two high-level, general-purpose, interpreted, dynamic programming languages
    • Core Features
      • Special variables - The variables that have a special meaning to Perl
      • Built-in regex - The syntax of regular expressions in Perl
      • Context - A property of expressions that determines how they behave when evaluated
      • Scalar values - A single item of data
        • Reference - A scalar data type that 'points' to another piece of data
      • Quote-like operators - A set of generic quoting operators
      • I/O operators - The operators used for input and output operations, such as reading from a filehandle
  • Tcl - A dynamic programming language and a graphical user interface toolkit used for a wide range of applications
  • Lua - A powerful, efficient, lightweight, embeddable scripting language
  • Emacs Lisp - The programming language used to extend and customize the Emacs text editor
    • S-expression - A notation for nested list (tree-structured) data
    • Homoiconicity - A property of some programming languages in which the primary representation of programs is also a data structure in a primitive type of the language itself

Asynchronous & Concurrency​

Relevant DSS-P Skills
  • 3. Technology > 3.1 Software Development > Computer Science
  • Concurrent computing - A form of computing in which several computations are executed concurrently instead of sequentially
    • Coroutine - A computer program component that generalizes subroutines for non-preemptive multitasking, by allowing execution to be suspended and resumed
    • Async/await - A syntactic feature that allows an asynchronous, non-blocking function to be structured in a way similar to an ordinary synchronous function
    • Futures and promises - The constructs used for synchronizing program execution, representing a proxy for a result that is initially unknown
    • Semaphore - A variable or abstract data type used to control access to a common resource by multiple threads in a concurrent system
    • Mutex - A synchronization primitive that prevents state from being modified or accessed by multiple threads of execution at the same time
    • Channel - A model for interprocess communication and synchronization via message passing
    • Thread safety - A property of computer code applicable in multi-threaded environments, ensuring correct manipulation of shared data structures
    • Deadlock - A situation in concurrent computing where no member of a group of entities can proceed because each waits for another member to take action

Language Analysis​

Relevant DSS-P Skills
  • 3. Technology > 3.1 Software Development > Computer Science
  • Concepts
    • Formal language - A set of words, i.e. finite strings of letters, symbols, or tokens
      • Well-formed formula - A finite sequence of symbols from a given alphabet that is part of a formal language
    • Formal grammar - A set of formation rules for strings in a formal language
    • Chomsky hierarchy - A containment hierarchy of classes of formal grammars
    • Automata theory - The study of abstract machines and automata, as well as the computational problems that can be solved using them
    • Lexical Analysis (Tokenizing)
    • Syntactic Analysis (Parsing)
    • BNF syntax - A notation technique for context-free grammars, often used to describe the syntax of languages used in computing
    • AST - A tree representation of the abstract syntactic structure of source code written in a programming language
  • Parser Generators
    • ANTLR - A powerful parser generator for reading, processing, executing, or translating structured text or binary files
    • Bison - A general-purpose parser generator that converts a grammar description for a context-free grammar into a C program to parse that grammar
  • Lexer Generators
    • Flex - The Fast Lexical Analyzer - scanner generator
    • Ragel - A state machine compiler
  • Parsers/Libraries
    • tree-sitter - A parser generator tool and an incremental parsing library
    • ts-morph - A TypeScript Compiler API wrapper

Program Translation​

Relevant DSS-P Skills
  • 3. Technology > 3.1 Software Development > Computer Science
  • Concepts
    • Compiler - A computer program that translates computer code written in one programming language into another language
    • Transpiler - A type of translator that takes the source code of a program written in a programming language as its input and produces an equivalent source code in the same or a different programming language
    • Program optimization - The process of modifying a software system to make some aspect of it work more efficiently or use fewer resources
    • Machine code - A computer program written in machine language instructions that can be executed directly by a computer's central processing unit (CPU)
    • Cross compiler - A compiler capable of creating executable code for a platform other than the one on which the compiler is running
    • Linker - A computer system program that takes one or more object files and combines them into a single executable file

Major Compiler Infrastructures​

  • LLVM Compiler Infrastructure - A collection of modular and reusable compiler and toolchain technologies
    • Clang - A C language family frontend for LLVM
    • LLD - The LLVM Linker
  • gcc - The GNU Compiler Collection which includes front ends for C, C++, Objective-C, Fortran, Ada, Go, and D
  • rustc - The compiler for the Rust programming language

Specific Translators & Build Tools​

  • MinGW-w64 - An advancement of the original mingw.org project, created to support the GCC compiler on Windows systems
  • Go build command - A tool for managing Go source code
    • Static binary executable
  • GopherJS - A compiler from Go to JavaScript
  • Bunster - A shell compiler that turns your scripts into a self-contained executable programs

Linkers (Standalone)​

  • mold - A Modern Linker
  • Runtime Libraries
    • glibc - The GNU C Library project which provides the core libraries for the GNU system and GNU/Linux systems
    • musl libc - A C standard library intended for operating systems based on the Linux kernel

Program Execution​

Relevant DSS-P Skills
  • 3. Technology > 3.1 Software Development > Computer Science
  • Concepts
    • Runtime System - The part of a program that runs on a computer, for the language in which the program was written
    • Bytecode - A form of instruction set designed for efficient execution by a software interpreter
    • Just-in-time compilation - A way of executing computer code that involves compilation during execution of a program
    • Global interpreter lock - A mutex that protects access to Python objects, preventing multiple threads from executing Python bytecodes at the same time

Runtime Implementations​

  • Javascript

    • Node.js - A free, open-source, cross-platform JavaScript runtime environment
      • libuv - A multi-platform support library with a focus on asynchronous I/O
    • Deno - A modern runtime for TypeScript and JavaScript
      • Deno Deploy - A distributed HTTP service that allows you to run JavaScript, TypeScript, and WebAssembly at the edge
      • Deno Subhosting - A platform for SaaS providers to securely run untrusted customer code at scale using V8 isolates
    • Bun - A fast, all-in-one toolkit for running, building, testing, and debugging JavaScript and TypeScript
    • WinterJS - A blazingly fast JavaScript runtime built on Rust, using the SpiderMonkey engine and the Tokio runtime

  • Python

    • CPython (default)
    • pypy - A fast, compliant alternative implementation of Python
    • Pyodide - A Python distribution for the browser and Node.js based on WebAssembly

  • Ruby

    • CRuby (default)
    • JRuby - An implementation of the Ruby programming language atop the Java Virtual Machine

  • Java SE - The most proven, trusted, and secure development platform for modern application development

    • Java HotSpot VM - The primary Java Virtual Machine for desktops and servers, produced by Oracle Corporation
    • JMX API - The Java Management Extensions technology which is a standard part of the Java Platform
    • JDK tools - The command-line tools to create and build applications
    • GraalVM - An advanced JDK with ahead-of-time Native Image compilation
    • OpenJDK - The place to collaborate on an open-source implementation of the Java Platform, Standard Edition
    • Eclipse Temurin - The open-source, enterprise-ready, and TCK-certified builds of OpenJDK

  • .NET - The free, open-source, cross-platform framework for building modern apps and powerful cloud services

    • CLR - The virtual machine component of .NET Framework

  • Runtime Utilities

    • PM2 - A daemon process manager that will help you manage and keep your application online
    • PyCall - A Ruby library that allows you to call Python functions from Ruby
    • VisualVM - An All-in-One Java Troubleshooting Tool

Algorithm & Computational Complexity​

Relevant DSS-P Skills
  • 3. Technology > 3.1 Software Development > Computer Science

Algorithm​

  • Algorithm - A finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation
    • Analysis Techniques
      • Amortized analysis - A method for analyzing a given algorithm's complexity
      • Big O notation - A mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity
    • Algorithmic Paradigms
      • Recursion - A method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem
      • Divide and conquer - An algorithm design paradigm
      • Dynamic programming - A method for solving a complex problem by breaking it down into a collection of simpler subproblems
      • Backtracking - A class of algorithms for finding solutions to some computational problems
      • Greedy algorithm - An algorithmic paradigm that follows the problem-solving heuristic of making the locally optimal choice at each stage
    • Sorting Algorithms
      • Quicksort - An in-place sorting algorithm
      • Merge sort - An efficient, general-purpose, and comparison-based sorting algorithm
      • Heapsort - A comparison-based sorting algorithm
    • Searching Algorithms
      • Binary search - A search algorithm that finds the position of a target value within a sorted array
      • Interpolation search - An algorithm for searching for a key in a sorted array that has been ordered by numerical values assigned to the keys
    • String Algorithms
    • Graph Algorithms
      • Traversal
      • Shortest Path
        • Dijkstra's algorithm - An algorithm for finding the shortest paths between nodes in a weighted graph
        • Bellman–Ford algorithm - An algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph
      • Minimum Spanning Tree - A subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together
        • Prim's algorithm - A greedy algorithm that finds a minimum spanning tree for a weighted undirected graph
        • Kruskal's algorithm - A minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest
      • Other
    • Hashing Algorithms
      • Hash function - Any function that can be used to map data of arbitrary size to fixed-size values

Data Structures​

  • Abstract Data Types - A mathematical model for data types
    • String - A finite sequence of symbols that are chosen from a set called an alphabet
    • List - An abstract data type that represents a finite number of ordered values
    • Associative array - An abstract data type that can hold a collection of (key, value) pairs
    • Stack - An abstract data type that serves as a collection of elements, with two main operations: push and pop
    • Queue - An abstract data type that serves as a collection of elements, with two main operations: enqueue and dequeue
      • Priority queue - An abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it
    • Tree - An abstract data type that represents a hierarchical tree structure with a set of connected nodes
    • Graph - An abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics
  • Data Structures - A data organization, management, and storage format that is designed to enable efficient access and modification
    • Passive data structure - A record data structure that contains only public data fields and provides no methods other than implicitly for reading/writing the fields
    • Array - A data structure consisting of a collection of elements (values or variables)
      • Array slicing - An operation that extracts a subset of elements from an array and packages them as another array
      • Sparse matrix - A matrix in which most of the elements are zero, allowing for specialized storage and algorithms to save memory and processing time
    • Hash table - A data structure that implements an associative array abstract data type
      • Collision Resolution
        • Cuckoo hashing - A scheme in computer programming for resolving hash collisions of keys in a hash table
        • Linear probing - A scheme in computer programming for resolving collisions in hash tables
    • Linked data structure - A data structure which consists of a set of data records (nodes) linked together and organized by references
    • Persistent structure - A data structure that always preserves the previous version of itself when it is modified
    • Disjoint-set data structure - A data structure that stores a collection of disjoint (non-overlapping) sets
    • Tree-based
      • Search tree - A tree data structure used for locating specific keys from within a set
        • Binary search tree (BST) - A rooted binary tree data structure with the key of each internal node being greater than all keys in the respective node's left subtree and less than the ones in its right subtree
      • Markle tree - A tree in which every leaf node is labelled with the cryptographic hash of a data block
      • Heap - A tree-based data structure that satisfies the heap property
      • Trie - A search tree data structure used to locate specific keys from within a set
      • Fenwick tree - A data structure that can efficiently update elements and calculate prefix sums in a table of numbers
    • Graph-based
      • Adjacency matrix - A square matrix used to represent a finite graph
      • Adjacency list - A collection of unordered lists used to represent a finite graph