ARIZONA STATE UNIVERSITY
CSE 310 — Data Structures and Algorithms — Fall 2017 Assignment #2
Available Friday, 09/08/2017; due electronically Friday, 09/29/2017
Submit electronically, before midnight on Friday, 09/29/2017, using the submission link on Blackboard for Assignment #2, a single file named yourFirstName-yourLastName.zip, containing
1. 2.
1
1.1
1.2
a pdf file with your solution to this assignment (a .doc or .docx file is also acceptable, but .pdf is preferred);
a folder named Code with your source code to the programming question and a Makefile (more instruc- tions below).
Number of Levels in a Binary Tree (20 points)
Design a divide-and-conquer algorithm for computing the number of levels in a binary tree. In par- ticular, the algorithm should return 0 and 1 for the empty and single-node trees respectively. Please provide the pseudocode for your algorithm. What is the running time of your algorithm in the worst case using O() notation?
Design a divide-and-conquer algorithm for computing the number of levels in a COMPLETE binary tree. In particular, the algorithm should return 0 and 1 for the empty and single-node trees respectively. Please provide the pseudocode for your algorithm. What is the running time of your algorithm in the worst case using O() notation? (A complete binary tree refers to the type of binary trees where every level except the last level is completely filled and all the nodes are left justified. An example of the complete binary tree is shown below.)
Figure 1: An Example of Complete Binary Tree.
Heaps and Heapsort (25 points)
Is the sequence < 23, 17, 14, 6, 13, 10, 1, 5, 7, 12 > a max-heap? Why or why not? IllustratetheoperationofMax-Heapify(A;3)onthearrayA=<27,17,3,16,13,10,1,5,7,12,4,8,9,10>,
using the binary trees as we did in class.
Illustrate the operation of Build-Max-Heap(A) on the array A =< 5, 3, 17, 10, 84, 19, 6, 22, 9 >, using the binary trees as we did in class.
2
2.1 2.2
2.3
1
2.4 You are given a list of numbers for which you need to construct a min-heap. How would you use an algorithm for constructing a max-heap to construct a min-heap? Explain in your own words.
2.5 Argue the correctness of Heapsort using the following loop invariant: At the start of each iteration of the for loop, the subarray A[1, . . . , i] is a max-heap containing the i smallest elements of A[1, . . . , n], and the subarray A[i+1,…,n] contains the n−i largest elements of A[1,…,n].
3 Quicksort (15 points)
Suppose we have three arrays, each with 7 elements, and we want to use Quicksort (using the last element in the array as the pivot) to sort each array (from the smallest to the largest).
• Array 1: (1, 3, 4, 6, 8, 10, 12).
• Array 2: (1, 4, 3, 6, 10, 8, 6).
• Array 3: (12, 10, 8, 6, 4, 3, 1).
Which array(s) has the best-case running time, and which array(s) has the worst-case running time? Justify your answers.
4 Programming Question (40 points) 4.1 Instructions
You need to write the code by yourself. Your implementation must use C/C++ and your code must run on the Linux machine general.asu.edu. Please refer to the programming guide (available under the Assignments folder on Blackboard) for using the general.asu.edu server, as well as compiling and running C/C++ code under Linux.
For this question, you need to provide a Makefile that compiles your program to an executable named a2 that runs on the Linux machine general.asu.edu. Our TA will write a script to compile and run all student submissions; therefore, executing the command make in the Code folder must produce the executable a2 also located in the Code folder.
4.2 Requirements
In this question, you will write a serial program that executes a sequence of commands that operate on individual files. Valid commands include:
• Start Name, where Name is a character string of maximum length 20 alphabetic characters representing the name of the data file (Name.txt). The structure of Name.txt is an integer N indicating the total number of data entries contained in this file, followed by N additional lines of integers (the actual data entries). This command first reads N from the file Name.txt, dynamically allocates an array of integers of size N (if it has not already been allocated), and then reads the remaining N data entries into the array. The commands that follow until the End command are to be applied to the resulting data array. The output of the Start command is:
Processing data from: Name.txt
• End Name, which indicates the end of the processing for the data in file Name.txt. The Start and End commands will always come in pairs with matching names. Any memory dynamically allocated for Name must be freed on an End command. The output of the End command is:
End of processing data from: Name.txt
2
• InsertionSort, applies insersion sort on the input data array. You must implement the insertion sort based on the pseudocode discussed in class or from the textbook. The output includes the number of comparisons made (ci), the number of swaps made in sorting the data (si), and the time taken to run the insertion sort (ti) in the following format:
Number of comparisons made by insertion sort: ci Number of swaps made by insertion sort: si
Time to run insertion sort (ms): ti
• MergeSort, applies merge sort on the input data array. You must implement the merge sort based on the pseudocode discussed in class or from the textbook. The output includes the number of comparisons made (cm), the number of swaps made in sorting the data (sm), and the time taken to run the merge sort ™ in the following format:
Number of comparisons made by merge sort: cm Number of swaps made by merge sort: sm
Time to run merge sort (ms): tm
• Select item, selects an item from a sorted data array. If the array has not been sorted by a previous command yet, the following error must be reported:
Unable to select from an unsorted array.
Valid items for selection include:
– max, prints the largest value in the data array;
– min, prints the smallest item in the data array;
– median, prints the median value of the data array.
Output the selected item (i), and the time taken (ts) to select this item as follows: Selection item: i
Time to run the selection (ms): ts
• Exit, indicates that there are no more commands to execute, i.e., the program terminates.
Test your program against the following command sequence. All the test files are provided in the folder
named ‘data files’.
Start test 1 InsertionSort Select max MergeSort Select min Select median End test 1 Start test 2 Select max End test 2 Start test 3 Select median
3
MergeSort Select median End test 3 Exit
Please feel free to generate additional test files, and test your program against any valid command sequence (e.g., a Start command has to be accompanied by an End command with the same file name).
4.3 Grading
The grading for this coding exercise is broken down into 2 categories: (1) Implementation (50%, including proper memory management and the Makefile); and (2) Correctness (50%, corresponding to the percentage of correct outputs from the script file used by the TA, which is different from the command sequence you’ve seen before).
4
Reviews
There are no reviews yet.