CS 4120/5120 Spring 2017Homework 2_______ / 50 pointsDUE MONDAY FEBRUARY 13, 2017 7:30PMTurn in both an electronic copy on Canvas and a printed copy in lecture.Name______________________________________ID______________________________________1.[5 pts] Draw the recursion tree (see Fig 2.5, page 38 in the book for an example) for the recurrence:T(n) = θ(1) if n = 1= 2T(n/2) + n2if n > 11
CS 4120/5120 Spring 2017Homework 22.[2 pts] Use the tree from Problem 1 to guess a solution to the recurrence.3.[5 pts] Use the substitution method to solve the recurrence based on your guess in Problem 2.4.[5 pts] Use the Master Method to solve the recurrence in Problem 1.2
CS 4120/5120 Spring 2017Homework 25.[5 pts] Use MERGE-SORT algorithm (available on Page 34 in textbook) to sort the following list:5 8 2 1 6 6 4 2 3Show the steps (One example is illustrated in Fig 2.4 on Page 35 in the textbook).3
Found this document preview useful?
Related Documents
Data Structure and Algorithms - Desklib Online Librarylg...
