Master this deck with 327 terms through effective study methods.
No description available
O(n)
O(n)
O(log n)
O(log n)
O(log n)
O(n^2)
O(n^2)
O(nm)
O(nm)
Worst
readonly Contact contacts = new Contacts[100];
Linked List
Linked List
Linked List
node
1. the value 2. reference to next item in the list
Node head = new Node(1); head.Next = new Node(2); head.Next.Next = new Node(3);
Singly Linked List
Doubly Linked List
Node node1 = new Node(1); Node node2 = new Node(2); Node node3 = new Node(3); node1.Next = node2; node2.Previous = node1; node2.Next = node3; node3.Previous = node2;
null
AddHead
AddTail
Find
Contains
Remove
Sorted List
Add
Data Structure
record
Array
linked list
binary tree
hash table
max heap
min heap
graph
vertex
edge
Stack
Top
Queue
Head
Tail
Doubly Ended Queue (deque)
Doubly Ended Queue (deque)
Tree
one
one
0 or more
Leaf nodes
one
two
Degree
Height
Binary Search Tree
left right
O(log n)
O(n)
Pre-order
In-order
Post-order
To create an identical copy of a tree
Sorting trees from least to greatest
To delete every node in a tree
O(n)
O(log n)
Unlinking the node
Promote the child
Move the successor's child up to the root node.
O(log n)
Associative Array
Associative Array
Hash Table
Hash Function
Stability Uniformity Security
Stability
Uniformity
Security
Reference Count
(high + low)/2 (DO NOT ROUND UP)
Yes (it's considered for garbage collection right once it's assigned to null)
Dictionaries
unique immutable
remove();
pop();
popitem();
keys();
4
Preorder Traversal (Binary Tree)
Hash Function
10
999
50
key
buckets
O(1)
unique
34
1 (201%50)
0
data structure that stores subitems, with a name associated with each subitem
a data structure that stores an ordered list of items, with each item is directly accessible by a positional index homogeneous data elements
data structure that stores *ordered* list of items in nodes, where each node stores data and has a pointer to the next node; can have multiple subitems
A data structure that consists of nodes, with one root node at the base of the tree, and two nodes (left child and right child) extending from the root, and from each child node can have no children, single left or right, or both right and left
data structure that stores *unordered* items by mapping (or hashing) each item to a location in an array
a tree that maintains the simple property that a node's key is greater than or equal to the node's childrens' keys
a tree that maintains the simple property that a node's key is less than or equal to the node's childrens' keys
data structure for representing connections among items, and consists of vertices connected by edges
part of a graph the represents an item in a graph
when inserting a new item at the beginning it causes no shift to the data
data type described by predefined user operations, such as "insert data at rear", without indication how each operation is implemented
ADT for holding ordered data
ADT which items are only inserted on or removed from the top of a stack LIFO
ADT in which items can be removed at both the front and back
a queue in which the highest-priority elements are removed first; within a priority value, the earliest arrival is removed first. common underlying DS: heap
ADT that associates (or maps) keys with values common underlying DS: has table, binary search tree
ADTs with array, linked list as common underlying DS
ADTs with linked list as their only common underlying DS
ADT operation for a queue that returns but does not remove item at the front of the queue
unique identifier that describes the object
symbol for floored division
behaves similar to a list but is immutable -- once created the els can not be chagned const array/list
sets i to 0 during the first iteration of the for loop, i to 1 during the second iteration, and finally i to 2 on the third iteration. The value within the parentheses is not included in the generated sequence.
code for every int form 5 down to -5
code for every 2nd int from 10 to 20
functional behavior depends on the argument types
used to determine the type of objects as a program executes; Python
requires the programmer to define the type of every variable and every function parameter in a program's source code; C, C++
keyword that can be used to create a user-defined type of object containing groups of related vars and fxns creates a new type of object
instantiation of a class automatically calls this method defined in the class def this is also known as the constructor
the process of an app req and being granted memory
type of operation condition ? (T)Block1: (F)Block2
type of operation for setting a var
type of operation for comparing data <, > ...
type of operation == !==
A data structured contains the name, size, and starting block/cluster address of a file. A table is used to identify the address of each piece of the file. Storage is allocated using pointers to new locations as needed.
A ______ is a "doubled-ended queue"
mid-values calculation for binary search. toCeil()
What is the effect on the object regarding garbage collection? Computing obj = new Computing(); obj = null
open to or capable of change, fickle
(adj.) not subject to change, constant
Characteristics of keys in associative dictionary data type
method used to take a value out of a dictionary
Java method used to read bytes from standard file
command that inserts object x at position index in a list
recursively breaks down a problem into two or more subproblems of the same or related type
Bubble sort && Insertion sort time complexity
Best: O(n+k) Avg: O(n+k) Worst: O(n^2) Space: O(nk) for uniformly distributed nums across a range to be sorted
for i from 0 to N -1 if a[i] > a[i+1] swap(a[i], a[i +1] end for
def shortSort(alist): exchanges = True passnum = len(alist)-1 while passnum > 0 and exchanges: exchanges = False for i in range(passnum): if alist[i]>alist[i+1]: exchanges = True temp = alist[i] alist[i] = alist[i+1] alist[i+1] = temp passnum = passnum-1
int partition( void *a, int low, int high ) { int left, right; void *pivot_item; pivot_item = a[low]; pivot = left = low; right = high; while ( left < right ) { /* Move left while item < pivot */ while( a[left] <= pivot_item ) left++; /* Move right while item > pivot */ while( a[right] > pivot_item ) right--; if ( left < right ) SWAP(a,left,right); } /* right is final position for the pivot */ a[low] = a[right]; a[right] = pivot_item; return right; }
Big-O FindMin(x, y) { if (x < y) { return x } else { return y } }
Big-O BinarySearch(numbers, N, key) { mid = 0 low = 0 high = N - 1 while (high >= low) { mid = (high + low) / 2 if (numbers[mid] < key) { low = mid + 1 } else if (numbers[mid] > key) { high = mid - 1 } else { return mid } } return -1 // not found }
O(5) has a _____ runtime complexity.
o(N log N) has a ________ runtime complexity.
O(N + N^2)
O(N)
O(n^2)
BinarySearch number of times to find num
What makes a function recursive?
a list passed to binary_search needs to be...
Starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbor exchange.
Z+ representing the distance between elements in an interleaved list; specifies the number of interleaved lists
A data structure that stores an ordered list of items, with each item is directly accessible by a positional index.
A data structure in which each node stores data and has up to two children, known as a left child and a right child.
A data structure that stores unordered items by mapping (or hashing) each item to a location in an array (or vector).
mapping each item to a location in an array (in a hash table).
handles hash table collisions by using a list for each bucket, where each list may store multiple items that map to the same bucket.
value used to map an index
each array element in a hash table ie A 100 elements hash table has 100 buckets
computes a bucket index from the items key. It will map (num_keys / num_buckets) keys to each bucket. ie... keys range 0 to 49 will have 5 keys per bucket. 50 / 10 = 5
Hash tables support fast search, insert, and remove. Requires on average O(1) Linear search requires O(N)
common has function uses this. which computes the integer remainder when dividing two numbers. Ex: For a 20 element hash table, a hash function of key % 20 will map keys to bucket indices 0 to 19.
A binary tree that maintains the simple property that a node's key is greater than or equal to the node's childrens' keys. (Actually, a max-heap may be any tree, but is commonly a binary tree). *a max-heap's root always has the maximum key in the entire tree.
Heaps are typically stored using arrays. Given a tree representation of a heap, the heap's array form is produced by traversing the tree's levels from left to right and top to bottom. The root node is always the entry at index 0 in the array, the root's left child is the entry at index 1, the root's right child is the entry at index 2, and so on.
An insert into a max-heap starts by inserting the node in the tree's last level, and then swapping the node with its parent until no max-heap property violation occurs. The upward movement of a node in a max-heap is sometime called percolating. Complexity O(logN)
Always a removal of the root, and is done by replacing the root with the last level's last node, and swapping that node with its greatest child until no max-heap property violation occurs. Complexity O(logN)
The upward movement of a node in a max-heap
Similar to a max-heap, but a node's key is less than or equal to its children's keys.
Because heaps are not implemented with node structures and parent/child pointers, traversing from a node to parent or child nodes requires referring to nodes by index. The table below shows parent and child index formulas for a heap. ie 1) parent index for node at index 12? 5 *** ((12-1) // 2) = 5 or 12 //2 -1 = 5 2) child indices for a node at index 6? 13 & 14 *** 2 * 6 + 1 = 13 and 2 * 6 + 2 = 14 **Double# and add 1, double# and add 2 Node index Parent Index Child Indices 0 N/A 1, 2 1 0 3, 4 2 0 5, 6 3 1 7, 8 4 1 9, 10 5 2 11, 12
parent_index = (node_index - 1) // 2 or node_index // 2 - 1
left_child_index = 2 * node_index + 1
right_child_index = 2 * node_index + 2
Both functions return the value in the root, but the Pop function removes the value and the Peek function does not. Pop is worst-case O(logN) and Peek is worst-case O(1). Push and pop operate have runtime O(logN). All other operations (Peek, IsEmpty, GetLength) happen in constant time O(1).
A list ADT implemented using an array. An array-based list supports the common list ADT operations, such as append, prepend, insert after, remove, and search.
If a program requires fast insertion of new data, a linked list is a better choice than an array.
A data type described by predefined user operations, such as "insert data at rear," without indicating how each operation is implemented.
An ADT for holding ordered data. Dups ok Sequence type: A mutable container with ordered elements. Underlying data structures: Array, linked list
generic class that supports different data types. declared as follows, where T is the data type.
Sequence type: An immutable container with ordered elements.
An ADT in which items are only inserted on or removed from the top of a stack. *Last-in First-Out Underlying data structures: Linked list Push(stack, x), pop(stack), peek(stack), IsEmpty(stack), GetLength(stack) *Pop & peek should not be used on a empty stack.
Example starting with stack: 99, 77 (top is 99). Push(stack, x) Inserts x on top of stack Push(stack, 44). Stack: 44, 99, 77 Pop(stack) Returns and removes item at top of stack Pop(stack) returns: 99. Stack: 77 Peek(stack) Returns but does not remove item at top of stack Peek(stack) returns 99. Stack still: 99, 77 IsEmpty(stack) Returns true if stack has no items IsEmpty(stack) returns false. GetLength(stack) Returns the number of items in the stack GetLength(stack) returns 2.
Can be implemented in Python using a class with a single LinkedList data member. The class has two methods, push() and pop(). push() adds a node to the top of the stack's list by calling LinkedList's prepend() method. *New elements are place on the top of the stack, not at the bottom of the stack. pop() removes the head of the stack's list by calling the LinkedList's remove_after() method and then returns the removed node.
Can also be implemented in Python using a class with a single LinkedList data member and class methods push() and pop(). push() adds a node to the end of the queue's list by calling LinkedList's append() method. *New elements are added to the end of a queue. The pop() method removed the queue's head node and is identical to Stack's pop() method.
An ADT in which items are inserted at the end of the queue and removed from the front of the queue. *first-in first-out ADT. Underlying data structures: Linked list, Array, Vector The Queue class' push() method uses the LinkedList append() method to insert elements in a queue. Both the Stack and Queue pop() methods operate exactly the same by removing the head element and returning the removed element.
A linear data structure, much like an array, that consists of nodes, where each node contains data as well as a link to the next node, but that does not use contiguous memory. Head and tail node The LinkedList class implements the list data structure and contains two data members, head and tail, which are assigned to nodes once the list is populated. Initially the list has no nodes, so both data members are initially assigned with None. If the node has no next node, the next data member is assigned with None, the Python term signifying the absence of a value.
In a previous section, the LinkedList class was defined, making use of the Node class. The Node class defined previously can be extended from the singly-linked list version to include a reference variable called prev that refers to the previous node in the list. When a new node is first constructed, the prev variable is assigned with None. Creating a doubly-linked node or a doubly-linked list is still the same as creating a singly-linked node and a singly-linked list. A linked list's head node does not have a previous node, thus the prev data member has a value of None.
Short for double-ended queue- an ADT in which items can be inserted and removed at both the front and back. Underlying data structures: Linked list
An ADT for storing items in which the order does not matter and duplicate items are allowed. Underlying data structures: Linked list, Array
An ADT for a collection of distinct items. (no dups!) Underlying data structures: Binary search tree, Hash table
A queue where each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority. Dups ok Underlying data structures: Heap *In addition to push and pop, a priority queue usually supports peeking and length querying. A peek operation returns the highest priority item, without removing the item from the front of the queue. Pop returns front or head item which is top priority item
A dictionary is an ADT that associates (or maps) keys with values. Underlying data structures: Binary search tree, Hash table
They are unique and immutable.
D1[key].remove(value)
returns a view object that yields (key, value) tuples.
returns a view object that yields dictionary keys.
returns a view object that yields dictionary values.
A for loop over a dict retrieves each key in the dict. ie.. for key in dictionary:
my_dict[key] Indexing operation - retrieves the value associated with key. john_grade = my_dict['John'] my_dict[key] = value Adds an entry if the entry does not exist, else modifies the existing entry. my_dict['John'] = 'B+' del my_dict[key] Deletes the key entry from a dict. del my_dict['John'] key in my_dict Tests for existence of key in my_dict if 'John' in my_dict: # ...
my_dict.clear() Removes all items from the dictionary my_dict = {'Bob': 1, 'Jane': 42} my_dict.clear() print(my_dict) {} my_dict.get(key, default) Reads the value of the key entry from the dict. If the key does not exist in the dict, then returns default. my_dict = {'Bob': 1, 'Jane': 42} print(my_dict.get('Jane', 'N/A')) print(my_dict.get('Chad', 'N/A')) 42 N/A my_dict1.update(my_dict2) Merges dictionary my_dict with another dictionary my_dict2. Existing entries in my_dict1 are overwritten if the same keys exist in my_dict2. my_dict = {'Bob': 1, 'Jane': 42} my_dict.update({'John': 50}) print(my_dict) {'Bob': 1, 'Jane': 42, 'John': 50} my_dict.pop(key, default) Removes and returns the key value from the dictionary. If key does not exist, then default is returned. my_dict = {'Bob': 1, 'Jane': 42} val = my_dict.pop('Bob') print(my_dict) {'Jane': 42}
Set, Dictionary(Map)
Priority queue
Bag, Queue, List
Deque, Stack
Append, Prepend, InsertAfter, Print, PrintReverse, Sort, Remove, Search, IsEmpty, GetLength
Push, Pop, Peak, IsEmpty, GetLength
Data type is a single-precision 32-bit IEEE 754 floating point. Use a float (instead of double) if you need to save memory in large arrays of floating point numbers.
A data type is a double-precision 64-bit IEEE 754 floating point. For decimal values, this data type is generally the default choice.
Data type is an 8-bit signed two's complement integer. The byte data type is useful for saving memory in large arrays.
0 1 2 3 4 Every integer from 0 to 4
= vs ==
*It reclaims memory from data structures implemented using linked allocations.* Python is a managed language, meaning objects are deallocated automatically by the Python runtime, and not by the programmer's code. When an object is no longer referenced by any variables, the object becomes a candidate for deallocation. Python's garbage collector will deallocate objects with a reference count of 0. However, the time between an object's reference count becoming 0 and that object being deallocated may differ across different Python runtime implementations.
An integer counter that represents how many variables reference an object. When an object's reference count is 0, that object is no longer referenced.
The process of an application requesting and being granted memory. Memory used by a Python application must be granted to the application by the operating system. When an application requests a specific amount of memory from the operating system, the operating system can then choose to grant or deny the request. Python does this automatically
is an algorithm that searches a SORTED LIST for a key by first comparing the key to the middle element in the list and recursively searching half of the remaining list so long as the key is not found.
The __init__ method, commonly known as a constructor, is responsible for setting up the initial state of the new instance.
A special value indicating a pointer points to nothing.
A data structure for representing connections among items, and consists of vertices connected by edges. Graph is a data structure that consists of following two components: A vertex (vertices) represents an item (node) in a graph. An edge represents a connection between two vertices in a graph.
item in a graph. A finite set of vertices also called as nodes V -> Number of Vertices
a connection between two vertices in a graph. A finite set of ordered pair of the form (u, v) E -> Number of Edges
Weighted Graph : The Graph in which weight is associated with the edges. Unweighted Graph : The Graph in which their is no weight associated to the edges.
Undirected Graph : The graph in which all the edges are bidirectional. Directed Graph : The graph in which all the edges are unidirectional.
In a list, each node has up to one successor. In a binary tree, each node has up to two children, known as a left child and a right child. "Binary" means two, referring to the two children.
A tree node with no children.
A node with at least one child.
A node with a child is said to be that child's parent.
include the node's parent, the parent's parent, etc., up to the tree's root.
The one tree node with no parent (the "top" node).
The link from a node to a child is called an edge. A node's depth is the number of edges on the path from the root to the node. The root node thus has depth 0. All nodes with the same depth form a tree level. A tree's height is the largest depth of any node. A tree with just one node has height 0.
every node contains 0 or 2 children.
all levels except possibly the last are completely full, and the last level has all its nodes to the left side
if all internal nodes have 2 children and all leaf nodes are at the same level.
An algorithm visits all nodes in the tree once and performs an operation on each node.
Visits all nodes in a BST from smallest to largest, which is useful for example to print the tree's nodes in sorted order. Starting from the root, the algorithm recursively prints the left subtree, the current node, and the right subtree. Left -> Root -> Right
Root -> Left -> Right
An especially useful form of binary tree, which has an ordering property that any node's left subtree keys ≤ the node's key, and the right subtree's keys ≥ the node's key. That property enables fast searching for an item, as will be shown later. *When searching, search always starts at the root
Stack: 99, 77, 66 The pop() removes the head of the stack's list by calling the LinkedList's remove_after() method and then returns the removed node. Pop(stack) returns: 99. Stack: 77 Queue: queue: 43, 12, 77 The pop() method removed the queue's head node and is identical to Stack's pop() method. Pop(queue) returns: 43. Queue: 12, 77 Priority Queue: Removes and returns the item at the front of the queue, which has the highest priority.
Stack: numStack 7, 5 push() adds a node to the top of the stack's list by calling LinkedList's prepend() method. *New elements are place on the top of the stack, not at the bottom of the stack. push(numStack, 8) = 8, 7, 5 Queue: queue: 43, 12, 77 push() adds a node to the end of the queue's list by calling LinkedList's append() method. *New elements are added to the end of a queue. Push(queue, 56). Queue: 43, 12, 77, 56 Priority Queue: The priority queue push operation inserts an item such that the item is closer to the front than all items of lower priority, and closer to the end than all items of equal or higher priority.
We write O(logN) not O(log10N) or O(log^2N)
A sorting algorithm that has an average runtime complexity of O(N logN) or better.
**Look for something that swaps so the result can "bubble" to the top. *best used when the data is small Sorting algorithm that iterates through a list, comparing and swapping adjacent elements if the second element is less than the first element. Bubble sort uses nested loops. Given a list with N elements, the outer i-loop iterates N times. Because of the nested loops, bubble sort has a runtime of O(N2). Bubble sort is often considered impractical for real-world use because many faster sorting algorithms exist. Figure 11.20.1: Bubble sort algorithm. BubbleSort(numbers, numbersSize) { for (i = 0; i < numbersSize - 1; i++) { for (j = 0; j < numbersSize - i - 1; j++) { if (numbers[j] > numbers[j+1]) { temp = numbers[j] numbers[j] = numbers[j + 1] numbers[j + 1] = temp }}
**Look for something that distributes the values into "buckets" where they are individually sorted. **Bucket sort is mainly useful when input is uniformly distributed over a range. The bucket index is calculated as ⌊number∗(N−1)/M⌋ N =number of buckets M =maximum value of M ie 71 and 99 placed in the same bucket? 71 bucket 2 71 * (5-1) // 99 = 2 BucketSort(numbers, numbersSize, bucketCount) { if (numbersSize < 1) return buckets = Create list of bucketCount buckets // Find the maximum value maxValue = numbers[0] for (i = 1; i < numbersSize; i++) { if (numbers[i] > maxValue) maxValue = numbers[i] } // Put each number in a bucket for each (number in numbers) { index = floor(number * (bucketCount - 1) / maxValue) Append number to buckets[index] } // Sort each bucket for each (bucket in buckets) Sort(bucket) // Combine all buckets back into numbers list result = Concatenate all buckets together Copy result to numbers }
**Look for something that continually splits a list in half. A sorting algorithm that divides a list into two halves, recursively sorts each half, and then merges the sorted halves to produce a sorted list. The recursive partitioning continues until a list of 1 element is reached, as list of 1 element is already sorted. mergedNumbers[mergePos] = numbers[rightPos]
**Look for keywords "Pivot" and/or "Split" selects the kth smallest element in a list. Ex: Running quickselect on the list (15, 73, 5, 88, 9) with k = 0, returns the smallest element in the list, or 5. The best case and average runtime complexity of quickselect are both O(N). In the worst case, quickselect may sort the entire list, resulting in a runtime of O(N2). Figure 11.21.1: Quickselect algorithm. // Selects kth smallest element, where k is 0-based Quickselect(numbers, first, last, k) { if (first >= last) return numbers[first] lowLastIndex = Partition(numbers, first, last) if (k <= lowLastIndex) return Quickselect(numbers, first, lowLastIndex, k) return Quickselect(numbers, lowLastIndex + 1, last, k) }
Best to worst O(1) O(log n) O(n) O(n log n) O(n^2) O(2^n) O(nl)
Selection sort O(N2) Not fast Insertion sort O(N2) Not fast Shell sort O(N1.5) No fast Quicksort O(NlogN) fast Merge sort O(NlogN) fast Heap sort O(NlogN) fast Radix sort O(N) fast (integer only)
10 buckets
Stack Queue Deque (Double-Ended Queue) List Priority Queue Set Map (or Dictionary)
Array Linked List Heap Binary Tree Hash Table Graph
O(n^2) - S
O(n^2) - I
O(n^2) - B
O(n^2) - Q
O(n log n) - M
O(n log n) - H
O(nk), where k is the # of digits in the largest number in the array.
Look for something that swaps so the result can "bubble" to the top.
Look for something that distributes the values into "buckets" where they are individually sorted.
Look for something that continually splits a list in half.
Look for the keyword "pivot".
A data structure that stores a fixed-size sequential collection of elements of the same type. Elements in an array can be accessed using their index, which starts from 0.
A data structure consisting of a sequence of nodes, each containing an element and a reference to the next node. Linked lists can be used to implement dynamic data structures, where the size of the data changes frequently.
A binary tree data structure where each node has at most two children, and the left child is always less than its parent, while the right child is always greater than its parent. Binary search trees are commonly used for searching and sorting operations.
A data structure that uses a hash function to map keys to indices of an array, where values associated with the keys can be stored. Hash tables provide constant-time average case for basic operations such as insert, delete, and search.
A binary tree data structure where the parent nodes are always greater (or less) than their children. Heaps are used to implement priority queues, where the highest (or lowest) priority element is always at the root of the heap.
Function: An ordered collection of elements of the same or different data types. Distinctions: Elements are ordered and can be accessed using an index. Underlying Data Structure: Dynamic array. Basic Commands and Syntax: [] is used to create a list. append() adds an element to the end of the list. pop() removes and returns the last element.
Function: An ordered collection of elements of the same or different data types. Distinctions: Tuples are immutable, meaning their values cannot be changed. Underlying Data Structure: Dynamic array. Basic Commands and Syntax: () is used to create a tuple. Indexing and slicing are used to access tuple elements.
Function: A collection of elements that follows the Last-In-First-Out (LIFO) principle. Distinctions: Elements are added and removed from the top of the stack. Underlying Data Structure: Dynamic array or linked list. Basic Commands and Syntax: append() adds an element to the top of the stack. pop() removes and returns the last element.
Function: A collection of elements that follows the First-In-First-Out (FIFO) principle. Distinctions: Elements are added to the rear and removed from the front of the queue. Underlying Data Structure: Linked list. Basic Commands and Syntax: append() adds an element to the rear of the queue. pop(0) removes and returns the first element.
Function: A collection of elements that supports adding and removing elements from both ends. Distinctions: Deque stands for "double-ended queue". Underlying Data Structure: Linked list. Basic Commands and Syntax: append() adds an element to the rear of the deque. appendleft() adds an element to the front of the deque. pop() removes and returns the last element. popleft() removes and returns the first element.
Function: An unordered collection of elements which may include duplicates. Distinctions: Elements can be added and removed, but the order is not preserved. Underlying Data Structure: Hash table. Basic Commands and Syntax: add() adds an element to the bag. remove() removes an element from the bag.
Function: An unordered collection of unique elements. Distinctions: Sets do not allow duplicate elements. Underlying Data Structure: Hash table. Basic Commands and Syntax: set() creates a set. add() adds an element to the set. remove() removes an element from the set.
Function: A collection of elements where each element has a priority associated with it. Distinctions: Elements are ordered based on priority, not insertion order. Underlying Data Structure: Heap. Basic Commands and Syntax: heapq module is used to implement priority queue. heappush() adds an element to the heap. heappop() removes and returns the element with the highest priority.
Function: A collection of key-value pairs. Distinctions: Keys are unique and used to access the corresponding value. Underlying Data Structure: Hash table. Basic Commands and Syntax: {} is used to create a dictionary. keys() returns a list of all the keys. values() returns a list of all the values. items() returns a list of all the key-value pairs.
Description: In programming, the = sign is used to assign a value to a variable, while the == sign is used to compare two values. Example:x = 5 assigns the value 5 to the variable x.if (x == 5): checks if the value of x is equal to 5.
Description: The process of reserving memory space for an object in a program. Example: In Java, memory is allocated using the new keyword. Example: MyClass obj = new MyClass(); allocates memory for an object of the MyClass class.
Description: A memory allocation technique where memory is allocated in linked nodes. Each node contains a pointer to the next node. Example: Linked lists are a data structure that uses linked allocation. Each node in the linked list contains a pointer to the next node.
Description: A memory allocation technique where memory is allocated in a sequential manner. Example: Arrays are a data structure that uses sequential allocation. Memory is allocated for all the elements of the array in a sequential manner.
Description: A variable that stores the memory address of another variable. Example: In C++, we use pointers to access memory directly. Example: int *ptr; declares a pointer variable that can store the memory address of an integer.
Description: A search algorithm that finds the position of a target value in a sorted array by repeatedly dividing the search interval in half. Example: To conduct a binary search on a list: Find the middle element of the list. Return its position if the middle element is equal to the target value. Otherwise, repeat the search in the appropriate half of the list.
Description: A special method is used to initialize an object when it is created. Example: In Java, the constructor method has the same name as the class. Example: MyClass obj = new MyClass(); calls the constructor method of the MyClass class.
Description: A linear data structure that follows the Last In, First Out (LIFO) principle. Operations: Push: Adds an element to the top of the stack. Pop: Removes the top element from the stack and returns it. Peek: Returns the top element of the stack without removing it.
Description: A linear data structure that follows the First In First Out (FIFO) principle. Operations: Enqueue: Adds an element to the back of the queue. Dequeue: Removes the front element from the queue and returns it. Peek: Returns the front element of the queue without removing it.
Description: A specialized queue where elements are dequeued based on their priority. Operations: Enqueue: Adds an element to the priority queue based on its priority. Dequeue: Removes the highest-priority element from the priority queue and returns it. Peek: Returns the highest-priority element of the priority queue without removing it.
Description: The process of visiting each node in a tree in a specific order. Types: Inorder Traversal: Visits the left subtree, then the current node, and finally the right subtree. Preorder Traversal: Visits the current node, then the left subtree, and finally the right subtree. Postorder Traversal: Visits the left subtree, then the right subtree, and finally the current node.
Description: A collection of key-value pairs where each key maps to a value. Operations: Get: Returns the value associated with a specified key. Set: Sets the value associated with a specified key. Delete: Removes a key-value pair from the dictionary.
Description: A data structure that uses hashing to store and retrieve key-value pairs efficiently. Components: Hashing: Converts a key into an index to access a value. Chaining: Handles collisions by storing multiple key-value pairs in the same index. Hash Key: Result of hashing a key to determine its index. Modular Arithmetic: Uses the remainder of a key divided by table size for hashing.
Description: A data structure that stores a fixed-size sequence of elements of the same type in contiguous memory locations. Operations: Insertion: Adding elements at the end (O(1)); adding in the middle/beginning (O(n)). Deletion: Removing elements at the end (O(1)); removing in the middle/beginning (O(n)). Indexing: Access elements using their index.
Description: A sequence of nodes, each containing an element and a reference to the next node. Operations: Insertion: Add elements at the beginning or end (O(1)). Middle insertion takes O(n). Deletion: Delete known nodes in O(1). Traversing to delete takes O(n).
Description: Similar to a linked list but with references to both the previous and next nodes. Operations: Insertion and Deletion are similar to linked lists but allow bidirectional traversal.
Description: A specialized tree structure used to maintain the maximum or minimum element in a collection. Types: Min-Heap: Parent value ≤ children. Max-Heap: Parent value ≥ children. HeapList: Represented as a list where 2i and 2i+1 are children.
Typically refers to the array representation of a heap data structure, where the heap (either a min-heap or a max-heap) is stored as a list (array) for efficient computation. The complete binary tree structure of a heap makes it very convenient to store the heap as a linear array or list because the parent-child relationships can be easily calculated using indices.
Sequence: Visit the left subtree, then the current node (root), and finally the right subtree. Order: Left → Root → Right Use Case: Produces nodes of a binary search tree (BST) in sorted order. Traversal Steps: Visit the left subtree (2). Visit root (1). Visit the right subtree (3). Result: 2, 1, 3
Sequence: Visit the current node (root) first, then the left subtree, and finally the right subtree. Order: Root → Left → Right Use Case: Useful for creating a replica of the tree or for prefix expressions. Traversal Steps: Visit root (1). Visit the left subtree (2). Visit the right subtree (3). Result: 1, 2, 3
Sequence: Visit the left subtree, then the right subtree, and finally the current node (root). Order: Left → Right → Root Use Case: Useful for deleting a tree (deletes children before the parent) or evaluating postfix expressions. Traversal Steps: Visit the left subtree (2). Visit the right subtree (3). Visit root (1). Result: 2, 3, 1
Which abstract data type (ADT) allows operations at one end only?
Which Python list function removes the first instance of the specified element?
By iterating through the sorted list while placing each value into its correct sorted position within the list.
Which tool in Python is used to implement a deque ADT?
Which loop type will always be done at least once?
How would a strongly typed language create an integer variable?
Which component of a case statement would be considered a fall back in case no other parameters are met?
It consists of variables and methods.
Which format is used to store data in a hash table?
Which factor takes the ability to easily update an algorithm into consideration?
What is a high-level consideration in an algorithm's design?
Which review of an algorithm happens after implementation?
Which data type do heap sorts work with?
Which search algorithm has the best performance when the data set is sorted?
Unordered: Keys are not stored in any specific order (though modern Python maintains insertion order). Mutable: You can add, update, or delete key-value pairs. Unique Keys: Keys must be unique; duplicate keys overwrite previous values. Fast Lookups: Dictionary operations are generally very efficient.
Push: Add an element to the top of the stack. Pop: Remove the top element from the stack. Peek/Top: View the top element without removing it. IsEmpty: Check if the stack is empty. Size: Get the number of elements in the stack.
Enqueue: Add an element to the rear of the queue. Dequeue: Remove an element from the front of the queue. Peek/Front: View the element at the front of the queue without removing it. IsEmpty: Check if the queue is empty. Size: Get the number of elements in the queue.
EnqueueFront/PushFront: Add an element to the front of the deque. EnqueueRear/PushBack: Add an element to the rear of the deque. DequeueFront/PopFront: Remove an element from the front of the deque. DequeueRear/PopBack: Remove an element from the rear of the deque. PeekFront: View the front element without removing it. PeekRear: View the rear element without removing it. IsEmpty: Check if the deque is empty. Size: Get the number of elements in the deque.
Enqueue: Add an element based on its priority. Dequeue: Remove the element with the highest priority. Peek: View the highest-priority element without removing it. IsEmpty: Check if the priority queue is empty. Size: Get the number of elements in the priority queue.
Insert: Add an element at a specific position. Append/Add: Add an element to the end of the list. Remove/Delete: Remove an element by its value or position. Get/Access: Retrieve an element by its position. IndexOf/Search: Find the position of an element by its value. Sort: Arrange elements in a specific order (ascending or descending). Reverse: Reverse the order of elements in the list.
Set/Add: Add a key-value pair to the dictionary. Get: Retrieve the value associated with a key. Delete/Remove: Remove a key-value pair by its key. Keys: Get a list of all keys in the dictionary. Values: Get a list of all values in the dictionary. Contains: Check if a specific key exists in the dictionary.