CS计算机代考程序代写 algorithm CSCI 4041

CSCI 4041
Discussion Section Notes
mo000007@umn.edu

Expectations and Resources
● Online Textbook: Introduction to Algorithms, Third Edition
● Please watch the lecture videos before the discussion sections!
● We will review what we have learned and do some programming exercises
● Grab a paper or open up any IDE (any of your choice) or Google Colab
2

Asymptotic Notation
Best-case running time: the shortest running time for any input of size n; lower
bound
Worst-case running time: the longest running time for any input of size n; upper bound
Average-case running time: probabilistic analysis to yield an expected running time, assuming that all inputs of a given size are equally likely
The “average case” is often roughly as bad as the worst case.
3

Asymptotic Notation
𝚯(n): c1 f(n) <= g(n) <= c2 f(n) asymptotically tight bound О(n): g(n) <= c2 f(n) asymptotic upper bound 𝛀(n): c1 f(n) <= g(n) asymptotic lower bound 4 Sorting Algorithms Insertion Sort Exercise: Given the insertion code (page: 18), how many while loops will execute for the following arrays: arr = [5, 2, 8, 4, 6, 1, 3, 7] arr = [1, 2, 3, 4, 5, 6, 8, 7] Write Insertion Sort (in your preference programming language) and count the while loop. 6 Insertion Sort Exercise: Given the insertion code (page: 18), how many while loops will execute for the following arrays: arr = [5, 2, 8, 4, 6, 1, 3, 7] count: 14 arr = [1, 2, 3, 4, 5, 6, 8, 7] count: 1 7 Runtime of Insertion Sort Best: 𝛀(n) Worst: О(n2) n = [100, 200, 300, ..., 10000] Average: О(n2) Runtime of Insertion Sort for random input of sizes n 8 MergeSort Divide and Conquer algorithm ● Recursively divide into subproblems (smaller size) ● Solve each subproblem ● Conquer/combine each solution back How MergeSort works? ● Divide n elements into 2 subproblems, each has n/2 elements ● Recursively sort each subproblem using merge-sort ● Merge each sorted arrays into one Question: Is it possible to divide it into 3 sub arrays to sort? 9 10 11 page: 31-34 12 MergeSort Exercise: ● The code (Merge) on page 31 sort the array in ascending order. What changes need to be made so that it will sort the array in descending order. ● Rewrite the Merge so that it does not use sentinels, instead stopping once either array L or R has had all its elements copied back to A and then copying the remainder of the other array back into A. 13 MergeSort Exercise: The code (Merge) on page 31 sort the array in ascending order. What changes need to be made so that it will sort the array in descending order. Changes need to be made: Lines 8,9: L[n1+1] = -∞, R[n2+1] = -∞ Line 13: if L[i] >= R[j]
14

MergeSort Exercise:
Rewrite the Merge so that it does not use sentinels, instead stopping once either array L or R has had all its elements copied back to A and then copying the remainder of the other array back into A.
You can either use for loop or while loop.
The idea is when either L or R runs out of elements, we need to copy the remainder of the other subarray into the remaining spots of A.
15

Runtime of MergeSort
T(n) = 𝚯(n log n)
16

Runtime of Recurrence
● n – the size of the problem
● a – the number of subproblems
● n/b – the size of each subproblem; you put 1/b size of original size into each
subproblem
● 𝚯(n) – D(n) + C(n)
● D(n) – time to divide the problem into subproblems: 𝚯(1)
● C(n) – time to combine the solutions to the subproblems into the solution to
original problem: 𝚯(n)
17

Master Theorem
page: 94
18

Master Theorem: Exercise
● Use the master method to give tight asymptotic bounds for the following recurrences.
● Show that the runtime for MergeSort, T(n) = 2T(n/2) + 𝚯(n) is 𝚯(n lg n).
19

Master Theorem: Exercise
● For all problems: a = 2, b = 4, logba = log42 = 1⁄2, nlog_4 2 = n1⁄2 = √n a) f(n) = 1; f(n) < nlog_4 2 ; 1 < √n thus case 1 ■ 𝚯(nlog_4 2) = 𝚯(√n) b) f(n) = √n; f(n) = nlog_4 2 case 2 ■ 𝚯(nlog_4 2 lg n) = 𝚯(√n lg n) c) f(n) = n; f(n) > nlog_4 2 case 3
■ 𝚯(n)
d) c = 2; f(n) > nlog_4 2 case 3
■ 𝚯(n2)
a b f(n)
● Runtime for MergeSort: T(n) = 2T(n/2) + 𝚯(n).
○ a = 2, b = 2, f(n) = n, logba = log22 = 1, nlog_2 2 = n
○ 𝚯(n lg n)
a b f(n)
20

Reference
Introduction to Algorithms, Third Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein.
21