2. Assuming time cost is the most important thing in our decision making process, present at least ONE example scenario that can best be solved by using a circular singly linked list (no need for a doubly linked list), explain WHY (3 point).

3. Assuming each reference costs 1 byte, and each piece of data/info costs 1 byte as well. When will a doubly linked list be more appropriate when space cost is the most important thing in our decision making process comparing to a 256 element array? Why? (3 point).

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 doesnt 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 I saw and cartrac. (6 points):