Final Exam Supplement - Heap Sort Implementation
CS291 DE (Spring XXXXXXXXXXWeek 16
Swap
void swap(int A[], int i, int j)
{
int temp;
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
Bu
leUp
void bu
leUp(int A[], int i)
{
if (i > 1 && A[i] > A[i/2]) {
swap(A, i, i/2);
u
leUp(A, i/2);
}
}
Insert
void insert(int A[], int x, int *pn)
{
(*pn)++;
A[*pn] = x;
u
leUp(A, *pn);
}
Bu
leDown
void bu
leDown(int A[], int i, int n)
{
int child;
child = 2*i;
if(child < n && A[child+1] > A[child])
++child;
if(child <=n && A[i] < A[child]){
swap(A, i, child);
u
leDown(A, child, n);
}
}
DeleteMax
void deletemax(int A[], int *pn)
{
swap(A, 1, *pn);
--(*pn);
u
leDown(A, 1, *pn);
}
Generate Random
Not core to the priority queue implementation.
int random_value(int range, long seed) {
srand(seed);
Begin: Single Line Directive
float generator = (float)
and() / (float) RAND_MAX;
End: Single Line Directive
Begin: Single Line Directive
float random =
floor(range * generator);
End: Single Line Directive
eturn random;
}
Main
#include
#include
#include
#include
using namespace std;
using namespace std::chrono;
int main() {
int RANGE = 100;
int CAPACITY = 16;
int heap[CAPACITY];
int n = 0;
int *pn = &n;
for(int i = 0; i < CAPACITY; i++) {
heap[i] = 0;
}
for(int i = 0; i < CAPACITY; i++) {
Begin: Single Line Directive
long nanoseconds = std::chrono::duration_cast
(std::chrono::system_clock::now().time_since_epoch()).count();
End: Single Line Directive
Begin: Single Line Directive
insert(heap, random_value(RANGE, nanoseconds/(i+1)), pn);
End: Single Line Directive
}
cout
"|";
for(int i = 0; i < n; i++) {
cout
heap[i]
"|";
}
cout
"\n";
eturn 0;
}
Final Exam
CS291 DE (Spring XXXXXXXXXXWeek 16
Date: May 24th, 2020
First Name:
Last Name:
I. ADMINISTRATIVE
Please answer as many questions as you can. In particular,
if you would like to improve your grade overall.
There is quite a bit to consider in this final and it will be
possible to achieve a perfect score without answering all
questions, yet in answering all questions, you will
demonstrate proficiency in all topics covered since the
midterm. Wishing everyone the best of luck and a great
summer filled with academic and educational pursuit.
II. ELEMENTARY NON-LINEAR DATA STRUCTURES
1) Given a list
L = (8, 29, 30, 11, 4, 7, 2, 27, 24, 35, 42, 25, 68, 57, 31),
construct a binary tree given a left to right insertion orde
without any balancing applied.
2) Given the above list, if we are to instantiate an optimally
alanced tree, what is the best selection for a root node.
3) Given the tree instantiated in question (1), what is the
path of traversal initiated at the root that determines if 37
is a member of our search space. As a note, given a
collection of nodes (each of which is a child of the prior)
n1, n2, n3, ...nk, a path of traversal can be written using
the following form (from root node n1).
n1 → n2 → n3 → ...→ nk
4) Given the tree instantiated in question (2), what is the
path of traversal initiated at the root that determines if 37
is a member of our search space.
5) From our study of partially ordered trees and priority
queues, we know that we can instantiate a priority queue
using a heap implementation which relies on a primitive
a
ay. This method of storing a partially ordered binary tree
can be extended to support storage of our list L from
question (1) in the form of a binary search tree. Create a
C++ program that instantiates a binary search tree using
our heap implementation from an a
ay argument such as L
from question (1). This implementation is not effective in a
situation where our binary tree is dynamic (meaning there
is continuous change of structure by way of insertion and
deletion), yet for the purposes of determining the max
height of an instantiated tree (be it balanced or random),
we can use this representation.
6) After implementing (5), consider the below listed seeds
for the genlist.cpp program provided for Assignment
3.
S1 = XXXXXXXXXX
S2 = XXXXXXXXXX
S3 = XXXXXXXXXX
S4 = XXXXXXXXXX
Use these seeds to generate (4) lists of 15 numbers each
and instantiate the structure from (5) with each unsorted
list B.
7) Now consider the node (or nodes) of greatest depth
given our binary search tree stored as a heap. The structure
should be comparable to one instantiated using the random
order of elements provided by list B. Given all fou
variations derived from S1, ..., S4, spend some time
eviewing the form these randomly generated trees take on
implemented as heaps.
8) Provide some observations that can be used to identify
the height of our binary tree (for each case S1, S2, S3, and
S4), then attempt to generalize your observations into some
formula that can be applied universally. If you can offe
any other details from analysis than do so.
9) Consider the below infix expression.
E = ((((v1 + (v6/v3))/v2)× (v11 + (v5 − v1)))%v0)
Sketch an expression tree co
esponding to expression E.
10) Apply preorder traversal to derive a prefix formulation
of E. Similarly apply postfix traversal to derive a postfix
formulation of E.
III. ALGORITHMS AND ASYMPTOTIC ANALYSIS II
SORTING ALGORITHMS
1 and 2) From the description of insertion sort provided in
the notes, create an implementation of the algorithm and
apply it to the unsorted lists generated by ou
genlist.cpp program given the below seeds.
S1 = XXXXXXXXXX
S2 = XXXXXXXXXX
S3 = XXXXXXXXXX
S4 = XXXXXXXXXX
3 and 4) Code to assist in implementing a priority queue is
provided as a supplement to this exam. Given the
supplement, extend the code to support the heap sort
method. In other words first instantiate a priority queue
elementwise and then dequeue each element one by one to
generate a sorted list.
5) Apply your heap sort method to the unsorted lists (B)
generated by the genlist.cpp method.
Administrative
Elementary Non-linear Data Structures
Algorithms and Asymptotic Analysis II Sorting Algorithms