C949 Data Structures and Algorithms
Tuple
A datatype that is immutable, which means that once it's been created, the elements can't be
changed. It is also a sequence type. Is typically used when element position, and not just the
relative ordering of elements is important.
Named Tuple
An immutable datatype where the element position is important. Each element can have it's
own designated name.
Set
An ADT that serves as an unordered collection of unique elements. When created, the values
should be contained within a sequence-type iterateable object.
Intersection
Returns a new set containing only the elements in common between one set and all provided
sets.
Union
Returns a new set containing all of the unique elements in all sets.
Difference
Returns a set containing only the elements of set that are not found in any of the provided sets.
Symmetric Difference
Returns a set containing only elements that appear in exactly one of set A or set B.
Dictionary
A python container used to describe associative relationships. It associates keys with values. A
key can be any immutable type, such as a number, string, or tuple. A value can be any type.
Numeric Data Type
A data type which supports all of the normal mathematical operations. These are the most
common types used to store data.
,Sequence Data Type
Data types which are collections of objects ordered by position.
Mapping Data Type
A data type used exclusively by the dict type. Each element is independent, which means there
is no special ordering. Also uses key value pairs to associate a key with a value.
Algorithm
A sequence of steps for accomplishing a task.
Linear Search
A search algorithm that starts from the beginning of a list and checks each element until the
search key is found or the end of the list is reached.
Runtime
The time it takes for an algorithm to execute.
Binary Search
An algorithm for searching a list if the list's elements are sorted. It starts by checking the middle
element of the list. If the search key is found, the algorithm returns the matching location. If
not, the algorithm repeats the search on the remaining left sublist if the search key is less than
the middle element, or on the remaining right sublist if it's larger.
[log2N]+1
The maximum number of steps required to reduce the search space to an empty sublist.
Which of the following Big O Notations is equivalent to O(N+999)?
O(N)
Which of the following Big O Notations is equivalent to O(734*N)?
O(N)
Which of the following Big O Notations is equivalent to O(12*N)+6(N^3+1000)?
O(N^3)
Simplify: 10*O(N^2)
O(N^2)
,Simplify: 2*N^3+O(N^2)
O(N^3)
Simplify: log2N
O(logN)
O(1)
Constant runtime complexity.
O(logN)
Logarithmic runtime complexity.
O(N)
Linear runtime complexity.
O(NlogN)
Log-linear runtime complexity.
O(N^2)
Quadratic runtime complexity.
O(c^N)
Exponential runtime complexity.
Selection Sort
A sorting algorithm that treats the input as two parts, sorted and unsorted, and repeatedly
selects thee proper next value to move from the unsorted part to the end of the sorted part.
Has a complexity of O(N^2)
Insertion Sort
A sorting algorithm that treats the input as two parts, sorted and unsorted, and repeatedly
inserts the next value from the unsorted part into the correct location in the sorted part. Has a
complexity of O(N^2). For sorted or nearly sorted inputs, it's runtime is O(N).
Quicksort
A sorting algorithm that repeatedly partitions the input into low and high parts (each unsorted),
and then recursively sorts each of those parts. The algorithm uses two variables, l and h (low
and high). As long as the value at index l is less than the pivot value, the algorithm increments l.
, As long as the value at index h is higher than the pivot value, the algorithm decrements h. Then
if l >= h, all elements have been partitioned. Otherwise, the elements at l and h are swapped,
then the algorithm continues. It's runtime complexity is typically O(NlogN)
Pivot
A selected value that then divides the data into low and high parts. It can be any value within
the array, but it is most commonly the value of the middle array element.
Data Structure
A way of organizing, storing and performing operations on data. Operations performed include
accessing or updating, searching, inserting or removing data.
Record
A data structure that stores subitems, often called fields with a name associated with each
subitem.
Array
A data structure that stores an ordered list of items, where each item is directly accessible by a
positional index.
Linked List
A data structure that stores an ordered list of items in nodes, where each node stores data and
has a pointer to the next node.
Binary Tree
A data structure in which each node stores data and has up to two children, known as a left and
a right child respectively.
Hash Table
A data structure that stores unordered items by mapping each item to a location in an array.
Max-Heap
A data structure that is a tree that maintains the simple property that a node's key is greater
than or equal to the node's childrens' keys.
Min-Heap
A data structure that is a tree that maintains the simple property that a node's key is less than
or equal to the node's childrens' keys.
Tuple
A datatype that is immutable, which means that once it's been created, the elements can't be
changed. It is also a sequence type. Is typically used when element position, and not just the
relative ordering of elements is important.
Named Tuple
An immutable datatype where the element position is important. Each element can have it's
own designated name.
Set
An ADT that serves as an unordered collection of unique elements. When created, the values
should be contained within a sequence-type iterateable object.
Intersection
Returns a new set containing only the elements in common between one set and all provided
sets.
Union
Returns a new set containing all of the unique elements in all sets.
Difference
Returns a set containing only the elements of set that are not found in any of the provided sets.
Symmetric Difference
Returns a set containing only elements that appear in exactly one of set A or set B.
Dictionary
A python container used to describe associative relationships. It associates keys with values. A
key can be any immutable type, such as a number, string, or tuple. A value can be any type.
Numeric Data Type
A data type which supports all of the normal mathematical operations. These are the most
common types used to store data.
,Sequence Data Type
Data types which are collections of objects ordered by position.
Mapping Data Type
A data type used exclusively by the dict type. Each element is independent, which means there
is no special ordering. Also uses key value pairs to associate a key with a value.
Algorithm
A sequence of steps for accomplishing a task.
Linear Search
A search algorithm that starts from the beginning of a list and checks each element until the
search key is found or the end of the list is reached.
Runtime
The time it takes for an algorithm to execute.
Binary Search
An algorithm for searching a list if the list's elements are sorted. It starts by checking the middle
element of the list. If the search key is found, the algorithm returns the matching location. If
not, the algorithm repeats the search on the remaining left sublist if the search key is less than
the middle element, or on the remaining right sublist if it's larger.
[log2N]+1
The maximum number of steps required to reduce the search space to an empty sublist.
Which of the following Big O Notations is equivalent to O(N+999)?
O(N)
Which of the following Big O Notations is equivalent to O(734*N)?
O(N)
Which of the following Big O Notations is equivalent to O(12*N)+6(N^3+1000)?
O(N^3)
Simplify: 10*O(N^2)
O(N^2)
,Simplify: 2*N^3+O(N^2)
O(N^3)
Simplify: log2N
O(logN)
O(1)
Constant runtime complexity.
O(logN)
Logarithmic runtime complexity.
O(N)
Linear runtime complexity.
O(NlogN)
Log-linear runtime complexity.
O(N^2)
Quadratic runtime complexity.
O(c^N)
Exponential runtime complexity.
Selection Sort
A sorting algorithm that treats the input as two parts, sorted and unsorted, and repeatedly
selects thee proper next value to move from the unsorted part to the end of the sorted part.
Has a complexity of O(N^2)
Insertion Sort
A sorting algorithm that treats the input as two parts, sorted and unsorted, and repeatedly
inserts the next value from the unsorted part into the correct location in the sorted part. Has a
complexity of O(N^2). For sorted or nearly sorted inputs, it's runtime is O(N).
Quicksort
A sorting algorithm that repeatedly partitions the input into low and high parts (each unsorted),
and then recursively sorts each of those parts. The algorithm uses two variables, l and h (low
and high). As long as the value at index l is less than the pivot value, the algorithm increments l.
, As long as the value at index h is higher than the pivot value, the algorithm decrements h. Then
if l >= h, all elements have been partitioned. Otherwise, the elements at l and h are swapped,
then the algorithm continues. It's runtime complexity is typically O(NlogN)
Pivot
A selected value that then divides the data into low and high parts. It can be any value within
the array, but it is most commonly the value of the middle array element.
Data Structure
A way of organizing, storing and performing operations on data. Operations performed include
accessing or updating, searching, inserting or removing data.
Record
A data structure that stores subitems, often called fields with a name associated with each
subitem.
Array
A data structure that stores an ordered list of items, where each item is directly accessible by a
positional index.
Linked List
A data structure that stores an ordered list of items in nodes, where each node stores data and
has a pointer to the next node.
Binary Tree
A data structure in which each node stores data and has up to two children, known as a left and
a right child respectively.
Hash Table
A data structure that stores unordered items by mapping each item to a location in an array.
Max-Heap
A data structure that is a tree that maintains the simple property that a node's key is greater
than or equal to the node's childrens' keys.
Min-Heap
A data structure that is a tree that maintains the simple property that a node's key is less than
or equal to the node's childrens' keys.
