---
tags: 2023DS
---
# 2023 Data Structure - Homework 2: Transpose
* Deadline: 4/7 - 14:00
* Upload your homework to **moodle** platform.
* Please consult with TA if you have any questions.
* FB or email

## Problem
Given a sparse matrix A, transpose it by the following three methods:
1. Using traditional 2-dimensional array representation
2. Using the “Transpose” method in the textbook
3. Using the “FastTranspose” method in the textbook

## Input file description
The first line reads as m*k, where m and k are the number of rows and columns of the matrix, respectively. The following n lines are these non-zero elements, each line corresponding to a data point in the matrix.

E.g., a line may read as ```4 0 3```, indicating A(4,0) = 3

(assuming the row and column indices start with 0).

# cmd 讀入.in , 輸出到.out 
main.exe < 7_9.in > 7_9.out

## Output file description
The output shall consist of n+3 lines where the first n lines should print out the results of the transpose (refer to the sample output below for an example). The (n+i)-th line shall print out the execution time of method i.

## Sample Input

5 6
0 0 1
0 2 1
1 1 2
2 0 4
2 2 3

## Sample Output

(0, 0, 1) becomes (0, 0, 1) in the transpose
(0, 2, 1) becomes (2, 0, 1) in the transpose
(1, 1, 2) becomes (1, 1, 2) in the transpose
(2, 0, 4) becomes (0, 2, 4) in the transpose
(2, 2, 3) becomes (2, 2, 3) in the transpose
0.03 ms
0.02 ms
0.01 ms

Hint: The unit of the execution time can be determined by you.

## Note
For this homework, please use the input to generate a sparse matrix. Your code should be able to read in the input file, and quit this reading process once it reaches the EOF (end of file), and then start constructing the matrix. In the homework, you are expected to work on the following tasks:

1. Store all the elements using the 2-dimensional array representation. Then transpose the matrix.
2. Store the non-zero elements using the triple format; then use "Transpose" and "FastTranspose" methods to do the matrix transposition.

You shall follow the codes provided in the textbook, but be sure to use "polymorphism" to implement these three methods to write your C++ codes for this homework assignment, and print out the results using the triple format (i.e., (row, column, value)) suggested in the textbook.

Also, you have to write a function to print out exactly how much time each method takes to transpose a matrix (e.g., mini-seconds or whatever proper time units to show the difference among these methods).
::: info
Write down the analysis time complexity and what you learned from this exercise or any discussion in the report.
:::

Compress all the files (including your report and source code files), and name the compressed file as ```A1105500_hw2.zip(or .rar)``` using your student ID. Then upload the compressed file to the **moodle** platform. Also, you shall print out the output in the p2.out after executing the .exe

The file structure should be like one of the following forms:

|-A1105500_hw2.zip (.rar)
| |-main.cpp
| |-xxx.h
| |-xxx.cpp
| |-Report.pdf
| |-(And other files...)

or

|-A1105500_hw2.zip (.rar)
| |-A1105500 (Folder)
| | |-main.cpp
| | |-xxx.h
| | |-xxx.cpp
| | |-Report.pdf
| | |-(And other files...)

**Don't cheating**, or you will get 0 for this homework. If you can’t finish this homework before deadline, just hand in your unfinished code and report.

**Be honest with yourself.**

## Measurement
* Source code: 80%
* Report: 20%
## [Optional] Download test cases from moodle.
You can download some test input cases, which are created by assistant, to test your program's execution time.

The files just help everyone to write your homework.

Each of input files is named as the form ```i_j.in```.
* Ex: ```7_9.in``` means it has a matrix with 7 rows and 9 columns.