Have to use Merge Sort to solve no other sorting method 1. An integer matrix is
ID: 3745774 • Letter: H
Question
Have to use Merge Sort to solve no other sorting method
1. An integer matrix is an n m array of integers, for example: 3 10 4 1 1012-18 A-3 -12-101 23 670 3 10 A row is a series of numbers from left to right and a column is the series from top to bottom. Here, we will modify merge sort to sort the rows of a matrix, with respect to their columns. For the above example, this yields: 1 1012-18 3 -12-101 A-3 10 4 3 10 67 0 23 (a) (15 pts) Write pseudocode for this modified version of merge sort (call it MATRIXMErGESorT) (b) (20 pts) Prove the best- and worst-case complexity of MATRIXMerGe- Sort. For simplicity, assume that the matrices are square (i.e. they are n × n matrices, in which the number of rows is equal to the number of columns) (c) (5 pts) Assume that comparing two rows can be done in constant time (e(1)). Is the worst-case complexity of MATRIXMErGE- SorT in this case better or worse than regular merge sort? Why?Explanation / Answer
5:54 PM
In this assignment, you will create a class similar to the List ADT.
Simulate a simple text editor, which stores a string of characters using the List ADT which has been endowed with some additional features. We will call this endowed List ADT as a Cursor class. Normally, you would implement the Cursor class using inheritance, that is, the Cursor class would be a derived class of the List ADT which would serve as the base class. However, in this assignment we will implement the Cursor class from scratch and model it after the List ADT.
You must use a singly linked list. Do not use any iterators to traverse the list. The reason is I want you to manipulate the linked lists directly.
Your editor should support the following operations and redisplay the current text (that is, the list) after performing any one of them.
left : move cursor left one character (or do nothing if at the beginning of the text)
right : move cursor right one character (or do nothing if at the end of the text)
delete : delete the character to the right of the cursor (or do nothing if at the end of
the text)
back : delete the character to the left of the cursor (or do nothing if at the
beginning of the text)
insert c : insert the character c just after the cursor.
home: move cursor to the beginning of the text (or do nothing if at the beginning
of the text)
end: move cursor to the end of the text (or do nothing if at the end of the text)
undo: undo the last insert/delete/back operation
(You can assume that between any two consecutive “undo” commands issued by the user, there will be at least one insert/delete/back operation.)
The Cursor class definition is provided to you. You can only add member variables or member functions to the definition provided. You cannot remove any declaration from the class definition1. You have to write the implementation for the Cursor class and a driver program that will allow the user to enter text to use your “text editor”. The user will input:
• l-forleft • r-forright
• d - for delete
1 If you need to make any deletions because of recent updates to the C++ language, please bring it to my attention immediately.
b-forback
i c - for insert character c
h–forhome
e–forend
u–forundo
(l, r, d, b, i, h, e and u will be input in lower case only)
After each of the above operations you will display the entire text with a ‘|’ indicating where the cursor is currently positioned.
For example, the following table gives a sequence of user commands and what will be displayed after each command:
user command
Displayed text
id
d|
ia
da|
it
dat|
ia
data|
l
dat|a
l
da|ta
b
d|ta
r
dt|a
u
da|ta
b
d|ta
ie
de|ta
il
del|ta
The user will enter the $ character when they are done.
(FIRST EXTRA CREDIT 50 points) Allow the user to undo up to the last 10 insert/delete/back operations. (Hint: You will have to use a stack for this.). For this, you cannot assume that between any two consecutive “undo” commands issued by the user, there will be at least ten insert/delete/back operations.
(SECOND EXTRA CREDIT 50 points) Allow the user to delete/back a contiguous group of characters – this command will be specified by d or b followed by a number. For e.g., d5 will delete 5 characters counting forward from the current position of the cursor. You can assume a valid number will be input. That is, if the user inputs d5, you can assume that there are at least 5 characters counting forward from the current position of the cursor. Note that if you choose to implement this option, the undo operation should work in this case also (just like in a real editor such as Word).
#ifndef CURSOR_H
#define CURSOR_H
// Cursor class.
// *****************PUBLIC OPERATIONS*******************************************************************************
// bool isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void left( ) --> Move cursor one position left or do nothing if already at beginning of text
// void right( ) --> Move cursor one position right or do nothing if already at end of text
// void del( ) --> Delete node after current cursor position or do nothing if already at end of text
// void back( ) --> Remove node before current cursor position or do nothing if already at beginning of text
// void insert( x ) --> Insert x after current cursor position
// void home( ) --> Move cursor to the beginning of text or do nothing if already at beginning of text
// void end( ) --> Move cursor to the end of text or do nothing if already at end of text
// void undo( ) --> Undo the last delete/back/insert operation
// ******************PRIVATE OPERATIONS*****************************************************************************
// void printText ( ) --> This will print the entire contents of the list. This is a private member function.
// This will be called by each of left(), right(), del(), back() and insert().
//********************************************************************************************************************
template <class Object>
class Cursor; //forward declaration.
template <class Object>
class CNode
{
CNode( const Object & theElement = Object( ), CNode * n = nullptr ): element( theElement ), next( n ) { }
Object element;
CNode *next;
friend class Cursor<Object>;
};
template <class Object>
class Cursor
{
public:
Cursor( );
CABIN, 5:56 PMskip6:01 PMa b c Unread messagesCABIN, 6:04 PMa. Array <--- array[m][n] //declare 2D array of size m and n and later initialize
insertionSort(array[m][n]) //pass array in real insertion sort algorithm
/**********************in InsertionSort*****************/
sort by columnwise // instead of swapping elements swap row arrays
now find where column elements are same and sort it according second column if elemnts of second column are same sort according to subsequent column
tip: // use insertion sort algorithm for above, in that algorithm change 1D array with 2D array and single elements with row array
b. best case is when all the elements in first column are different so we will not have to worry about second column so time complexity only n2
worst case is when all the elements in first n-1 columns are same and only last column elements are different(optional because if same not much difference it will make), here we will have to sort columnwise so for every column we will get n2 time so we will have to sort all n columns due to that time complexity will be n3
c. It will not be same, in this case , worst-case complexity of MATRIX- INSERTION-SORT, is better than the regular insertion sort.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.