data structure

COMP 3270 Homework 3 Solutions 1. (7 points) Heapsort Show the array A after the algorithm Min-Heap-Insert(A, 6) is operates on the Min Heap implemented in array A=[6, 8, 9, 10, 12, 16, 15, 13, 14, 19, 18, 17]. In order to solve this problem you have to do some of the thinking assignment on

Introduction 1 Sorting A universal problem! Many applications often incorporate sorting There is a wide variety of sorting algorithms, and they use rich set of techniques. 2 Sorting algorithm Insertion, Bubble, Selection sorts: Non-recursive In place: only a constant number of additional storage locations (for local variables) are used outside the array. Merge sort :

Correctness Proofs Reading Assignments By now you should have already read Chapter 1 Now read Chapter 2 Section 2.1 Computational Problem Solving Problems Designing solution strategies Developing algorithms Writing algorithms that implement the strategies Understand existing algorithms and modify/reuse Understanding an algorithm by simulating its operation on an input Ensuring/proving correctness Analyzing and comparing performance/efficiency

Introduction Ch.23. Minimum spanning tree Read the entire chapter, but omit proof of Theorem 23.1 2 Click to edit Master text styles Second level Third level Fourth level Fifth level 3 23.1 Growing a minimum spanning tree What is a safe edge? 1. One that has the smallest cost among edges not yet in the