Flashcards
M269
Cards in this deck (34)
- 10-1 knapsackA variant of a knapsack problem in which only one copy of each item is available.
- 23SATThe decision problem whether there is an interpretation that makes a 3CNF propositional logic formula true
- 3abstract data type (ADT)A definition of a data structure only in terms of the operations that may be performed it and by the pre- and postconditions of those operations
- 4abstractionAbstraction provides a handle on complexity by either
1. Ignoring detail by means of a model
2. hiding detail through the use of encapsulation - 5acyclic (graph)A graph containing no cycles
- 6adjacency listA means of representing a graph as a collection of unordered lists, one for each vertex in the graph. each list contains the set of neighbours of its vertex. Suitable for storing sparse graphs
- 7adjacency matrixA means of representing a graph showing which vertices of a graph are adjacent to which other vertices. Suitable for storing dense graphs.
- 8algorithmA precisely stated, step-by-step list of instructions.
- 9alphabetIn string-search algorithms, the set of distinct characters that are used to construct the search string. In Python implementations, an alphabet such as {G,A,C,T} is often represented as a string (i.e. 'GACT') though it could be represented as a proper set of strings:{'G','A','C','T'}.
- 10ambiguous / ambiguity (in natural language)when an expression of any natural language, such as English, or any formal language, such as predicate logic, can be interpreted in more than one way, it is described as ambiguous. Ambiguity is the property of being ambiguous.
- 11Analytical engineEarly design for a mechanical computer.
- 12approximate algorithmsa class of algorithms which will not necessary find the best solution to a problem, but will return solutions that are 'good enough'. On a very restrictive interpretation of this concept, an approximate algorithm should always return solutions that are within a fixed range from the optimal solution.
- 13arcs/edgesa link between two vertices in a graph
- 14argument (logic)A demonstration of a particular proposition (the conclusion, C) follows from, or is implied by, one or more other propositions (the premises, P1,P2, ... , Pn).
- 15argument (predicate)An entity to which a predicate applies.
- 16argument (programming)A value required by a function in a programming language.
- 17aritythe arity of a predicate or function is the number of arguments that the predicate or function takes.
- 18assignment (predicate logic)An assignment in predicate logic associates each constant with an object in the domain and each n-ary predicate with an n-ary relation.
- 19assignment (programming)a statement that stores a value in a variable
- 20assignment (propositional logic)An assignment in propositional logic associates each propositional variable with a truth value.
- 21atomicUsed to refer to the data types of a programming language, such as integers, Booleans, etc., which cannot be divided or further broken down in any way.
- 22atomic formulaIn predicate logic, an atomic formula is an expression of the form: p(t1,t2,..., tn) where p is a predicate symbol of arity n, and each of the t1,t2,...tn is either a constant symbol or a variable symbol.
- 23average-case analysisThe average-case analysis of an algorithm consists of an analysis of the efficiency of an algorithm using a model which identifies those inputs that occur in the real world (as opposed to all possible inputs).
- 24AVL treeA type of binary search tree is which every node has a balance factor of no less than -1 and no greater than 1.
- 25Babbage, CharlesCharles Babbage (1791-1871) was a British inventor and polymath
- 26backtrackingIn tree or graph search algorithms, the process of returning to an earlier state to explore a new set of possible states from there.
- 27balance factorin an AVL Tree, the height of a node's right subtree subtracted from the height of its left subtree.
- 28best caseAn input to an algorithm that would result in its quickest performance. For example, the best case for bubble sort is an input sequence that is already sorted.
- 29best first search (BeFS)A form of an algorithm for traversing trees or graphs in which the next node chosen for exploration is the one with the best value, where this value is calculated according to some heuristic.
- 30Big-O notationA symbolism used in mathematics to indicate the upper bound on how fast a function f(n) grows as n increases. Used in computer science to approximate the number of computational steps required for an algorithm to complete for inputs of size n.
- 31binary alphabetThe set {0,1}
- 32binary (function, predicate, relation)A binary function, predicate or relation has an arity of 2.
- 33binary heepA subclass of complete binary trees in which, for every node x with parent p, either p will be smaller than or equal to x (a min heap), or p will be greater than or equal to x (a max heap)
- 34binary searchA classic divide-and-conquer algorithm for searching sorted sequences for a specified item. It works by progressively having the length of the search sequence, and discarding the sub-sequences that could not possibly hold the search item.
Information
- Description
- Bachelors Degree M269 Algorithms, data structures and computability Flashcards on M269, created by E O on 12/11/2015.
- Created by
- E O
- Views
- 1
- Rating