SOLVE PLEASE EXPERTS ONLY :

Homework $1($Data Structures, Fall $2024)$ Due: ${16}^{th}$ September $2024(11$:$59$ PM$)$

Q$1)($a$)$ What's is the result of the following postfix? Show the stack at the various stages of scanning the input postfix, the way it was done in class. $($Each time the stack changes, show the stack$).$

$62+153-i+i$

$($b$)$ In O$-$notation, what is the time complexity of this algorithm that evaluates postfix expressions $($Where $n$ is the length of the given postfix string$).$

Q$2)($a$)$ Write a function: "reverseStack$($Stack $st",$ which prints the contents of the stack st in reverse $($i$.$e$.,$ the top of the stack is printed last$).$

You are allowed only to use another stack, "Stack st$2".$ That is$,$ you cannot use any arrays etc. The only functions you can use on stacks are pop$(),$ push$()$ and empty$().($Hint: You put the contents of one stack into another by popping and pushing. Is the order the same?$)$

$($b$)$ Let $n$ be the length of the input stack. Let $k$ be the total number of times you had to push and pop from the two stacks. Express $k$ in terms of $n.$ What is the complexity of this reversing algorithm in O$-$notation?

Q$3)$ Consider the following nested loop:$($a$)$ How many times is $"$ j$=$j$+10"$ executed? $($Do not ignore any constants, as we are not talking about the O$-$notation yet$).($b$)$ In the code shown above, answer $($a$),$ if we replace $"$ j$=$j$+10",$ with $"$ j$=$ j$/4".($c$)$ Answer $($a$),$ if we make the following two changes to the code: We replace $"$ i$++"$ with $"$i$*=2",$ as well as we replace $"$ j$=$j$+10"$ with $"$ j$=$j$//4".$

Q$4)$ Order the following functions in ascending order of growth $($That is$,$ the function that grows the slowest growing function comes first$)$ :

$n+5,n^{\frac{1}{3}},n^{2}log(n),(1\mathrm{.}1{)}^n,n^{2\mathrm{.}5},(lo{g}_5{n}^2{)}^3$

NOTE: $log(n^k)=$klog$(n),$ and therefore have the same order of growth. However, $(logn{)}^k$ of course has a different order of growth as you would already know.