Programming Assignment 3

COSC 3320

Algorithms and Data Structures

The writeup portion of your submission must be typed. We prefer you use LATEX to type your

solutions — LATEX is the standard way to type works in mathematical sciences, like computer science, and

is highly recommended; for more information on using LATEX, please see this post on Piazza — but any

method of typing your solutions (e.g., MS Word, Google Docs, Markdown) is acceptable. Your writeup

must be in pdf format. The assignment can be submitted up to two days late for a penalty of

10% per day. A submission more than two days late will receive a zero.

Before you begin the assignment, create an account on LeetCode if you do not already have one.

Problem 1 I Maximum Non-Negative Product in a Matrix

You are given a rows × cols matrix grid. Initially, you are located at the top-left corner (0, 0)

and, in each step, you can only move right or down in the matrix.

Among all possible paths starting from the top-left corner (0, 0) and ending in the bottom-right

corner (rows − 1, cols − 1), find the path with the maximum non-negative product. The product

of a path is the product of all integers in the grid cells visited along the path.

Return the maximum non-negative product mod 109 + 7. If the maximum product is negative,

return −1.

Note that the modulo is performed after getting the maximum product.

Example 1

Input:

grid =

−1 −2 −3

−2 −3 −3

−3 −3 −2

Output: -1

Explanation: It’s not possible to get non-negative product in the path from (0, 0) to (2, 2), so

return -1.

Example 2

Input:

grid =

1 −2 1

1 −2 1

3 −4 1

Output: 8

Explanation: Maximum non-negative product (in red) is 1 · 1 · −2 · −4 · 1 = 8.

Example 3

Input:

grid =

1 3

0 −4

Output: 0

Explanation: Maximum non-negative product (in red) is 1 · 0 · −4 = 0.

Example 4

Input:

grid =

1 4 4 0

−2 0 0 1

1 −1 1 1

Output: 2

Explanation: Maximum non-negative product (in red) is 1 · −2 · 1 · −1 · 1 · 1 = 2.

You must solve this using both a bottom-up Dynamic Programming algorithm and a memoized

recursive algorithm. Note that some solutions posted on LeetCodee may also be. In any case, a solution

that is largely copied from another source (e.g., verbatim or made to look different by simply changing

variable names) will be in violation of the Academic Honesty Policy.

The following must be submitted.

(a) Writeup (50 Points)

• Define the subproblems for your DP solution for finding the maximum non-negative product

value.

• Give a recursive formulation, including the base cases, to solve this problem.

• What is the running time of your solution?

• Write a DP algorithm (give pseudocode) that outputs the maximum non-negative product

value.

• Write a memoized algorithm (give pseudocode) that outputs the maximum non-negative

product value.

(b) Source Code (50 Points)

• Write your solution in Python, C, C++, Java, or JavaScript.

• Your code should be well written and well commented.

• A comment with a link to your LeetCode profile (e.g., https://leetcode.com/jane-doe/)

and a statement of whether or not your code was accepted by LeetCode. We will verify whether

your code is accepted.

• We must be able to directly copy and paste your code into LeetCode at the LeetCode problem

page. If your code does not compile on LeetCode, it will will receive zero points. Under

no circumstances will we attempt to modify any submission, so be sure the code you submit

works.

• Submit two files – one with the bottom-up Dynamic Programming solution and one with the

recursive memoized solution.

Please submit these files individually. Do not submit as an archived file (zip file, tarball, etc.).

1 Pseudocode and Explanation

Algorithm 1 Max-Prod-DP

1: def Max-Prod-DP(grid):

Algorithm 2 Max-Prod-Rec

1: def Max-Prod-Rec(grid):

2 Analysis