Midterm Exam Flashcards
(34 cards)
What is a priority queue?
An abstract data type similar to a queue but each element has a priority
What operations does a priority queue have?
- insert - Inserts an item with a given priority
- extractMax - Removes and returns the item with the highest priority
- peek - returns the item with the highest priority without removing it
- isEmpty - Checks if the queue is empty
Operation times for priority queue in unsorted array or list
- insert - O(1)
*extractMax - O(n) - must search for highest priority
Operation times for priority queue in sorted arrays or lists
- insert - O(n) - has to search to insert in correct position
*extractMax - O(1)
Operation times for priority queues in Binary Heaps
-Most efficient and commonly used
- insert - O(log n)
-extractMax / extractMin - O(log n)
-peek - O(1)
What is a job scheduler?
- A system that manages a queue of jobs (tasks / processes) and determines which to run based on priority.
-Operating Systems, printer queues
-A priority queue
What is a singly linked list?
A linear data structure where each element (nodes) points to the next node in the list.
Memory is not contiguous.
Can be dynamically grown / shrank.
Random access is not possible.
What is a doubly linked list?
- A data structure where nodes point both forward and backward
- Allows for traversal in both directions for easier deletions
- Slightly more complex to implement
What is hashing?
The process of converting input data into a fixed-size string of characters.
Explain how to hash
- Done using a hash function
- Always produces the same output for the same input.
What is a block chain?
A chain of ‘blocks’ (like nodes) that are linked together with a key (hash of previous node). If a block is altered, it invalidates the chain. This makes it extremely hard to commit fraud.
What does every block of a blockchain contain?
- Data
- Timestamp
- Previous block’s hash
- Current block’s hash
What is Big-Omega time complexity?
- Gives the best-case lower bound of an algorithm’s runtime or growth
- “This algorithm will take at least this long”
What is big-theta time complexity?
- Gives the exact or tight bound of an algorithm’s runtime.
-Best case, worst case, always the same.
What is little-Omega time complexity?
- Describes a strict lower bound - meaning this function will ALWAYS take at least this much time.
What is a hash table?
- A key-value data structure that lets you store data for very fast access.
- You provide a key, and the hash table gives you back the value.
- Under the hood, it uses a hash function to map the key to an index in an array
Real world applications of hash tables
- Dictionaries
-Data base indexing - Caching
-Password storage
What is chaining?
- A method of handling collisions in hash tables where each index of the hash table is a linked list of entries that hash to the same index
Open Addressing - Solving Collisions
- Handles collisions by finding another open slot in the hash table.
What is asymptotic analysis
A way of describing the behavior of an algorithm as the input size becomes very large.
- Running time depends on the size of the input
What is merge sort?
Divides the array into two halves, then sorts each halve recursively, then merges the sorted halves into one array
What is insertion sort?
- Goes through each element and compares it to the elements before it. Shifts the larger values to the right and inserts the current value into its correct position.
Heap Sort
- Comparison-based sorting algorithm that uses binary heap data structure
- Sort into a max or min heap and then swap the root node with the most or least node. Then heapify. Repeat this cycle until sorted.
What is quick sort?
- Picks a pivot and all elements less than the pivot go to the left of the array and all elements more than go to the right
