Description
Written Questions (50 marks):
Q1. Consider the problem of generating all the possible permutations of length n. For example, the
permutations of length 3 are: {1,2,3}, {2,1,3},{2,3,1}, {1,3,2}, {3,1,2}, {3,2,1}. In this question,
you will provide:
a) Well documented pseudocode of a recursive algorithm that computes all the permutations of
size n. Calculate the time complexity of your algorithm using the big-Oh notation. Show all
calculations.
b) Well documented pseudocode of a non-recursive algorithm that computes all the permutations
of size n. The only data structure allowed is a stack (you may use maximum up to two stacks).
Any other memory usage should be O(1). Calculate the time complexity of your algorithm using
the big-Oh notation. Show all calculations
Q2. Answer the following questions:
a) In class, we discussed a recursive algorithm for generating the power set of a set. In this
assignment, you will develop a well-documented pseudocode that generates all possible
subsets of a given set T (i.e. power set of T) containing n elements with the following
requirements: your solution must be non-recursive, and must use a stack and a queue to solve
the problem. For example: if T = {2, 4, 7, 9} then your algorithm would generate: {}, {2}, {4},
{7}, {9}, {2,4}, {2,7}, {2,9}, {4,7}, {4,9}, {7,9}, …etc. (Note: your algorithm’s output need
not be in this order).
b) Calculate the time complexity of your algorithm using the big-Oh notation. Show all
calculations.
Q3. Rank the following functions in non-decreasing order (≤) according to their big-Oh complexities
and justify your ranking:
n
4 + (log n)
2
, log log n,
n , n! + n,
2
n
,
n
2
, 2n
, n log n, nn
, 2log n
, 2
n!
+ n
2
, 2
2
n
Programming Questions (50 marks):
Q4. In this programming assignment, you will expand and implement the pseudo code discussed in
class for an arithmetic calculator that uses two different stacks (refer to slides 18 and 19 from the
chapter on Stacks). The expansion will involve: inclusion of more binary operators and inclusion of
the parentheses pairs (possibly nested ones). You will implement your code in Java. Your arithmetic
calculator 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 and follow the
Assignment 2 – page 2 of 2
standard operator precedence as shown in the following (1 to 6: 1 is the highest and 6 is the lowest.
Same precedence operators are evaluated from left to right).
1. Parentheses (possibly nested ones): ( , )
Binary operators:
2. power function: x^y.
3. operators: *, /
4. operators: +, –
5. operators: >, ≥, ≤, < 6. operators: ==, != As part of this programming assignment, you will do the following: a) Design and submit the pseudo-code of the arithmetic calculator. b) Implement a Java program. In your program, you will implement and use your own arraybased stack (and not the built-in Java stack) of dynamic size based on the linearly incremental strategy to be discussed in class (refer to the code segments provided on your slides and the textbook). c) Briefly explain the time and memory complexity your calculator. You can write your answer in a separate file and submit it together with the other submissions. d) Provide test logs for the Java program for at least 20 different and sufficiently complex arithmetic expressions that use all types of operators (including parentheses) in varying combinations. Submit all your answers to written questions in PDF format only. For the Java programs, you must submit the source files together with the compiled executables. The solutions to all the questions should be zipped together into two separate .zip files (one for Theory and one for Programming) and submitted via EAS (Refer to the course outline for more details on submission guidelines).
