In this assignment, you will be designing and implementing MapReduce algorithms for a variety of common data processing tasks. Problem 6: Assume you have two matrices A and B in a sparse matrix format, where each record is of the form i, j, value. Design a MapReduce algorithm to compute matrix multiplication: A x B

Map Input

The input to the map function will be matrix row records formatted as lists. Each list will have the format [matrix, i, j, value] where matrix is a string and i, j, and value are integers.

The first item, matrix, is a string that identifies which matrix the record originates from. This field has two possible values:

```    ‘a’ indicates that the record is from matrix A

‘b’ indicates that the record is from matrix B

```

Reduce Output

The output from the reduce function will also be matrix row records formatted as tuples. Each tuple will have the format (i, j, value) where each element is an integer.

You can test your solution to this problem using matrix.json:

```    python multiply.py matrix.json

```

You can verify your solution against multiply.json.

```import MapReduce
import sys

"""
Word Count Example in the Simple Python MapReduce Framework
"""

mr = MapReduce.MapReduce()

# =============================
# Do not modify above this line

def mapper(record):
# key: document identifier
# value: document contents
matrix, row, col, value = record
for n in range(5):
if matrix == 'a':
cell = (row,n)
matr = 'L'
col_row = col
else:
cell = (n,col)
matr = 'R'
col_row = row
mr.emit_intermediate(cell, (matr, col_row, value))
#key = (cell, matrix, col_row, value)

def reducer(key, list_of_values):
# key: word
# value: list of occurrence counts
left_matrix  = [(item,item) for item in list_of_values if item == 'L' ]
right_matrix = [(item,item) for item in list_of_values if item == 'R' ]

result = 0

for item_L in left_matrix:
for item_R in right_matrix:
if item_L == item_R :
result += item_L * item_R

#mr.emit((key, item, result))
if result != 0:
mr.emit((key,key, result))

# Do not modify below this line
# =============================
if __name__ == '__main__':
inputdata = open(sys.argv)
mr.e xecute(inputdata, mapper, reducer)``` 