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)

3 multiple choice options

Which of the following Big O Notations is equivalent to O(734*N)?

O(N)

3 multiple choice options

Which of the following Big O Notations is equivalent to O(12*N)+6(N^3+1000)?

O(N^3)

3 multiple choice options

Simplify: 10*O(N^2)

O(N^2)

3 multiple choice options

Simplify: 2*N^3+O(N^2)

O(N^3)

2 multiple choice options

Simplify: log2N

O(logN)

2 multiple choice options

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.

Graph

A data structure for representing connections among items, and consists of vertices connected by edges. A vertex represents an item, and an edge represents a connection between the vertices.

Computational Problem

Specifies an input, a question about the input that can be answered using a computer, and the desired output.

NP-Complete Problems

A set of problems for which no known efficient algorithm exists. Alongside this, no one has proven an efficient algorithm to solve this problem is impossible, and if an efficient algorithm exists, then all of these problems can be solved efficiently.

Efficient Program

An algorithm with a runtime that increases no more than polynomially with respect to the input size.

Abstract Data Type (ADT)

A data type described by predefined user operations.

List

An ADT for holding ordered data.

Dynamic Array

An ADT for holding ordered data and allowing indexed access.

Stack

An ADT in which items are only inserted on or removed from the top. Is referred to as a last-in first-out ADT.

Queue

An ADT in which items are inserted at the end, and removed from the front. Is referred to as a first-in first-out ADT.

Deque

An ADT in which items can be inserted and removed at both the front and back.

Bag

An ADT for storing items in which the order does not matter and duplicate items are allowed.

Priority Queue

An ADT where items are inserted at the end, and removed from the front. Each item has a priority, and items with a higher priority are closer to the front.

Dictionary (Map)

An ADT that associates keys with values.

Abstraction

To have a user interact with an item at a high-level, with lower-level internal details hidden from the user.

Computational Complexity

The amount of resources used by the algorithm.

Runtime Complexity

A function, T(N), that represents the number of constant time operations performed by the algorithm on an input of size N.

Space Complexity

A function, S(N), that represents the number of fixed-size memory units used by the algorithm for the input of size N.

Auxiliary Space Complexity

The space complexity not including the input data.

Constant Time Operation

An operation that, for a given process, always operates in the same amount of time, regardless of input values.

O Notation

Provides a growth rate for an algorithm's upper bound.

Ω Notation

Provides a growth rate for an algorithm's lower bound.

Θ Notation

Provides a growth rate that is both an upper and lower bound.

Recursive Algorithm

An algorithm that breaks the problem into smaller subproblems and applies the algorithm itself to solve the smaller subproblems.

Recursive Function

A function that calls itself.

Fibonacci Sequence

A numerical sequence where each term is the sum of the previous 2 terms in the sequence, except the first 2 terms, which are 0 and 1.

Recurrence Relation

A function that is defined in terms of the same function operating on a value less than N.

Recursion Tree

A visual diagram of an operation done by a recursive function, that separates operations done directly by the function and operations done by recursive calls.

Shell Sort

A sorting algorithm that treats the input as a collection of interleaved lists, and sorts each list individually with a variant of the insertion sort algorithm. It uses the gap values to determine the number of interleaved lists.

Gap Value

A positive integer representing the distance between elements in an interleaved list. If an element is at index i, the next element is at index i + this value.

Radix Sort

A sorting algorithm designed specifically for integers. This algorithm makes use of a concept called buckets and is a type of bucket sort. It processes one digit at a time starting with the least significant digit and ending with the most. It works in two steps, one, all array elements are placed into buckets, then the array is rebuilt by removing all elements from the buckets, in order from lowest to highest.

Bucket

A collection of integer values that all share a particular digit value, such as: 7, 77, 87, 27. Note, the shared value needs to be in the same decimal place.

Fast Sorting Algorithm

A sorting algorithm that has an average runtime complexity of O(NlogN) or better.

Comparison Sorting

A sorting algorithm that operates on an array of elements that can be compared to each other.

Python sorted Function

A function that takes one list argument, and then sorts the list's elements in ascending order using the less than operator and returns a new list with the sorted elements. Can take an optional keyword argument of reverse, and when true, it sorts in descending order instead.

Python Sort Function

A method for lists in Python that does an in-place sorting of the list elements in ascending order, meaning the list is modified and another list is not returned. Can take an optional keyword argument of reverse, and when true, it sorts in descending order instead.

Key Argument

An optional argument you can enter when using the sort or sorted functions. It allows you to determine how to sort the list.

Python itemgetter Function

A function that can be used to get a key from an element using an index instead of a custom key function.

Singly-Linked List

A data structure for implementing a list ADT, where each node has data and a pointer to the next node. The first node is called the head, and the last is called the tail. It is also called a positional list.

Null

A special value indicating a pointer points to nothing.

Prepend

An operation for a singly-linked list that inserts the new node before the list's head node.

InsertAfter

An operation for a singly-linked list that inserts the new node after a provided existing list node. curNode is a pointer to an existing list node, but can be null when inserting into an empty list. The algorithm considers three insertion scenarios: insert as the lists first node, insert as the lists last node, and insert as the middle node.

RemoveAfter

An operation for a singly-linked list that removes the node after the specified node. If the node given is null, it removes the first list node. It has two scenarios: removing the list's head node and removing the node after a given node.

The Data Value of a Node is Set to None if the Node is Not in a List

False

1 multiple choice option

The Node Class Has Two Data Members

True

1 multiple choice option

Is Operator

An operator used to test if two objects share the same memory location.

Doubly-Linked List

A data structure for implementing a list ADT, where each node has data, a pointer to the next node, and a pointer to the previous node. The list structure typically points to the first node and the last node. It uses pointers to both the next and previous nodes.

Positional List

A list where elements contain pointers to the next and/or previous elements in the list. A doubly-linked list is an example.

Which Characteristic of an Algorithm is Independent in Nature?

Uses an agnostic code repository

3 multiple choice options

What is Referred to as a Data Structure that Stores Subitems?

Record

3 multiple choice options

Which Term Refers to a Type of Search Algorithm?

Linear

3 multiple choice options

What Data Type do Heap Sorts Work With?

Tree-based data structure

3 multiple choice options

What Function is Used in Conjunction With a Merge Sort Algorithm?

Recursion

3 multiple choice options

Which Search Algorithm Has The Best Performance When the Data Set is Sorted?

Interval Search

3 multiple choice options

Which Format is Used to Store Data in a Hash Table?

Array

3 multiple choice options

Which Term Refers to a Data Structure That Groups Related Items of Data Together?

Record

3 multiple choice options

Which Data Structure is Used to Store Unordered Items by Mapping Each Item to a Location in an Array?

Hash Table

3 multiple choice options

What is an Advantage That a Linked List Has Over an Array?

Grows and shrinks as needed

3 multiple choice options

What Would be the Best Data Structure for a Hash Table with Simple Chaining?

Doubly-linked list

3 multiple choice options

What is the Height of this Tree?

Two

3 multiple choice options

What is the Resulting Stack When the Push(1) Function is Implemented on this Stack Yield?

1,8,9,3,5

3 multiple choice options