Midterm 2 Flashcards
review
When it comes to job scheduling, whether to use a binary search tree or a queue depends on the specific requirements and constraints of the scheduling problem being addressed. for example in a operating systems ________ are used to manage the same priority level processes. (tasks are completed in the order they arrive.
Queue
Web browsers use ________ to let users navigate back and forth through their browsing history.
Stacks
________ are easily adaptable to implement specific scheduling algorithms like dynamic job scheduling
BST’s
For prioritized job execution where jobs should be processed based on their priority and not on their arrival time, we can use a _______ or a ______
Heap or priority queue
______ are used to manage function calls in programming languages
stacks
many backtracking algorithms utilize ______
stacks
complexity of inserting an element into a binary heap
o(log n)
complexity of removing the minimum element from a min heap
o(log n)
in binary heap if element is at index i what the the indices of the children
2i and 2i +1
which of the following can result in a stack overflow
recursive function calls with no base case
which divide and conquer algorithm has the worst case time complexity of o(n log n) regardless of the input data
heap sort
time complexity of creating a binary heap from an unordered array of n elements
o(n)
what sceneario does the quick sort algoritm do poorly
already sorted elements
how to solve hash collision
probe into another key or the new entry is added to the link list at the hash index
build max heap 1,12,9,5,6
do it
insert 25 into max heap 10,5,3,2,4
do it
what is 19 replaced with
when removing a node chose the last leaf that is unbalanced
bst with keys 1,2,3,4,5,6,7
degenerate
average time of hash table for search insert and deletion
- O(1)
worst time com for building heap
O(n)
worst time come for inserting element in binary heap
O(log n)
Check if Two Strings Are Anagrams
FUNCTION isAnagram(string1, string2)
IF length(string1) ≠ length(string2) THEN
RETURN False // Anagrams must have the same length
END IF
// Convert both strings to lowercase (if case-insensitive comparison is needed)
Convert string1 and string2 to lowercase
// Create frequency dictionaries for both strings
Create an empty dictionary freq1
Create an empty dictionary freq2
FOR each character in string1
IF character exists in freq1 THEN
Increment its count
ELSE
Add character to freq1 with a count of 1
END IF
END FOR
FOR each character in string2
IF character exists in freq2 THEN
Increment its count
ELSE
Add character to freq2 with a count of 1
END IF
END FOR
// Compare the frequency dictionaries
IF freq1 == freq2 THEN
RETURN True // Strings are anagrams
ELSE
RETURN False
END IF END FUNCTION END
Print Main Diagonal of 2D Array
BEGIN
FUNCTION printMainDiagonal(array, n)
FOR i FROM 0 TO n - 1 DO
PRINT array[i][i] // Print the element at the main diagonal
END FOR
END FUNCTION
END
Remove a node v from a linked list (can be beginning, middle or end or not in the linked list)
BEGIN
FUNCTION removeNode(head, value)
// Case 1: The list is empty
IF head == NULL THEN
PRINT “List is empty.”
RETURN head
END IF
// Case 2: The node to remove is the head node IF head.data == value THEN TEMP = head head = head.next // Update head to the next node DELETE TEMP RETURN head END IF // Case 3: Traverse the list to find the node PREVIOUS = NULL CURRENT = head WHILE CURRENT ≠ NULL AND CURRENT.data ≠ value DO PREVIOUS = CURRENT CURRENT = CURRENT.next END WHILE // Case 4: Node not found IF CURRENT == NULL THEN PRINT "Node not found." RETURN head END IF // Case 5: Remove the node PREVIOUS.next = CURRENT.next DELETE CURRENT RETURN head END FUNCTION END
