Python

Knowledge

Declarative knowledge involves statements of fact, while imperative knowledge consists of steps or recipes on how to do something.

Recipe

A sequence of simple steps that dictate the flow of control in a process, including when each step is executed and when to stop.

Fixed program computer

An older type of computer like a calculator that follows a predetermined set of instructions.

Stored program

A computer that can store and execute instructions, including special programs like interpreters that execute instructions in order.

Turing's primitives

Six basic operations (move left, move right, read, write, scan, do nothing) that can be used to compute anything, with programming languages adding more primitives.

Expressions

Legal combinations of primitives in a programming language, with values and meanings, formed by combining objects and operators.

Semantics

Refers to the meaning of syntactically valid strings in a programming language, ensuring proper grammar and syntax placement.

Objects

Data entities that programs manipulate, having a type defining the operations that can be performed on them, such as scalar (indivisible) and non-scalar (structured) types.

Scalar

Data types like integers, real numbers, boolean values, and None, each with specific characteristics and uses in programming.

Expressions

Combine objects and operators to form expressions, each having a value and a type, following a syntax pattern of

While loops

Iterative structures in programming that continue until a condition is met, often used when the number of iterations is unknown.

For loops

Iterative structures where the number of iterations is known, allowing for easier control over the loop and counter variables.

Indexing

Refers to finding specific values within code, with strings being immutable and algorithms like bisection search used for efficient searching.

Algorithms

Methods like guess and check, bisection, and approximation used to solve problems efficiently and accurately in programming.

Abstraction

Simplifying complex systems by focusing on essential details, achieved through function specifications, docstrings, and decomposition in programming.

Bisection Search

A search algorithm that requires the list to be sorted and finds the position of a target value within a sorted array.

Logarithmic Complexity

Refers to algorithms where the time complexity grows logarithmically with the input size, often seen in bisection search where the number of steps is proportional to the logarithm of the input size.

Polynomial Complexity

Describes algorithms whose time complexity grows with the square size of the input, commonly seen in nested loops or recursive function calls.

Exponential Complexity

Occurs in recursive functions where more than one recursive call is made for each size of the problem, leading to a high cost, as in problems like Towers of Hanoi.

Big Oh Notation

A notation used to describe the upper bound of the time complexity of algorithms, providing a comparison of algorithm efficiency and growth rates.

Linear Search

A search algorithm that finds an item within a collection by sequentially checking each element, with a time complexity of O(n) in the worst case.

Binary Search

A search algorithm that requires the list to be sorted and finds an element in O(log n) time complexity.

Amortized Cost

Refers to the average cost of an operation over a sequence of operations, often used when sorting a list once and performing multiple searches.

Monkey Sort

Also known as bogosort or stupidsort, a sorting algorithm that randomly shuffles elements until they are sorted, with a best-case time complexity of O(n) and an unbounded worst-case time complexity.

Merge Sort

A sorting algorithm that uses a divide and conquer approach by recursively splitting the list into sublists, sorting them, and merging them back together, with a time complexity of O(n log(n)), making it one of the fastest sorting algorithms.