You Gotta Know These Programming Terms
An algorithm is a set of detailed instructions for solving a problem, such as “sort a list” or “divide two numbers.” Algorithms can be described in human language, a programming language, or in other ways, but they are written in detail to explain how to handle all possible inputs (e.g., the list to sort or the numbers to divide) or fail if the task is impossible (e.g., if dividing two numbers and the second is 0).
The word “algorithm” derives from the name of Al-Khwarizmi, a Persian scholar also credited with some of the most fundamental principles in algebra.
Computer scientists analyze how many steps algorithms need (time complexity) and how much memory they need for temporary storage of intermediate results (space complexity). The worst-case situations are expressed using big O notation; for example, if an algorithm to sort a list of n items might need up to n2 to sort the list, the algorithm’s worst-case time complexity is O(n2). (This is a simplification of the mathematics of asymptotic notation.)
Recursion is a technique used in some algorithms. Sometimes an algorithm calls itself to solve a smaller case of the problem, until it reaches a simple base case that is already solved. For example, a recursive algorithm to calculate n factorial uses the fact that n! = n·(n−1)!, so it calls itself on n−1 and keeps going with smaller values until it reaches the base case of 1!, which is just 1.
Tail recursion is the use of recursion as the last step of an algorithm. Algorithms that use tail recursion are often more optimized by compilers. Recursive algorithms can have their big O runtime calculated by the Master theorem.
A graph is a mathematical concept often used in algorithms, in which a set of vertices is connected by a set of edges. In visual representations, the vertices are shown as dots, with edges shown as lines between the two vertices they connect. A path between two vertices is a sequence of edges that starts at the first vertex and ends at the last. A cycle is a path that begins and ends at the same vertex.
A graph is called weighted if every edge has a number representing the “cost” of traveling the edge; weighted graphs are used, for example, in analyzing navigation, with vertices representing cities, edges representing roads between them, and weights representing distance (or travel time). A graph is called directed if each edge has an inherent direction (an edge going from vertex A to vertex B, but not from B to A), e.g., representing a one-way road
Graphs are also called networks, and this is the origin of the term social network: if vertices represent people and edges represent who knows whom, a social network is a graph of a collection of people and the relationships between them.
Graphs are used to organize data (often in trees, which are graphs in which you can reach any vertex from any other vertex, but there are no cycles), analyze navigation/travel (broadly construed, such as the flow of fluid in a complex pipe system), manage tasks and scheduling (with edges representing dependencies), and more.
Dijkstra’s algorithm is used to find the shortest path between two vertices of a graph (possibly a weighted graph, in which case “shortest” means least total weight). Prim’s algorithm and Kruskal’s algorithm are used to find a graph’s minimum spanning tree, that is a tree connecting all its vertices whose edges have the smallest possible total weight.
- Divide-and-conquer algorithms use recursion to split problems into smaller subproblems with smaller input sets. By solving the same problem on each of these subproblems, then combining the outputs in some way, a divide-and-conquer algorithm can efficiently solve problems on big input sets. Merge sort (a sorting algorithm), binary search (an algorithm for finding an item in a sorted list), and Karatsuba’s algorithm (an algorithm for multiplying integers) are examples of divide-and-conquer algorithms.
- Greedy algorithms are algorithms that make the locally optimum or “best” choice at every step. Such algorithms may or may not produce an overall best solution. Consider an algorithm for making change in which you pick the largest coin smaller than or equal to the amount of change you need to give. If you need to give 7¢ change, you first pick a nickel (5¢) and still have to make 2¢ change, so you pick a penny (1¢) and still have to make 1¢, so you add an additional penny and have broken the 7¢ into 5¢ + 1¢ + 1¢. In the U.S. coin system, this is optimal in the sense of using as few coins as possible, namely three coins. However, in a coin system that offered coins worth 1¢, 3¢, 4¢, and 5¢, the greedy algorithm would give the same solution, even though a solution with fewer coins is possible (4¢ + 3¢).
- Object-oriented programming is a programming paradigm that involves the creation of objects from classes that can hold data and transform it in various ways. A class is a definition of the fundamental properties than an object has, while objects are specific examples of a class (for instance, the general idea of a dog is a class, while your pet dog would be an object.) Inheritance allows subclasses to be defined so that the properties of a parent class are present in the sub-class (for example, “schnauzer” might be a subclass of “dog”). In composition, an object contains or references another object (which might or might not be of the same class, e.g., a dog’s digestive system might be another object). Object-oriented programming also often uses encapsulation to hide unnecessary details from other aspects, e.g., a dog’s digestive system doesn’t need to know about its circulatory system. Polymorphism is the idea that different classes may be able to do the same things in potentially different ways, e.g., animals all eat but they do so in different ways. Java and C++ are object-oriented languages.
- Functional programming is a paradigm based on the execution of various functions to calculate values. Functions in pure functional programming are free of side effects, meaning that they do not change the program state but only compute values. Functional languages use currying to evaluate functions with multiple inputs. ML and Haskell are functional programming languages.
A language’s typing refers to how the type of data a variable holds is defined and can or can#’t change. Common types of variables are booleans, which can only be true or false; strings, which hold text; integers; and floats and doubles, which hold non-integer numbers.
In statically typed languages, a variable is given a type the first time it is used and can’t be changed; compilers check that all variables have the correct types while the program is compiling, which helps catch errors but also makes some tasks more difficult. Java, C, and C++ have static typing.
Some languages support duck typing, which is sort of intermediate between static and dynamic typing. Duck typing essentially allows objects to do the same or similar things even if their classes have no formal relation. For example, airplanes and birds might both have a “fly” capability even though neither is a subclass of the other (or otherwise related).
This article was contributed by NAQT writer Vishwa Shanmugam.