You may work alone or in groups of at most 2. The project has 3 parts.

**Part 1 (30%): Run an algorithm on an input set**

You are given a fragment of pseudocode below which describes an algorithm.

(a) The pseudocode below may or may not contain an error. If there is an error, rewrite the algorithm in pseudocode with the error corrected. This may involve some judgement on your part. Highlight your change. If there is no error, skip Part 1(a).

(b) Choose an appropriate input set for the (corrected) algorithm. Show what the algorithm does with this input set. Show each step.

(c) Determine a big-O estimate for the time complexity of the (corrected) algorithm. Explain your answer.

**Part 2 (50%): Translate into English**

It is up to you to determine *what task* the (corrected) algorithm from Part 1 is performing, as well as *how* it accomplishes this task. Write a short essay providing a detailed description of what task the algorithm is performing, as well as a line-by-line description of how it accomplishes this task. You may quote lines directly from the pseudocode in your essay. If there was an error in the original pseudocode, include a detailed description of the error, why it causes a problem, and how your correction solves the problem. Write your essay in plain English so that it is readable by a non-expert–someone who has never taken a programming or algorithms class and who is not familiar with pseudocode.

**Part 3 (20%): Translate into a programming language**

Write a program that implements the (corrected) algorithm for the set of inputs you chose in Part 1 and prints the output. Include comments throughout; in particular, include a comment that shows where you have included your input set. Your program must be written in C++ or Java.

**Submission instructions (note: these will be updated)**

Email the following to kpoirier@citytech.cuny.edu by 11:59pm on Monday, May 16. Be sure to include your name in every file.

- Part 1 may be completed by hand or using a computer; attach it to your email as a jpg or a pdf.
- Part 2 must be typed using a word-processor and attached as a pdf.
- If you are writing Part 3 in C++, save your program on cpp.sh. Create a short URL and include the link in the body of your email. If you are writing Part 3 in Java, DETAILS TBA.

**The algorithm**

**procedure** *mystery algorithm 1*(: real numbers)

**if** **then**

mystery algorithm 2(mystery algorithm 1(), mystery algorithm 1(), mystery algorithm 1()

return

**procedure** *mystery algorithm 2*( : sorted lists)

:= empty list

**while** and are both nonempty

remove smaller of first elements of and from its list; put it at the right end of

**if** this removal makes one list empty **then** remove all elements from the other list and

append them to

return

**Edit:** Mystery algorithm 1 and/or 2 may look similar to algorithms we’ve seen in class. For the project you will have to use your judgement if you are making corrections. However, if your corrected algorithm looks like one from class, then you will not receive credit for the correction. However, you may wish to use algorithms from class as a guide. Let me know if you have any questions.

**Edit 2:** This is not a class project. You may ask clarifying questions in the comments below, but you must work either completely independently or with your partner if you have one. (This is just a friendly reminder not to spoil it for anyone by spilling too much information about how to complete the project in the comments!)

Hi Prof.

Just wanted to make sure, those are two different algorithms correct? From these two algorithms we can pick one and then go through the parts stated above?

@Angel If you go through the algorithm, you’ll figure out the answer to your question.

Yes. It is 2 separate algorithms. I believe it’s a choice of which algorithm you want to correct. Both seem to have mistakes in them.

Yes. It is 2 separate algorithms. I believe it’s a choice of which algorithm you want to correct. Both seem to have mistakes in them.