FUNDAMENTAL PRINCIPLES AND CONCEPTS OF COMPUTING Flashcards
(34 cards)
Set of well-defined instructions for performing a task or solving a problem.
ALGORITHM
Each step is clearly defined.
PRECISION
An algorithm must terminate after a finite number of steps.
FINITENESS
Algorithms take input and produce output.
INPUT AND OUTPUT
Each operation is basic enough to be carried out, in principle, by a human using only paper and pencil.
EFFECTIVENESS
Uses divide-and-conquer to sort elements by partitioning arrays.
QUICKSORT
Divides the list into halves, sorts them, and merges them.
MERGESORT
Efficiently finds an element in a sorted list by repeatedly dividing the search interval in half.
BINARY SEARCH
Checks each element in a list until the target is found.
LINEAR SEARCH
Specialized formats for organizing, processing, retrieving, and storing data.
DATA STRUCTURES
Store elements of the same type in contiguous memory locations.
ARRAY—>FIXED SIZE
Each element points to the next.
LINKED LISTS—>SINGLY LINKED LIST
Each element has pointers to both the next and previous elements.
LINKED LISTS—>DOUBLY LINKED LIST
Elements are added and removed from the same end.
STACKS—>LIFO (Last In, First Out)
Elements are added at one end and removed from the other.
QUEUES—>FIFO (First In, First Out)
Each node has at most two children.
TREES—>BINARY TREE
A binary tree where the left child is less than the parent node and the right child is greater.
TREES—>BINARY SEARCH TREE
Consist of nodes (vertices) and edges (links).
GRAPHS—>DIRECTED/UNDIRECTED
Provide fast access to data.
HASH TABLES—>KAY-VALUE PAIRS
The study of the amount of resources required by an algorithm to run, typically time and space.
COMPUTATIONAL COMPLEXITY
Describes the upper bound of an algorithm’s running time.
BIG O NOTATION
Constant time, regardless of input size.
O(1)
Linear time, grows proportionally with input size.
O(n)
Logarithmic time, increases slowly with input size.
O(log n)
