Final

Question 1

In the backtracking solution to the m-coloring problema node is considered nonpromising if

Answer 1

it has the same color as its parent, and the parent represents an adjacent vertex

Question 2

One advantage of using an adjacency list rather than an adjacency matrix for representing graphs is

Answer 2

the adjacency list has lower storage space requirements when the graph is sparse

Question 3

When is an adjacency matrix a good choice for implementing a graph?

Answer 3

When the graph is nearly complete

Question 4

In a branch-and-bound solution, each node in the decision tree is assigned a value called a bound The bound represents

Answer 4

the value of the partial solution represented by the node being examined

Question 5

has been shown that the Minimum Cost Spanning Tree problem is in the following categories many as applicable)

Answer 5

NP

Question 6

has been shown that the Boolean problem is in the following categories.

Answer 6

NP

Question 7

An NP - Complete problem is

Answer 7

solvable, and the best known solution runs in polynomial time

Question 8

The local UPS dispatcher creates the list of deliveries for various drivers each dayFor each driverthe goal is to minimize the total distance driven by the trucksYet, doing this by hand is highly time-consuming and unreliableYou have been hired to develop a program thatgiven the locations of all the deliveries for a particular driveroutputs the best route for delivery of all the packages For the problem described above, you are to think about the general problem solving techniques studied in class (see below)as well as their relative advantages and disadvantages

Identify what you consider would be the best technique for solving this problem.

Answer 8

Dynamic programming

Question 9

The Department of Motor Vehicles (DMV) has developed three versions of a video based licensing examination When applicants wish to take an exam, they are assigned the next available examinations station. The stations are place side by side in multiple rowsThe DMV wishes you to develop a system that will select one of the three versions of the exam so that no applicant is placed at a station beside behind another applicant who is taking the same exam. The system should also tell the administrator the exam if there is no exam the applicant can take at this point For the problem described above, you are to think about the general problem solving techniques in class (see below) as well as their relative advantages and disadvantages

Identify what you consider would be the best technique for solving this problem

Answer 9

Backtracking

Question 10

Suppose you have a collection of n elements stored in a complete and balanced binary search tree.

The time complexity associated with finding the MEDIAN element is.

Answer 10

0(Log n)

Question 11

Suppose you have a heap of n elements stored in an array starting at index 1. The time complexity associated with finding the parent of the last leaf is

Answer 11

O(1)

Constant

Question 12

What is the big-theta worst case time complexity associated with searching a hash table in which elements were WITHOUT collisions

Answer 12

O(1)

Constant

Question 13

Which of the following sorting algorithms should you use you need to guarantee O(n) log n) running time even in the worst case, but you cannot use any extra space (except for a few local vanables

Answer 13

Heap sort

Question 14

Dijkstra’s Algorithm is an example of the design strategy known as

Answer 14

Greedy techniques

Question 15

A college professor has very high standards for the type of music he listens to regularlyHe owns an extensive library of mp3 files full of classical treasuresincluding works by BachMozart Lennon/McCartney, etc. In order to listen to these artistic masterpieces in his car and other devicesthe professor wishes to place as many as possible in a flash drive with capacity Unfortunately not all of the music fits in the Therefore the professor asks you to write a program that will determine given a list of all the musical selections in his library, an optimal collection of files to be stored in the device so as to enjoymentorder to accomplish this objectivefor each songyou are provided with the size of the corresponding file and with an integer in the range representing the quality of the song For the problem described above you are to think the general problem solving techniques studied in class (see below as well as their relative advantages and disadvantages

Identify what you consider would be the best technique for solving this problem

Answer 15

Branch and bound

Question 16

are part of a team in charge of developing software to help a city in its transponation systemCity officials plan to so they the software to report the shortest travel times among points the For the problem described above you are the general problem solving see belowas well as their relative advantages and

Identify what you consider would be the best technique for solving this problem

Answer 16

Dynamic programming