485 views
1 votes
1 votes

Let $M$ be an $(n \times n)$ matrix where each element is a distinct positive integer. Construct another matrix $M'$ by permuting the rows and/or permuting the columns, such that the elements of one row appear in increasing order (while looking from left to right) and those of one column appear in decreasing order (while looking from top to bottom).

  1. Describe an $O(n^2)$ time algorithm for constructing $M'$. Justify your analysis.
  2. Propose a data structure that supports your algorithm. Clearly explain how much additional storage, other than the matrix itself, is required in your algorithm.

Please log in or register to answer this question.

Related questions

1 votes
1 votes
0 answers
1
go_editor asked Jun 1, 2016
513 views
A connected, simple, undirected planar graph $G(V, E)$ is given where $V$ denotes the set of vertices and E denotes the set of edges. In $V$, there is a designated source...