Algorithm Design and Analysis Solution



HW 2 (Given September 15, 2017; Due September 22, 2017)

Each (sub-)question is worth 10 points unless otherwise stated

1. Write an algorithm to determine if a string s is a palindrome (e.g. never odd or even). What is the running time of your algorithm?

2. Give the contents of the stack after each operation in the sequence E A S * Y * * Q U E * * S T * * * I * O N * *. Here, a letter implies the letter is “pushed” and a “*” implies a pop” operation

3. Draw teh Binary Search Tree that results from inserting into an initial empty tree records with the values E A S Y Q U E S T I O N

4. Write a program to implement a tree using a linked structure. The tree should support the basic operations

5. Write a program to do inorder traversal of a tree (use the implementa- tion from Q3 above)