undefined
CSC 320 S21 Homework 1 - Due by Monday February 8, 2021 Chapter 1 - 1. Use Euclid's algorithm to find ged(25959, 11713) a. Show your steps b. (extra credit) Run it in Python and submit the script and the running result 2. Describe algorithm for binary search in a given sorted list. a. In English b. In Psudocode c. Compare binary search and linear (sequential) search 3. Consider the sorting algorithm listed on Page 23 Exercise 1.3. #1. a. Apply this algorithm to sorting the list 15, 65, 81, 39, 65, 21, 42, 23 b. Is this algorithm stable? c. Is it in-place? 4. Give two representations for the following graph: 5. Find the most appropriate data structures for the following applications: a. Eval n arithmetic expression in designing a calculator b. Stand in line to check out in a store C. Schedule requested jobs with their assigned priorities Chapter 2 - 1. Indicate whether the first function of each of the following pairs has a smaller, same, or larger order of growth (to within a constant multiple) than the second function. Explain why briefly, a. (1+1)(n+1) and 2000n2 b. 10001 and 0.0017 c. log', n and log, n? d. 2" and 3" 2. For each of the following functions, indicate the class (g(n)) the function belongs to. (Use the simplest g(n) possible in your answers.) Briefly prove your assertions. a. (n+1) b. c. d. 4" + 3+1 3. Order the following functions according to their order of growth (from the lowest to the highest): 10%; (1-1)(1-2); (n-2)!; Ig(n+ 100)":22: 0.001n* + 3+1; In'n. ; 3" 4. Consider the following algorithm. ALGORITHM Puzzle (A[O..n - 1; 0..9 - 1]) //Input: A matrix AlO.. - 1:0. .n - 1] of real numbers //Output: ??? for i ro to n - 2 do for ju i + 1 to n - 1 do swap (Ali, jl, Alj, il) return A CSC 320 S21 Homework 1 - Due by Monday February 8, 2021 Chapter 1 - 1. Use Euclid's algorithm to find ged(25959, 11713) a. Show your steps b. (extra credit) Run it in Python and submit the script and the running result 2. Describe algorithm for binary search in a given sorted list. a. In English b. In Psudocode c. Compare binary search and linear (sequential) search 3. Consider the sorting algorithm listed on Page 23 Exercise 1.3. #1. a. Apply this algorithm to sorting the list 15, 65, 81, 39, 65, 21, 42, 23 b. Is this algorithm stable? c. Is it in-place? 4. Give two representations for the following graph: 5. Find the most appropriate data structures for the following applications: a. Eval n arithmetic expression in designing a calculator b. Stand in line to check out in a store C. Schedule requested jobs with their assigned priorities Chapter 2 - 1. Indicate whether the first function of each of the following pairs has a smaller, same, or larger order of growth (to within a constant multiple) than the second function. Explain why briefly, a. (1+1)(n+1) and 2000n2 b. 10001 and 0.0017 c. log', n and log, n? d. 2" and 3" 2. For each of the following functions, indicate the class (g(n)) the function belongs to. (Use the simplest g(n) possible in your answers.) Briefly prove your assertions. a. (n+1) b. c. d. 4" + 3+1 3. Order the following functions according to their order of growth (from the lowest to the highest): 10%; (1-1)(1-2); (n-2)!; Ig(n+ 100)":22: 0.001n* + 3+1; In'n. ; 3" 4. Consider the following algorithm. ALGORITHM Puzzle (A[O..n - 1; 0..9 - 1]) //Input: A matrix AlO.. - 1:0. .n - 1] of real numbers //Output: ??? for i ro to n - 2 do for ju i + 1 to n - 1 do swap (Ali, jl, Alj, il) return A
