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 different 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 different 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