CS3334 - Data Structures
Lab 2
Outline
• Program Complexity Exercises
• Assignment 908: Manipulate Stacks
• Assignment 751 Reverse Polish Notation
Program Complexity Exercise 1
• You are given 30 integers as the input. Write a procedure to
output the largest value and the smallest integer value; and
analyze the time complexity.
• Suppose a[0] to a[29] are storing these integers.
Program Complexity Exercise 1
• You are given 30 integers as the input. Write a procedure to
output the largest value and the smallest integer value.
• Suppose a[0] to a[29] are storing these integers.
Set two references min and max, make them equal to a[0] at the beginning.
For all the following integers a[1] to a[29],
• compare it with the current min and max,
• update min and max accordingly.
if (a[i] > max) #Comparison need to execute?
. . .
if (a[i] < min)
. . .
Program Complexity Exercise 1
• You are given 30 integers as the input. Write a procedure to
output the largest value and the smallest integer value.
• Suppose a[0] to a[29] are storing these integers.
Set two references min and max, make them equal to a[0] at the beginning.
For all the following integers a[1] to a[29],
• compare it with the current min and max,
• update min and max accordingly.
if (a[i] > max) if (a[i] > max)
. . . . . .
if (a[i] < min) else if (a[i] < min)
. . . . . .
#Comparison need to execute?
Program Complexity Exercise 1
• You are given 30 integers as the input. Write a procedure to
output the largest value and the smallest integer value.
• Suppose a[0] to a[29] are storing these integers.
Do pairs of comparisons to decide which half of numbers will produce the
largest value and which half of the numbers will produce the smallest value.
a[?] a[?]
a[0] a[1] a[2] a[3] . . . a[28] a[29]
Supplementary materials for Analysis
• Why do we care about Big-Oh Analysis?
• Why can we write n2+3n+1=O(n2)? We know that
n2+3n+1>n2!
• We said that n4=o(2n), but if I set n=3, I have 34>23, how
does it come?
Supplementary materials for Analysis
• Suppose program 1 has worst case running time T1(n)=3n2+100nlogn+9,
program 2 has worst case running time T2(n)=2n+n and they can output the
same results. Which program do you choose? Explain the reasons for the
choice.
• Suppose program 1 has best case running time T1(n)=3n2, program 2 has
best case running time T2(n)= n and they can output the same results.
Which program do you choose? Explain the reasons for your answer.
Exercise 2
Analyze the running time of the following program
Exercise 2
Analyze the running time of the following program
(d)
(c)
void function4(int n, int choice) {
void function3(int n) { int x = 0;
if (n==1) if (choice==1) {
return; for (int i=1; i<=n; i++)
for (int i=1; i<=n; i++) { for (int j=1; j<=20; j++)
for (int j=1; j<=n; j++) { for (int k=n; k>1; k=k/2)
print("*"); x+=5;
break; }
} else {
} for (int j=1; j<=n*n; j++)
} for (int k=0; k<n; k++)
x+=3;
}
}
908: Manipulate Stacks
Description
After learning stack--the widely used data structure, Icy plan to play with it. The
rule is as follows: There are 3 stacks A, B and S, where stack B and S are empty
initially.
There are only two kinds of movement.
(1)Top element of A can only be moved onto the top of S.
(2)Top element of S can only be moved onto the top of B.
By repeating (1) and (2) until A and S are empty, all elements in A will be moved
to B and the elements in B are permuted (the order may not be the same). So
here comes the problem.
Given the initial order of elements in stack A and a final order of elements in B,
can you cleverly judge whether the final order is possible to achieve?
908: Manipulate Stacks
Input/Output
The input contains multiple test cases.
• The first line of input is an integer T (1 <= T <= 10) representing the number
of test cases.
• For each test case, the first line gives an integer 𝑛 (1 ≤ 𝑛 ≤ 3000) indicating
the number of elements in stack A,
• the following line gives 𝑛 integers representing the corresponding elements
in stack A (first element is bottom, last element is top and we guarantee
that all the elements are distinct).
• Then, the next line contains an integer 𝑚 (𝑚 <= 200) telling you how many
permutations you have to judge
• and in each of the following 𝑚 lines, there are 𝑛 integers indicating the
desired elements to be tested in stack B.
If the permutation is possible to achieve, print "Aye",
otherwise print "Impossible" in a separate line.
908: Manipulate Stacks
Sample Input Sample Output
1 Aye
5 Impossible
12345 Aye
3
12345
15423
32145
908: Manipulate Stacks
751 Reverse Polish Notation
Description
Reverse Polish Notation (RPN), also known as polish postfix notation or simply
postfix notation, is a mathematical notation in which operators follow their
operands.
For example, the infix expression
P1: 5 + ((1 + 2) * 4) - 3 can be written like this in Reverse Polish Notation:
P2: 5 1 2 + 4 * + 3 –
In terms of the operation, the expression P1 and P2 can be evaluated as
751 Reverse Polish Notation
Description
The reverse polish notation has many advantages, such as there is no bracket in
the expression and no priority is needed for the operators, most importantly,
the evaluation process is quite simple. The reverse polish notation could be
evaluated by using a stack.
751 Reverse Polish Notation
Input
The input contains multiple test cases.
Each test case contains a reverse polish notation string S in one line which
consists of digits 0-9, operators + - * and space.
It is guaranteed that the number in string S is one-digit number, that means
this expression 5 1 + 72 * will not appear in the input as 72 has two digits.
(The length of S is in the range from 1 to 1000)
Output
For each test case, print a single line containing the value of the reverse polish
notation.
751 Reverse Polish Notation
Sample Input Sample Output
512+4*+3– 14
98793-*++ 59
