The Common Denominator? Solve the problem Basic Programming 2?, which you can find at this web address: open.kattis.com/problems/basicprogramming2? Although this problem has several parts, t

CSE 431/531, Algorithms: Design and Analysis, Fall

2022, Homework 2

Due Friday, October 21, 2022, 11:59pm

General Instructions: For this homework, there are two algorithms problems, both of which will require you to actually code. You will make a free account on open.kattis.com

and use its judging software to test your solutions. Your code is required to pass the test on Kattis, so be sure to start early and allow yourself enough time to complete the debugging process. If your code has any bugs or is too slow, you will almost certainly not pass all the tests.

Details:

• You may code in your choice of {C, C++, Java, Python}. It is up to you to ensure that your code will compile using the corresponding compiler on Kattis. (If you want to use one of the other languages Kattis supports, you need to clear it with the instructor and TAs first.)

• Kattis will test your answer for efficiency and correctness. It uses two sets of test inputs: a public one that you have access to while coding and debugging, and a private one that you don’t get to see, but also need to pass. It would be a good idea to make your own test inputs as well, and you are welcome to share these with your classmates on piazza. Each time you submit your code on Kattis, it will check whether it compiles correctly and passes the test inputs (without timing out).

• There is no limit on how many times you submit on Kattis. You just need to pass the tests in the end.

• Important: Kattis requires that you read the input from stdin, and write only the required output to stdout. You are encouraged to produce more verbose output that goes to stderr (Kattis will ignore this).

• For the problem submission on Gradescope, upload your full, commented code, followed by a proof that Kattis accepted it (such as a screenshot from Kattis showing your username and the Accepted status of the problem). You should be able to use this webpage: https://open.kattis.com/problems?show_solved=on&show_tried=off& show_untried=off

• Follow good programming practices such as carefully naming variables and functions, organizing your code, commenting, and making your code a joy to read (not an em- barassing mess!)

• As always, the code you submit must be your own. You must acknowledge any sources who made a significant contribution to your successful solution, such as classmates, textbooks, websites, etc. Upon request, you must be prepared to meet with the instructor and/or TA and explain, in detail, how your code works.

1

There are 2 problems, worth 20 points each. Start each problem on a new page! Include a cover sheet with your name, but do not put your name on the problem solution

pages. Submit your solution on GradeScope, using its interface to tell it which pages correspond

to each problem. Although the following are not required this time, you are encouraged to additionally

provide:

1. more readable descriptions of your algorithms (i.e., pseudocode)

2. proofs of correctness, and especially:

3. analysis of the running time.

Problem 1

The Common Denominator. Solve the problem “Basic Programming 2”, which you can find at this web address:

open.kattis.com/problems/basicprogramming2

Although this problem has several parts, there is a common theme to all of them. Part (a) of this problem is to write down what this common theme is (one sentence max).

Part (b) is to solve the problem.

Problem 2

Spiderman is Afraid of Heights. Solve the problem “Spiderman’s Workout”, which you can find at this web address:

open.kattis.com/problems/spiderman

2