The document discusses several problems involving recursion with data structures like arrays, linked lists, stacks. It provides pseudocode solutions to problems like Towers of Hanoi, checking if an array is sorted, and calculating factorials using recursion. For linked lists, it describes implementing a stack and finding the nth node from the end. For stacks, problems covered include reversing a stack, checking for palindromes, balancing symbols, postfix evaluation, and converting infix to postfix notation.
The document discusses several problems involving recursion with data structures like arrays, linked lists, stacks. It provides pseudocode solutions to problems like Towers of Hanoi, checking if an array is sorted, and calculating factorials using recursion. For linked lists, it describes implementing a stack and finding the nth node from the end. For stacks, problems covered include reversing a stack, checking for palindromes, balancing symbols, postfix evaluation, and converting infix to postfix notation.
The document discusses several problems involving recursion with data structures like arrays, linked lists, stacks. It provides pseudocode solutions to problems like Towers of Hanoi, checking if an array is sorted, and calculating factorials using recursion. For linked lists, it describes implementing a stack and finding the nth node from the end. For stacks, problems covered include reversing a stack, checking for palindromes, balancing symbols, postfix evaluation, and converting infix to postfix notation.
The document discusses several problems involving recursion with data structures like arrays, linked lists, stacks. It provides pseudocode solutions to problems like Towers of Hanoi, checking if an array is sorted, and calculating factorials using recursion. For linked lists, it describes implementing a stack and finding the nth node from the end. For stacks, problems covered include reversing a stack, checking for palindromes, balancing symbols, postfix evaluation, and converting infix to postfix notation.
Download as DOCX, PDF, TXT or read online from Scribd
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