CIS 334 Assignment 3 - Lists, Stacks and Queues 4. Write an algorithm in pseudo code to insert one element in a singly linked list before a given element. Your algorithm will print the original list, request the user to put in an element to be inserted, and an element to indicate the location of the insertion, then print the final list after the insertion is done. If the element doesn't exist in the list, add the new element to the end of the list. (5 points) Use the following as your test cases to evaluate whether your algorithm works correctly: if you have a linked list: 3>1>0 with user input 5 and 1, your list should become 3->5>1>0; with user input 5 and-1, your list should become 3>1>0 5. 5. Write an algorithm to check whether a given string is a palindrome. If a string reads the same backwards as forward (ignore the spaces, case not sensitive), we call the string as palindrome. For example, "madam" is a palindrome while "car" is not. Write your algorithm in pseudo code, then implement it in C++/Java. Your algorithm must involve explicit use of both a stack and a queue. Make sure to test your program with at least "Was it a car or a cat Isaw" and "cartrac". (6 points)