1. Write an algorithm (in readable pseudocode) that finds the beginning and end points (the index...

Transcribed Image Text:

1. Write an algorithm (in readable pseudocode) that finds the beginning and end points (the index in the sequence) of the longest string of repeating digits in a sequence of random digits (0...9) of length n. If there is more than one sequence of the same length, return the first one. If there are no repeating digits, return both indices as 1. 2. Write an algorithm (pseudocode again) that takes an unsorted list of n real numbers and finds the two numbers (their actual values) that are closest together. Calculate the total number of comparisons (leaving out any loop index operations) and use that to identify what order time complexity this algorithm is 3. Demonstrate a proof of the following statements using the definition of big-O a. If f(x) is O(g₁ (x)) and f_2 (x) is 0(92(x)) then (fi + f₂)(x) is 0(max(191 (x)1.192 (x))) b. If f(x) is 0 (g(x)) and f2(x) is 0(92(x)) then (fi fa)(x) is 0(91(x)92(x)) 4. Using the definition of big-O and specific values of C and k a. Show that n! is NOT O(2") b. Show that (logn)2 IS O(n) where log is base 2 5. Show that f(x) = 2x2-x+3 is e(x2) by finding C₁, C₂ and k in the definition of big-Theta 6. Using the worst case time and assuming a sorting algorithm no better than O(n log n) find the time complexity (and explain) of the greedy scheduling algorithm based on earliest end times. 6. Using the worst case time and assuming a sorting algorithm no better than O(n log n) find the time complexity (and explain) of the greedy scheduling algorithm based on earliest end times. procedure schedule(s1, s2, el, e2, ... sn: start times, .... en: end times) sort talks by finish time and reorder so that el Se2 s... Sen S:= 0 for j := 1 to n if talk j is compatible with S then S:=SU {talk j} return S 1. Write an algorithm (in readable pseudocode) that finds the beginning and end points (the index in the sequence) of the longest string of repeating digits in a sequence of random digits (0...9) of length n. If there is more than one sequence of the same length, return the first one. If there are no repeating digits, return both indices as 1. 2. Write an algorithm (pseudocode again) that takes an unsorted list of n real numbers and finds the two numbers (their actual values) that are closest together. Calculate the total number of comparisons (leaving out any loop index operations) and use that to identify what order time complexity this algorithm is 3. Demonstrate a proof of the following statements using the definition of big-O a. If f(x) is O(g₁ (x)) and f_2 (x) is 0(92(x)) then (fi + f₂)(x) is 0(max(191 (x)1.192 (x))) b. If f(x) is 0 (g(x)) and f2(x) is 0(92(x)) then (fi fa)(x) is 0(91(x)92(x)) 4. Using the definition of big-O and specific values of C and k a. Show that n! is NOT O(2") b. Show that (logn)2 IS O(n) where log is base 2 5. Show that f(x) = 2x2-x+3 is e(x2) by finding C₁, C₂ and k in the definition of big-Theta 6. Using the worst case time and assuming a sorting algorithm no better than O(n log n) find the time complexity (and explain) of the greedy scheduling algorithm based on earliest end times. 6. Using the worst case time and assuming a sorting algorithm no better than O(n log n) find the time complexity (and explain) of the greedy scheduling algorithm based on earliest end times. procedure schedule(s1, s2, el, e2, ... sn: start times, .... en: end times) sort talks by finish time and reorder so that el Se2 s... Sen S:= 0 for j := 1 to n if talk j is compatible with S then S:=SU {talk j} return S

Answer rating: 100% (QA)

1 Algorithm to find the longest string of repeating digits LongestRepeatingDigitssequence maxLen 0 s... View the full answer