Final Flashcards
In the backtracking solution to the m-coloring problema node is considered nonpromising if
it has the same color as its parent, and the parent represents an adjacent vertex
One advantage of using an adjacency list rather than an adjacency matrix for representing graphs is
the adjacency list has lower storage space requirements when the graph is sparse
When is an adjacency matrix a good choice for implementing a graph?
When the graph is nearly complete
In a branch-and-bound solution, each node in the decision tree is assigned a value called a bound The bound represents
the value of the partial solution represented by the node being examined
has been shown that the Minimum Cost Spanning Tree problem is in the following categories many as applicable)
NP
has been shown that the Boolean problem is in the following categories.
NP
An NP - Complete problem is
solvable, and the best known solution runs in polynomial time
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.
Dynamic programming
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
Backtracking
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.
0(Log n)
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
O(1)
Constant
What is the big-theta worst case time complexity associated with searching a hash table in which elements were WITHOUT collisions
O(1)
Constant
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
Heap sort
Dijkstra’s Algorithm is an example of the design strategy known as
Greedy techniques
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
Branch and bound
