代做Homework | 作业C++ | 代写Algorithm – Analysis of Algorithms

代做Homework | 作业C++ | 代写Algorithm – 这是一个利用C++进行的算法题目代写

CPSC 4100 Design & Analysis of Algorithms

homework #4 Programming Assignment

This is a programming assignment. You need to submit your c++ code on cs1.seattleu.edu.

Requirements

Problem #1 : Count the number of inversions for a vector of distinct integers using an order- statistics tree (OS tree). Given a vector A of n integers, if A[i] > A[j] where i < j , we call the pair (A[i], A[j]) an inversion.

In order to solve this problem, you need to implement an OS tree. Slightly different from the one we discussed in class, this OS tree is built on top of a binary search tree BST rather than a red- black tree. The source code files for the BST are provided including bst.h and bst.cpp. You can add data field(s) to the Node structure to maintain the additional information for the OS tree. You also need to support two public member functions for the OS tree, as shown in the table below:

int Select(int i) const Return the i-th smallest element on the OS tree.

int Rank(int val) const Return the rank of the key val on the OS tree. Assume that the key
val always exists on the OS tree.

In order to implement the OS tree, you will need to:

• Rename bst.h and bst.cpp to ost.h and ost.cpp respectively. Also rename C++ class BST to C++ class OST in both files.
• Change _BST_H to _OST_H in the header file ost.h.
• Modify Insert() and Erase() accordingly for your OS tree ( ost.cpp) to support maintenance of the additional info upon key insertion and removal respectively. You do NOT need to do rotations for tree rebalancing in this assignment.

Besides the OST class implementation, you need to complete the following function in the provided client.cpp:

int CountInversions(vector& A) {

//to complete

}

This function returns the number of inversions for a vector of distinct integers using the OS tree you have implemented as described above. You should not change anything in client.cpp except the function body for CountInversions(vector& A).

Problem #2 : Calculate the median and average of keys on a dynamic set of distinct integers. You need to augment a BST for this dynamic set called DICT. Again, you can use the provided BST class implementation and rename bst.h and bst.cpp to dict.h and dict.cpp, respectively. Rename C++ class BST to C++ class DICT in both files. Also, change _BST_H to _DICT_H in the header file dict.h. DICT supports two new (public) operations, as described in the table below:

int Average(int val) const Return the average of those keys <= val on the dynamic set
DICT. E.g., we have 3 keys on DICT <= val: {3, 4, 6}. Then
this function should return (3+4+6)/3 = 4. Note that it is an
integer division.
int Median(int val) const Return the low median of those keys <= val on the dynamic
set DICT. If we have m integers <= val on the set, then the
function should return (m+1)/2 - th smallest element.

Unlike the OS tree, you are not told what additional information should be maintained in DICT. You need to:

• Figure out what additional information to maintain in DICT. Add the additional information as new data members in the Node structure in dict.h.
• Modify Insert() and Erase() in dict.cpp to maintain the additional information upon key insertion and deletion repsectively. You do NOT need to do rotations for tree rebalancing in this assignment.

Provided Files

bst.h Head file for the underlying BST. You can use it as the template for dict.h and ost.h, respectively bst.cpp Implementation file for the underlying BST. You can use it as the template for dict.cpp and ost.cpp, respectively client.cpp Test program. You should not change anything except for implementing: int CountInversions(vector& A) using the OS tree. README In the README file, you need to:

• Include your name

• Time efficiency for CountInversions() by assuming that the OS tree you are using is always balanced
• For DICT, you need to: (1) Briefly explain what additional information is added to support DICT’s new operations. (2) Briefly explain how the additional information is maintained in Insert(). (3) Briefly explain how the additional information is maintained in Erase().

Submission

You can submit your program multiple times before the deadline on cs1.seattleu.edu. The last submission will be used for grading.

To submit your assignment, you should follow two steps below: 1). Wrap all your files into a package, named pa3.tar tar -cvf pa3.tar ost.h ost.cpp dict.h dict.cpp client.cpp Makefile README

2). Submit your newly generated package pa3.tar as the fourth programming assignment

pa /home/fac/zhuy/class/SubmitHW/submit pa3 pa3.tar

If it is a late submission, please contact me for late submission. Please do not email me the source files.

Grading Criteria

Label Notes 3 a. Submission (1 pt)

All required files are submitted.

3 b. Compilability (1 pts)

Your Makefile can compile the code and generate the executable file.

3 c. Format & Style (1 pt)

Clean, well-commented code. No messy output/debugging messages.

3d. README file (2 pts)

1. Time efficiency for CountInversions() by assuming the underlying tree is always balanced. (0.5pt)
2. Briefly explain what additional information is added to support DICT’s new operations. [0.5pt]
3. Briefly explain how the additional information is maintained in DICT::Insert(). [0.5pt]
4. Briefly explain how the additional information is maintained in DICT::Erase(). [0.5pt] 3e. Functionality and Algorithm efficiency (8 pts)

The program behaves as specified (passed all the test cases). All the member functions are
properly implemented. Algorithms are efficient.

3f. Overriding policy

If the code cannot be compiled or executed (segmentation faults, for instance), it results in zero point. 3g. Late submission

Check the late submission policy