Algorithms Correctness and Efficiency
(COMP2048 UNNC)
Course Work 1 Report
Hui BAO
20412001
11/14/2023
1
Aanalysis of Question 1
1.1
Data Structure
For storage of operators and operands,
stack
is chosen, which can realize LIFO(Last
In First Out) via
pop
and
push
. As the critical part of calculation comes down to
the precedence of operators,
stack
can better deal with current expression when
encounter operation with higher precedence or with parentheses.
In addition,
HashMap
is used to match the truth value with operators, as it can
quickly find the corresponding value via variable’s name and substituting value into
the operation.
1.2
Algorithm Design
Overall, this piece of code realizes
recursive algorithm
. As the whole expression
can be divided into small sub-expression on account of possibly existing parentheses.
Recursive algorithm will define a
base situation
and split question into small
sub-questions
, solved by calling the function itself. In
PartialCalculation
, the base
situation is that there is no nested expression in current expression. Otherwise, it
will recursively find expression between parentheses.
After reaching base situation, precedence of operator will be compared with the
one of current operator at the top of stack (if exists). Ultimately, operator(s) re-
mained in stack will be manipulated in sequence.
1.3
Correctness Justification and Efficiency Analysis
1.3.1
Algorithm Correctness Justification
The implementation of this code can be broadly broken down into five following
points: Mapping truth values, matching parentheses, precedence of operators and
methods of propositional logic.
ˆ
The code will first check whether there exits input of values, which will not
cause exception such as
IndexOutOfBound
and will
terminate
if answer is no.
Otherwise, before each time of mapping, function
MatchValue
will check the
1
existence of duplicate operand to avoid mistakenly mapping another value.
This ensures the
correct result for all valid input
.
ˆ
When matching parenthesis, an integer variable called
bracketBalance
is used.
The function will
terminate
when
bracketBalance
is 0 and for all opening paren-
theses,
correct closing parentheses will be found
.
ˆ
For expression calculation, progress will
terminate
after
pop
the result. And
stack
will ensure
accuracy
when facing precedence issue.
For all functions, they will
terminate
after all essential operations are done.
For
all valid inputs, for parentheses checking and concrete calculation part, appropriate
relationship was held between inputs and results
. Especially for basic single logic
calculation, it is able to return accurately outcome.
1.3.2
Algorithm Efficiency Analysis
For time complexity:
ˆ
PartialCalculation
,
FindEndingBracket
and
MatchValue
:
O
(
n
). They are re-
lated to the manipulation of each element or character. However, in
Match-
Value
,
HashMap
is used to store operands and corresponding values, which had
the complexity of
O
(1) and will not waste time on searching and adding.
ˆ
FindEndingOpt
,
IsOperation
,
ExistHigherPrecedence
and
TopCalculation
:
O
(1).
As operations will not be significantly influenced by number of operators or
operands.
To summary, the efficiency of this piece of code is acceptable under small-scale
data. If in face of large-scale data, stack’s depth can be worrying. Thus, postfix ex-
pressions can be taken into consideration to avoid manipulating operator precedence
and nested parentheses.
2
Aanalysis of Question 2
2.1
Data Structure
An
array
named
students
is used to store students’ positions. For example,
student[0]
stores the position of student with ID 1, which initially is 1. Reason for recording
students’ positions other than IDs is that for further operations, student can be found
straightly via index instead of traversing array and mapping element with parameter.
2.2
Algorithm Design
Overall, the algorithm chosen for this piece of code is just
simple data manipula-
tion and logical control
.
While reading in each line, for input of concrete operation, the code will immedi-
ately separate variables by detecting blank space and pass these variables to
Operate
function. For method 1 and 2, they adopt similar handling method, but method 3
adopt simpler method to reduce unnecessary primitive operations.
At the end of code, the whole array will be traversed to find student(s) on even
position.
2
