Variable - an abstraction inside a program that can hold a value. Each variable has associated data storage that represents one value at a time, but that value can be a list or other collection that in turn contains multiple values
Data Types - some programming languages provide types to represent data, which are referenced using variables. These types include numbers, Booleans, lists, and strings
List - an ordered sequence of elements
Element - an individual value in a list that is assigned a unique index
Index - a common method for referencing the elements in a list or or string using natural numbers
String - an ordered sequence of characters
Algorithm - a finite set of instructions that accomplish a specific task
Sequencing - the application of each step of an algorithm in the order in which the code statements are given
Code statement - a part of program code that expresses an action to be carried out
Expression - can consist of a value, a variable, an operator, or a procedure call that returns a value. They are evaluated to produce a single value
MOD (modulo operator) - evaluates to the remainder after division
String concatenation - joins together two or more strings end-to-end to make a new string
Substring - part of an existing string
Boolean value - a value that is either true or false
Logical operators - NOT, AND, and OR, which evaluate to a Boolean value (true/false)
Selection - determines which parts of an algorithm are executed based on a condition being true or false (if-statements)
Iteration - a repeating portion of an algorithm. Iteration repeats a specified number of times or until a given condition is met (for loops and while loops)
Traversing a list - accessing either a portion of elements in a list or all elements in a list (for loop processing a list)
Linear search algorithms - check each element of a list, in order, until the desired value or found or all elements in the list have been checked
Binary search algorithm - starts at the middle of a sorted data set of numbers and eliminates half of the data; this process repeats until the desired value is found or all elements have been eliminated
Procedure - a named group of programming instructions that may have parameters and return values (called function in Python)
Parameter - an input variable of a procedure (function). Allows functions (procedures) to be generalized, enabling the functions (procedures) to be reused with a range of input values or arguments
Argument - specifies the value of the parameter when a procedure (function) is called
Procedural abstraction - provides a name for a process and allows a procedure to be used only knowing what it does, not how it does it Using functions (procedural abstraction) avoids repeating code, make code easier to read.
Modularity - the subdivision of a computer program into separate subprograms
(Software) Library - contains functions (procedures) that may be used in creating new programs
Application program interface (API) - specifications for how the functions (procedures) in a library behave and can be used
Simulation - a representation that uses varying sets of values to reflect the changing state of a phenomenon. They often mimic real-world events with the purpose of drawing inferences, allowing investigation of a phenomenon without the constraints of the real world
Problem - a general description of a task that can (of cannot) be solved algorithmically. An instance of a problem also includes specific input
Decision problem - a problem with a yes/no answer (e.g., is there a path from A to B?)
Optimization problem - a problem with the goal of finding the "best" solution among many (e.g., what is the shortest path from A to B?)
Efficiency - an estimation of the amount of computational resources used by an algorithm. Efficiency is typically expressed as a function of the size of the input (n)
Reasonable amount of time - algorithms with a polynomial efficiency or lower (constant, linear, square, cube, etc. - n, 10*n, n2, n3)
Unreasonable amount of time - algorithms with exponential or factorial efficiencies (2n or n!)
Heuristic - an approach to a problem that produces a solution that is not guaranteed to be optimal but may be used when techniques that are guaranteed to always find an optimal solution are impractical - A heuristic is used when it's impossible or impractical to use an algorithm to solve a problem. Therefore, we need something that is good enough on average for most instances. This is where a heuristic shines.
Decidable problem - a decision problem for which an algorithm can be written to produce a correct output for all inputs (e.g., "Is the number even?")
Undecidable problem - a decision problem for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer