Explain the “Divide & Conquer” approach to algorithm design.  What impact does it have on time complexity? 

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

1)     Explain the “Divide & Conquer” approach to algorithm design.  What impact does it have on time complexity? 

2)     Why would we sometimes wish to write a non-recursive version of a recursive algorithm?  What is the name given to this approach? 

3)     What is a “treap,” and how does it contribute to the efficient execution of an algorithm in which it is implemented? 

4)     Starting with node “F,” in what order would the nodes be visited in the following graph using Depth-First Search?  Remember to choose the alphabetically “first” node in the event of a tie.

5)     What would the order be if BFS was used instead?

6)     Name and briefly describe an NP-complete problem other than the “Traveling Salesman.”

7)     Draw a Gantt chart for the following data using Shortest-Job-First scheduling:

Job       Time

  j1         10

  j2           2

  j3           3

  j4           7

What is the Average Wait Time for the processes?

8)     Construct a Huffman Code Tree for the following table of characters and use it to determine (fill in) the code for each:

Character	Code	Frequency
a   b   c   d		4 5 12 7

 

9)     What is the impact of a negative weight on a standard shortest-path algorithm?

10)  Under what circumstances will an Adjacency Matrix be better than an Adjacency List?

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of