Assign #1 Due Date: Sunday 21/03/2021 by 11:00 pm (on MOODLE) Notes: 1. The assignment should be submitted by the due date a6d time (Late Assignments will not be accepted for any reason). 2. The assignments are individual effort and copying the assignment will be treated as a cheating attempt, which may lead to FAILING the course. Consider the following sorting algorithms. 1- Heap sort 2- Quick sort A) Given the bellow array, trace the recursion function of the two sorting algorithms, and show all the changes that happens to the array during recursion process. Follow the slides in Lecture 3-Insertion sort and merge sort.pdf" from slide 78 till 113. And do exactly the same. A = 16 4 10 14 1932 8 7 B) Use Divide-and-conquer technique to design, analyze and implement an algorithm that calculates the summation of an array of n random integers. Requirements Algorithm design: Design recursive algorithms using divide-and- conquer technique and write the pseudocode. Algorithm analysis: Analyze the time complexity for the algorithms using O-notation (use tree method and master theorem). Implementation: Implement the algorithm using Python. Assignment submission: Submit part A as a PowerPoint file. Submit part B as (Python file.py, word file that explains your algorithm and time complexity analysis). Assign #1 Due Date: Sunday 21/03/2021 by 11:00 pm (on MOODLE) Notes: 1. The assignment should be submitted by the due date a6d time (Late Assignments will not be accepted for any reason). 2. The assignments are individual effort and copying the assignment will be treated as a cheating attempt, which may lead to FAILING the course. Consider the following sorting algorithms. 1- Heap sort 2- Quick sort A) Given the bellow array, trace the recursion function of the two sorting algorithms, and show all the changes that happens to the array during recursion process. Follow the slides in Lecture 3-Insertion sort and merge sort.pdf" from slide 78 till 113. And do exactly the same. A = 16 4 10 14 1932 8 7 B) Use Divide-and-conquer technique to design, analyze and implement an algorithm that calculates the summation of an array of n random integers. Requirements Algorithm design: Design recursive algorithms using divide-and- conquer technique and write the pseudocode. Algorithm analysis: Analyze the time complexity for the algorithms using O-notation (use tree method and master theorem). Implementation: Implement the algorithm using Python. Assignment submission: Submit part A as a PowerPoint file. Submit part B as (Python file.py, word file that explains your algorithm and time complexity analysis)
