DS 8001 Divide And Conquer Exercises PDF
Document Details
Uploaded by ManageableMeerkat
Toronto Metropolitan University
M Cevik
Tags
Summary
This document contains exercises on divide and conquer algorithms and recurrence relations. It covers topics like recurrence complexity calculations, Towers of Hanoi, MergeSort, and inversion counting. The exercises are suitable for undergraduate-level computer science students.
Full Transcript
LECTURE 2: DIVIDE AND CONQUER EXERCISES DS 8001 E X 1: R ECURRENCE C OMPLEXITY C ALCULATIONS □ Solve for the following recurrences (e.g., using guess and check, induction): (a) T(n) = T(n − 5) + c (b) T(n) = T(n/5) + c (c) T(n) = 2T(n/2) + c (d) T(n) = c...
LECTURE 2: DIVIDE AND CONQUER EXERCISES DS 8001 E X 1: R ECURRENCE C OMPLEXITY C ALCULATIONS □ Solve for the following recurrences (e.g., using guess and check, induction): (a) T(n) = T(n − 5) + c (b) T(n) = T(n/5) + c (c) T(n) = 2T(n/2) + c (d) T(n) = cn + T(n/4) + T(3n/4) M Cevik DS 8001 - Divide and Conquer Exercises 2/7 E X 2: R ECURRENCE C OMPLEXITY C ALCULATIONS □ Find the complexity of below functions using recurrence relations (i.e., using T(n) function) def recursiveF1(n,m,o): if n
