# Foundations of Artificial Intelligence Homework 3 Solution

\$35.00 \$30.80

## Description

1. (15 points) Describe in pseudo code how to implement the stack ADT using two queues.

• Write a C++ function that implements your solution. You can use the C++ STL queue container.

• What is the running time of the push and pop functions in this case?

1. (15 points) Write a recursive function in C++ that counts the number of nodes in a singly linked list.

• Test your function using diﬀerent singly linked lists. Include the code and screenshots with testing cases.

• Write a recurrence relation that represents your algorithm.

• Solve the relation using the iterating or a recursive tree method to obtain the running time of the algorithm in Big-O notation.

1. (15 points) Write a C++ recursive function that finds the maximum value in an array of integers without using any loops.

• Test your function using diﬀerent input arrays. Include the code and screenshots with testing cases.

• Write a recurrence relation that represents your algorithm. Solve the relation and obtain the running time of the algorithm in Big-O notation.

1. (15 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.

1. (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.

1. (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 subtree of a red-black tree is itself a red-black tree.

• The sibling of an external node is either external or it is red.

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

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

1. (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?

2

• T is an AVL tree.

• T is a (2,4) tree.

• T is a red-black tree.

• T is a binary search tree.

1. (10 points) R-9.16 p. 418

Draw an example skip list that results from performing the following series 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.

3