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
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.
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
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 any programming language) and count the while loop.
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
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?
page: 31-34
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.