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

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. 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

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme