Assignment #2 Solution

$30.00

Description

Please list all sources in the table below including web pages which you used to solve or implement the current homework. If you fail to cite sources you can get a lower number of points or even zero, read more Aggie Honor System Office http://aggiehonor.tamu.edu/

Type of sources

People

Web pages (provide URL)

Printed material

Other Sources

I certify that I have listed all the sources that I used to develop the solutions/code to the submitted work.

“On my honor as an Aggie, I have neither given nor received any unauthorized help on this academic work.”

1. (15 points) Write a recursive function that counts the number of nodes in a singly linked list. Write a recurrence relation that represents your algorithm. Solve the relation and obtain the running time of the algorithm in Big-O.

2. (15 points) Write a recursive function that finds the maximum value in an array of int values without using any loops. Write a recurrence relation that represents your algorithm. Solve the relation and obtain the running time of the algorithm in Big-O.

3. (10 points) What data structure is most suitable to determine if a string s is a palindrome, that is, it is equal to its reverse. For example, “racecar” and “gohan gasalamiimalasagnahog” are palindromes. Justify your answer. Use Big-O notation to represent the efficiency of your algorithm.

4. (10 points) Write a pseudocode to implement the stack ADT using two queues. What is the running time of the push and pop functions in this case?

5. (10 points) What is the best, worst and average running time of quick sort algorithm? Provide ar- rangement of the input and the selection of the pivot point at every case. Provide a recursive relation and solution for each case.

6. (10 points) What is the best, worst and average running time of merge sort algorithm? Use two methods for solving a recurrence relation for the average case to justify your answer.

7. (10 points) R-10.17 p. 493 For the following statements about red-black trees, provide a justification for each true statement and a counterexample for each false one.

(a) A subtree of a red-black tree is itself a red-black tree.

(b) The sibling of an external node is either external or it is red.

(c) There is a unique (2,4) tree associated with a given red-black tree.

(d) There is a unique red-black tree associated with a given (2,4) tree.

8. (10 points) R-10.19 p. 493 Consider a tree T storing 100,000 entries. What is the worst-case height of

T in the following cases? (a) T is an AVL tree.

(b) T is a (2,4) tree.

(c) T is a red-black tree.

(d) T is a binary search tree.

9. (10 points) R-9.16 p. 418 Draw an example skip list that results from performing the following se- ries of operations on the skip list shown in Figure 9.12: erase(38), insert(48,x), insert(24,y), erase(55). Record your coin flips, as well.