Week 13
Objectives : to learn more about computability and revise important concepts.- * Given above graph, trace through Dijkstra's algorithm for finding the
shortest path starting from
- vertex A.
- vertex F.
- * State the loop invariant of Dijkstra's Algorithm for finding shortest
path.
- This fragment of Dijkstra's algorithm assumes an adjacency matrix
representation of graph.
if (weight[u] > weight[v] + matrix[u][v]) weight[u] = weight[v] + matrix[u][v];Assume Carranos graph representation of adjacency list using a vector of maps, give c++ code for above fragment of a member function. - Given bins of size 13, and items of size : 9,9,8,5,5,3,3,3,2, what is optimal number of bins? Trace through Decreasing First-Fit Strategy and Decreasing Best-Fit strategies for bin-packing.
- Write an algorithm for solving the following problem. Given an array a[0..n-1] of integers, determine the maximum sum which can be obtained by the addition of any of the elements in a. For example if a contains 3,9,-5,2 then the maximum sum will be obtained by adding 3,9,2 which gives 14.
- Write an algorithm which given an array a[0..4] of positive ints and a target t will determine if it possible to add one or more of the elements in a to give t i.e. is there a subset of values in a which sum to t? For example if a contains 3,6,2,9,8 and the target is 10 then it is possible to obtain 10 by adding 8 and 2.
- Discuss the efficiency of your algorithm.
graph