University of Houston
Programming Assignment 4
COSC 3320
Algorithms and Data Structures
Gopal Pandurangan
NAME
Due: Sunday, April 18, 2021
11:59 PM
Read the University of Houston Academic Honesty policy.
Academic Honesty Policy
All submitted work should be your own. Copying or using other people’s work (including from the
Web) will result in −MAX points, where MAX is the maximum possible number of points for that
assignment. Repeat offenses will result in a failing grade for the course and will be reported to the
Chair. If you have any questions, please reach out to the professor and the TAs. The best way to
ask is on Piazza.
By submitting this assignment, you affirm that you have followed the Academic Honesty Policy.
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 Greatest Sum Divisible by Three
Given an array nums of integers, we need to find the maximum possible sum of elements of the
array such that it is divisible by three.
Hint: try splitting the array into three equivalence classes — the numbers whose
remainder are 0 mod 3, 1 mod 3, and 2 mod 3.
Note that if a and b are integers, then (a mod 3 + b mod 3) mod 3 = (a + b) mod 3. In particular,
if a mod 3 = 1 and b mod 3 = 2, then (a + b) mod 3 = 0.
Example 1
Input: nums = [3, 6, 5, 1, 8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).
Example 2
Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.
Example 3
Input: nums = [1, 2, 3, 4, 4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).
You must solve this using an efficient greedy algorithm. Note that some solutions posted on LeetCode
may be incorrect, inefficient, or utilize a different strategy. 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)
• Explain your greedy algorithm.
• Provide pseudocode and prove its correctness.
• Determine and prove the runtime of your algorithm.
(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.
Please submit these files individually. Do not submit as an archived file (zip file, tarball, etc.).
1 Pseudocode and Explanation
Algorithm 1 Greatest-Sum
1: def Greatest-Sum(nums):
2 Analysis