Application Algorithms (1) - 1

Download as docx, pdf, or txt
Download as docx, pdf, or txt
You are on page 1of 5

Recursion

Problem 1- Towers of Hanoi puzzle[O(2n)]:


1- Shift “N-1” disks from ‘A’ to ‘B’, using tower ‘C’

2- Shift the disk from ‘A’ to ‘C’

3- Shift ‘N-1’ disks from ‘B’ to ‘C’, using ‘A’

Problem 2- check whether the array is sorted[O(n)]:


1- Assign the base case to: length of array <= 1
2- Check if the first element is <= to the second:
• True: perform a recursive call with array[1:]
• False: the array is not sorted
3- Step 2 will be repeated when all the elements are sorted

Problem 3- Get the factorial[O(n)]:


1- Assign the base case to: n = 0 this will return 1
2- In recursive case n > 0 the function will call itself
to find (n-1) and multiply that by n
Linked-List

Problem 1- Implement stack using linked-list:


- First, we will make a node of singly linked list
- Push operation implementation same as insert at
beginning:
• Create a node
• Point the Node to the stack head
• Make the node is the top element
- Pop operation is implemented by deleting the node from
beginning:
• Check if the stack is empty(error)
• Assign top element to variable(temp)
• Set the head value to temp.next
Time complexity: book(pg:101)

Problem 2- find the nth node from the end of linked-list:


1- Calculate the length of the linked list = Len
2- Print the (Len – n+ 1) th node from the beginning
Time complexity: O(M) where M is the size of linked list
Stack
Problem 1- Reverse Stack elements[O(n2)]:
1- First, pop all the elements from the stack till it becomes empty
2- For each upward step in recursion, insert the element at the
bottom of the stack

Problem 2- Check whether the string is


palindrome[O(n)]:
1- Make to indexes one at the beginning ‘i’and the other at the
end ‘j’
2- Compare i and j values if they are the same:
True: increment ‘i’, decrease ‘j’
False: the string is not palindrome
3- If ‘i’ and ‘j’ met at the middle(X) the n the string is
palindrome.
Code in pg: 110

Problem 3- checking balancing of symbols[O(n)]:


1- Create a stack
2- Iterate for symbols in the given string
a. Ignore any symbol expect the parentheses
b. Push the symbol to the stack if it is opening (,{,[
c. If it closing, check if the stack empty report an error,
if not pop the stack
d. If the popped symbol does not correspond to an
opening
symbol, report, and error
3- At the end, if the stack is empty then the symbols are
balanced

Problem 4- Postfix evaluation:


l .Scan the Postfix string from left to right.
2 .Initialize an empty slack.
3 .Repeal steps 4 and 5 till all the characters arc scanned.
4. If the scanned character is an operand, push it onto the
stack.
5 .If the scanned character is an operator, and if the operator
is a unary operator, then pop an element from the slack. If
the operator is a binary operator, then pop two elements
from the stack. After popping the elements, apply the
operator to those popped elements. Let the result of this
operation be retVal onto the stack.
6 .After all characters are scanned, we will have only one
element in the stack.
7 .Return top of the stack as result.

Problem 5- Infix to Postfix:


a) Create a stack.
b) while (end of input is not
reached) :
1) If the character read is
not a symbol to be
balanced, ignore it.
2) If the character is an
opening symbol like(, [, {.
push it onto the stack
3) If it is a closing symbol
like ),],}, then if the stack
is empty report an error.
Otherwise pop the stack.
4) if the symbol popped is
not the corresponding
opening symbol, report
an error.
c) At end of input. if the stack is
not empty report a n error

You might also like