data structure

CMPSC 465 Data Structures & Algorithms Fall 2021 and HW 3 1. (20 pts.) Problem 1 (a) After Build-Heap: [1,5,2,7,6,4,3,9,8,10] After 1st iteration of the loop: [2,5,3,7,6,4,10,9,8,1] After 2nd iteration of the loop: [3,5,4,7,6,8,10,9,2,1] After 3rd iteration of the loop: [4,5,8,7,6,9,10,3,2,1] (b) Proof: Assume the element at position bn2c is an internal node, not a […]

CMPSC 465 Data Structures & Algorithms Fall 2021 and Worksheet 1 Monday, Aug 30, 2021 1. Compare Growth Rates. Order the following functions by asymptotic growth: (i) f1(n) = 3n (ii) f2(n) = n 1 3 (iii) f3(n) = 12 (iv) f4(n) = 2log2 n (v) f5(n) = √ n (vi) f6(n) = 2n (vii)

CMPSC 465 Data Structures & Algorithms Fall 2021 and HW 4 Due September 27, 10:00 pm Instructions: You are encouraged to solve the problem sets on your own, or in groups of three to five people, but you must write your solutions strictly by yourself. You must explicitly acknowledge in your write-up all your collaborators,

CSC373H Lecture 3 CSC373H Lecture 3 September 22, 2021 Single-Source Shortest Paths Today we’ll talk about the Single-Source Shortest Paths (SSSP) problem. ▶ Input: connected, directed, weighted graph G = (V ,E ), with n vertices and m edges; and start vertex s ▶ Each edge e has nonnegative weight w(e) ▶ Output: shortest path

CMPSC 465 Data Structures & Algorithms Fall 2021 and Worksheet 4 Monday, September 20, 2021 1. Recurrence Relations Solve the following recurrence relations and give a bound for each of them. Give a short justification for each of your answers. a) T (n) = 4T (n/2)+42n b) T (n) = 2T (2n/3)+T (n/3)+n2 c) T

CMPSC 465 Data Structures & Algorithms Fall 2021 and Worksheet 2 Solution Monday, September 6, 2021 1. Growth Rate. Sort the following functions based by their growth rate. (You may assume all loga- rithms have base 2.) ( √ 2)logn, n2, n!, (logn)!, (32) n, log2 n, n3, log(n!), 22 n , n 1 logn

CMPSC 465 Data Structures & Algorithms Fall 2021 and Worksheet 3 Monday, September 13, 2021 1. Heap Sort. Please consider the following array A = [1,2,9,5,6,10]. Suppose we remove the element at position 0 of the heap. How does the resulting heap look? Write both the array and tree representation of the heap. Solution: Our

CMPSC 465 Data Structures & Algorithms Fall 2021 and HW 2 Due September 13, 10:00 pm Instructions: You are encouraged to solve the problem sets on your own, or in groups of three to five people, but you must write your solutions strictly by yourself. You must explicitly acknowledge in your write-up all your collaborators,

CMPSC 465 Data Structures & Algorithms Fall 2021 and Quiz 1 Recitation Section: Monday, Aug 30, 2021 Student Name: PSU Email ID: 1. (2 pts.) Worst case time complexity of insertion sort where position of the data to be inserted is cal- culated using binary search is: (a) O(n) (b) O(n2) (c) O(n · logn)