4.
#5
1. Does the algorithm work correctly for every undirected graph with n > 0 vertices?
No.
2. If you answer yes, indicate the algorithm’s efficiency class in the worst case; if you
answer no, explain why.
No. The algorithm incorrectly removes vertices and their connections, leading to
inaccurate connectivity results.
4.2
#1
1. Apply the DFS-based algorithm to solve the topological sorting problem for the following
digraphs:
a)
*a
*b
*d
*e
*g
*c
*f
b)
*a
*b
*c
*d
*f
*e
*g
4.3
#10
Decrease-and-conquer algorithm for generating all combinations of k items chosen from n:
Algorithm:
Base Case:
• If k = 0 or n = 0, return an empty set.
• If k = n, return the entire set.
Recursive Step:
• Generate all combinations of k items chosen from n-1.
• For each combination generated in step 2, add the nth element to the combination.
• Combine the results from steps 2 and 3.
Is it minimal-change?
Yes, this algorithm is minimal-change. Each recursive step adds or removes a single
element from the current combination.
4.4
#9
Algorithm:
* Calculate the expected sum of n numbers: n * (n + 1) / 2.
* Calculate the actual sum of the array.
* Find the missing number by subtracting the actual sum from the expected sum.
Time Complexity: O(n)
5.1
#1
a. Pseudocode:
FindLargest(array, low, high)
If low == high: return low
Mid = (low + high) // 2
Left = FindLargest(array, low, mid)
Right = FindLargest(array, mid+1, high)
Return left if array[left] > array[right] else right
b. Output: Position of the first occurrence of the largest element.
c. Recurrence Relation: T(n) = 2T(n/2) + 1. Time Complexity: Θ(n log n)
d. Comparison: Brute-force is more efficient with O(n) time.
5.2
#3
Example showing that quicksort is not a stable sorting algorithm:
Array: [2ª, 2b] (where 2ª and 2b are distinct elements with the same value 2)
Quicksort (using first element as pivot):
* Pivot: 2ª
* After partitioning: [2ª, 2b]
* Recursive calls on subarrays (none in this case)
Result: [2ª, 2b]
Even though 2ª appeared before 2b in the original array, quicksort might place 2b before 2ª
in the sorted array, violating the stability property.
If you’d like, I can provide a more detailed explanation of why quicksort is not stable. Just
let me know!
5.5
#3
Recurrence: T(n) = 2T(n/2) + O(n log n) due to sorting in each recursive call. Solution: T(n) =
Θ(n log^2 n).
6.1
#1
a. Presorting-based Algorithm:
• Sort the array of numbers in ascending order.
• Iterate through the sorted array and calculate the difference between adjacent
numbers.
• Keep track of the minimum difference found.
Efficiency Class: O(n log n) due to the sorting step.
b. Comparison:
• Presorting-based: O(n log n)
• Brute-force: O(n^2)
The presorting-based algorithm is more efficient than the brute-force algorithm.
6.4
#1
a. Bottom-up:
• Start with the given array: [1, 8, 6, 5, 3, 7, 4]
• Heapify each node starting from the last non-leaf node, ensuring the heap property
is maintained.
b. Top-down:
• Create an empty heap.
• Insert each element from the list one by one, maintaining the heap property at each
insertion.
c. Yes, the bottom-up and top-down algorithms will always yield the same heap for the
same input, as long as the heap property is correctly maintained in both cases.
6.6
#5
Algorithm:
• Generate all possible triangles.
• For each triangle:
o Check if all other points lie inside.
• Return True if such a triangle exists, False otherwise.
Time Complexity: O(n⁴)
