Data Structure and Algorithms Assignment 2

 COMP352– Assignment 2

COMP 352: Data Structure and Algorithms

Assignment 2

Written Questions (50 marks):
Question 1
You need to provide a new design for the Stack data type. Besides the usual push() and pop() operations,
you need to add a method called max(), which returns the current maximum value for any item in the
stack. Notice that the stack grows and shrinks dynamically as elements are added or removed from the
stack (i.e. the contents of the stack are not fixed).
a. Write the pseudocode of the max() method.
b. What is the Big-O complexity of your solution? Explain clearly how you obtained such
complexity.
c. Is it possible to have all three methods (push(), pop() and max()) be designed to have a
complexity of O(1)? If no; explain why this is impossible. If yes; provide the pseudocode of the
algorithm that would allow O(1) for all three methods (this time, you do not only need to think
about it, but to actually give the pseudocode if you believe a solution is feasible!)
Question 2
2) Assume that we have one single array A of size N, where N is an even value, and that the array is not
expandable. We need to implement 2 stacks using that array. Develop well-documented pseudo code that
shows how these two stacks can be implemented using this single array. There are two cases you must
consider:
Case I: Fairness in space allocation to the two stacks is required. In that sense, if Stack1 for instance use
all its allocated space, while Stack2 still has some space; insertion into Stack1 cannot be made, even
though there are still some empty elements in the array;
Case II: Space is critical; so you should use all available elements in the array if needed. In other words,
the two stacks may not finally get the same exact amount of allocation, as one of them may consume
more elements (if many push() operations are performed for instance into that stack first).
For each of the two cases:
a. Briefly describe your algorithm;
b. Write, in pseudocode, the implementation of the following methods, for each of the stacks:
push(), pop(), size(), isEmpty() and isFull();
c. What is the Big-O complexity for the methods in your solution? Explain clearly how you
obtained such complexity.
d. What is the Big-Ω complexity of your solution? Explain clearly how you obtained such
complexity.
 Is it possible to solve the same problem, especially for Case II, if three stacks were
required? If so, do you think the time complexity will change from your solution
above? You do not need to provide the answers to these questions; but you certainly
need to think about them!
 COMP352–Winter 2020 Assignment 2 – Page 2 of 4
Question 3
For each of the following pairs of functions, either f(n) is O(g(n)), f(n) is Ω(g(n)), or f(n) is θ(g(n)). For each
pair, determine which relationship is correct. Justify your answer.
f(n) = log3 n; g(n) = √𝑛𝑛 log n.
i) f(n) = 𝑛𝑛√𝑛𝑛 + log 𝑛𝑛 ; g(n)=log n4
.
ii) f(n) = 2n; g(n) = log2 n.
iii) f(n) = √𝑛𝑛; g(n) = 2�𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙.
v) f(n) = 2n
; g(n) = nn
.
vi) f(n) = 50; g(n) = log 60.
Question 4
Develop well-documented pseudo code that accepts an array of integers, A, of any size, then finds and
removes all duplicate values in the array. For instance, given an array A as shown below:
[22, 61,-10, 61, 10, 9, 9, 21, 35, 22,-10, 19, 5, 77, 5, 92, 85, 21, 35, 12, 9, 61],
your code should find and remove all duplicate values, resulting in the array looking “exactly” as follows:
[22, 61,-10, 10, 9, 21, 35, 19, 5, 77, 92, 85, 35, 12].
Notice the change of size. Also keep in mind that this is just an example; your solution must not refer to this
particular example; rather it must work for any given array.
Additionally, you are only allowed to use Stacks, Queues, or Double-ended Queues (DQ) to support your
solution, if needed. You are NOT allowed to use any other ADTs.
a. Briefly justify the motive(s) behind your algorithm.
b. What is the Big-O complexity of your solution? Explain clearly how you obtained such
complexity.
c. What is the Big-Ω complexity of your solution? Explain clearly how you obtained such
complexity.
d. What is the Big-O space complexity of your solution?
Note: You must submit the answers to all the questions above. However, only one or more questions,
possibly chosen at random, will be corrected and will be evaluated to the full 50 marks.
 COMP352–Winter 2020 Assignment 2 – Page 3 of 4
Programming Questions (50 marks):
In class, we discussed about Evaluating Arithmetic Expressions (refer to your slides and the text
book).
In this programming assignment, you will design, using pseudo code, and implement, in Java, two
versions of arithmetic calculators. The first version will be based on the pseudo code discussed in
class that uses two different stacks. The second version must be completely based on recursion. This
means that you have to replace the explicit use of stacks (in the first version) by using recursion (that
implicitly uses the JVM runtime stack). Your arithmetic calculators must read lines of text from a
text file, where each line contains a syntactically correct arithmetic expression. Your output file must
repeat the input line and print the computed result on the next line. Your calculators must support the
following operators on integers or reals and observe the standard operator precedence as shown
below (1-8, highest to lowest; same precedence evaluated left to right).
• 1. Parentheses (possibly nested ones): ( , )
• unary operators
2. factorial: !
3. minus: -
• binary operators
4. power function: xy
5. operators: *, /
6. operators: +, -
7. operators: >, ≥, ≤, <
8. operators: ==, !=
For the implementation of factorial and power function you have to use your own code (refer to your
slides and the text book) that should be as efficient as possible.
a) Briefly explain the time and memory complexity for both versions of your calculator. You
can write your answer in a separate file and submit it together with the other submissions.
b) For the second version of your calculator describe the type of recursion used in your
implementation. Does the particular type of recursion have an impact on the time and
memory complexity? Justify your answer.
c) Provide test logs for at least 20 different and sufficiently complex arithmetic expressions that
use all types of operators (including parentheses) in varying combinations.
You are required to submit a fully commented Java source files, the compiled files (.class files),
and the text files. You additionally need to submit the pseudo code of your program, together
with your experimental results. Keep in mind that Java code is not pseudo code.
Important Notes
The written part must be done individually (no groups are permitted). The programming part
can be done in groups of two students (maximum!).
For the written questions, submit all your answers in PDF (no scans of handwriting; this will
result in your answer being discarded) or text formats only. Please be concise and brief (less
than ¼ of a page for each question) in your answers. Submit the assignment under Theory
Assignment 2 directory in EAS or the correct Dropbox/folder in Moodle (depending on your
section).
 COMP352–Winter 2020 Assignment 2 – Page 4 of 4
For the Java programs, you must submit the source files together with the compiled files. The
solutions to all the questions should be zipped together into one .zip or .tar.gz file and
submitted via EAS under Programming 1 directory or under the correct Dropbox/folder in
Moodle. You must upload at most one file (even if working in a team; please read below). In
specific, here is what you need to do:
1) Create one zip file, containing the necessary files (.java, .doc, .html, etc.). Please name your file
following this convention:
If the work is done by 1 student: Your file should be called a#_studentID, where # is the number of
the assignment studentID is your student ID number.
If the work is done by 2 students: The zip file should be called a#_studentID1_studentID2, where #
is the number of the assignment, and studentID1 and studentID2 are the ID numbers of each student.
2) If working in a group, only one of the team members can submit the programming part. Do not
upload 2 copies.
Very Important: Again, the assignment must be submitted in the right folder of the assignments.
Depending on your section, you will either upload to EAS or to Moodle (your instructor will indicate which
one to use). Assignments uploaded to an incorrect folder will not be marked and result in a zero mark.
No resubmissions will be allowed.
 Additionally, for the programming part of the assignment, a demo is required (please refer to
the courser outline for full details). The marker will inform you about the demo times. Please
notice that failing to demo your assignment will result in zero mark regardless of your
submission. If working in a team, both members of the team must be present during the
demo.