Data Structures and Algorithms in Java: Code Implementation Assignment

This assignment presents a Java code solution addressing three problems related to data structures and algorithms, based on the textbook "Data Structures and Algorithms in Java 6th ed." The solution includes Java code for problems involving recursion (turning lights on and off with analysis of time complexity), array manipulation, and the use of stacks, ArrayLists, and StringBuilders to evaluate and print the results of mathematical expressions. The document also includes the implementation of the code, along with explanations of the algorithms and data structures used. The solutions are designed to provide students with a comprehensive understanding of the concepts and their practical application in Java.

Question 1:
a.) Pseudocode for turnOn(n)
Algorithm turnOn( n )
//Lights 1… n are all off
//Final result :Lights 1… n are all on.
If(n = 1) then Turn ON light 1
//for n > = 2
else
{
If( n > 2) then turnOn( n – 2)
turn On light n
if(n > 2) then turnOff( n -1)
turnOff( n -1)
}
end
b.) The code is implemented by use of recursion and an array to keep track of the off and on lights
and print them as we power them either off or on respectively. It then generates results and
writes them in a file named LightsTestIO.txt.
c.) We are going to estimate the number of times the lights are turned off or on using the
substitution method of solving recurrences where we make a guess then use mathematical
induction to prove the guess correct or otherwise.
T(n) = 2T(n-2) + (n-1).
Let our solution be T(n)//linear time .
Now lets use induction to prove our answer.
We need to prove that T(n) <= n logn, assuming it is true for values smaller than n.
T(n)=2T(n – 2) + (n – 1) <= (n – 2) + ( n -1)
=2n -1
=n
Hence T(n).

d.) Algorithm
flipSwitches(n,s)
//Pre-Condition s = true meaning n lights are on
//Post-Condition s = false meaning n lights are off
If( n = 1 and s =true) then we turn off light 1 and set s= false;
else{
if( n > 2 and s =true) then flipSwitches(n-2,s);
Turn off light n and set s= false;
If( n > 2 and s = false) then flipSwitches(n-2,s) and set s=true
flipSwitches(n -1,s)
}
//Pre-Condition s = true meaning n lights are on
//Post-Condition s = false meaning n lights are off
If(n=1 and s = false) then we turn on light 1 and set s=true;
else{
if( n > 2 and s= false) then flipSwitches(n – 2,s);
Turn on light n and set s =true;
If(n > 2 and s = true) then flipSwitches(n-2,s) and set s=false;
flipSwitches(n -1,s);
}
end //all are turned off or off depending on boolean state of s
Problem 2:
The time complexity is linear that is O(n);the implementation is attached.

Problem 3:
It involves the use of stacks, ArrayLists and StringBuilders to check the equation, append the left
parenthesis, evaluate the equation and print the equivalent results in a text document called
ExpressionTestIO.txt.
Attached are the files.