CS502 Graded Discussion Board (GDB) spring 2012 (July 10 last date)

GDB

Dated: Jul 04, 12

Dear Students! Graded Discussion Board (GDB) will be launched on July 9, 2012 and it will remain open till July 10, 2012. Dynamic Programming is always preferable over greedy approach " Support or contradict this statement with solid arguments. A concise, coherent and to the point comment is preferred over lengthy comment having irrelevant details. Your comment must not be more than 5-7 lines. Comments, posted on regular Lesson's MDB or sent through email will NOT be considered. Any request about such an acceptance will not be catered.

CS502 Quiz # 4 spring 2012( current)

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 32 sec(s) Question # 1 of 10 ( Start time: 07:15:26 PM ) Total Marks: 1 The relationship between number of back edges and number of cycles in DFS is, Select correct option: Both are equal Back edges are half of cycles Back edges are one quarter of cycles There is no relationship between no. of edges and cycles

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 6 sec(s) Question # 2 of 10 ( Start time: 07:16:53 PM ) Total Marks: 1 What algorithm technique is used in the implementation of Kruskal solution for the MST? Select correct option: Greedy Technique Divide-and-Conquer Technique Dynamic Programming Technique The algorithm combines more than one of the above techniques v:shapes="_x0000_i1036"> Saving...

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 3 sec(s) Question # 3 of 10 ( Start time: 07:18:27 PM ) Total Marks: 1 There is relationship between number of back edges and number of cycles in DFS Select correct option: Both are equal. Cycles are half of back edges. Cycles are one fourth of back edges. There is no relationship between back edges and number of cycles. v:shapes="_x0000_i1046">

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 47 sec(s) Question # 4 of 10 ( Start time: 07:20:05 PM ) Total Marks: 1 Dijkstra’s algorithm : Select correct option: Has greedy approach to find all shortest paths Has both greedy and Dynamic approach to find all shortest paths Has greedy approach to compute single source shortest paths to all other vertices Has both greedy and dynamic approach to compute single source shortest paths to all other vertices. v:shapes="_x0000_i1056"> Saving...

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 6 sec(s) Question # 5 of 10 ( Start time: 07:20:58 PM ) Total Marks: 1 Kruskal's algorithm (choose best non-cycle edge) is better than Prim's (choose best tree edge) when the graph has relatively few edges. Select correct option: True False v:shapes="_x0000_i1066">

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 11 sec(s) Question # 6 of 10 ( Start time: 07:22:40 PM ) Total Marks: 1 What is the time complexity to extract a vertex from the priority queue in Prim’s algorithm? Select correct option: log (V) V.V E.E log (E) v:shapes="_x0000_i1072">

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 2 sec(s) Question # 7 of 10 ( Start time: 07:24:10 PM ) Total Marks: 1 You have an adjacency list for G, what is the time complexity to compute Graph transpose G^T.? Select correct option: ? (V + E) ? (V E) ? (V) ? (V^2) v:shapes="_x0000_i1082">

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 0 sec(s) Question # 8 of 10 ( Start time: 07:25:48 PM ) Total Marks: 1 A digraph is strongly connected under what condition? Select correct option: A digraph is strongly connected if for every pair of vertices u, v e V, u can reach v . A digraph is strongly connected if for every pair of vertices u, v e V, u can reach v and vice versa. A digraph is strongly connected if for at least one pair of vertex u, v e V, u can reach v and vice versa. A digraph is strongly connected if at least one third pair of vertices u, v e V, u can reach v and vice versa. v:shapes="_x0000_i1092"> Saving...

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 45 sec(s) Question # 9 of 10 ( Start time: 07:27:25 PM ) Total Marks: 1 You have an adjacency list for G, what is the time complexity to compute Graph transpose G^T ? Select correct option: (V+E) V.E V E

MC090409671 : Nouman Faqeer Quiz Start Time: 07:15 PM Time Left 51 sec(s) Question # 10 of 10 ( Start time: 07:28:23 PM ) Total Marks: 1 What is the time complexity to extract a vertex from the priority queue in Prim’s algorithm? Select correct option: O (log E) ? (V) ? (V+E) O (log V) Saving...

CS502 ASSIGNMENT SOLUTION # 5 spring 2012 (Not sure)

We know that Kruskal’s algorithm takes O(V ) time for initialization, O(E lgE) time to sort
the edges, and O(E(V )) time for the disjoint-set operations, for a total running time of O(V +
E lgE + E(V )) = O(E lgE).
If we knew that all of the edge weights in the graph were integers in the range from 1 to |V |,
then we could sort the edges in O(V + E) time using counting sort. Since the graph is connected,
V = O(E), and so the sorting time is reduced to O(E). This would yield a total running time of
O(V + E + E(V )) = O(E(V )), again since V = O(E), and since E = O(E(V )). The time
to process the edges, not the time to sort them, is now the dominant term. Knowledge about the
weights won’t help speed up any other part of the algorithm, since nothing besides the sort uses
the weight values.
If the edge weights were integers in the range from 1 to W for some constant W, then we could again
use counting sort to sort the edges more quickly. This time, sorting would take O(E +W) = O(E)
time, since W is a constant. As in the first part, we get a total running time of O(E(V )).

CS502 Fundamental of Algorithms Assignment # 05 Spring 2012

CS 502 Fundamental of Algorithms

Assignment # 05

Spring 2012

Total Marks = 20

Deadline

Your assignment must be uploaded / submitted before or on July 04, 2012

Upload Instructions

Please view the assignment submission process document provided to you by the

Virtual University.

Rules for Marking

Please note that your assignment will not be graded if:

• It is submitted after due date

• The file you uploaded does not open

• The file you uploaded is copied from someone else or from internet

• It is in some format other than .doc

Note: Material that is an exact copy from handouts or internet would be graded

Zero marks. Your solution should consist of the material found through different sources and written in your own words.

Assignment Statements:

Question:

Suppose that all edge weights in a graph are integers in the range from 1 to |V|. How fast can you make Kruskal's algorithm run? What if the edge weights are integers in the range from 1 to W for some constant W?

Note:

To solve this question, you are requested to read Kruskal's algorithm form your recommended book with listen the lecture carefully. 

CS502 Assignment # 3 solution 2012

A greedy algorithm forever makes the best available choice. In this case the best available choice is given by the order of the actions: the best selection among the available activities (those compatible with all previous choices) is, by meaning, that of an activity with the latest start. At each choice point, all actions overlap with the already chosen ones are discarded and the latest starting one among those remaining is chosen.

A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. On some problems, a greedy strategy need not produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution.

CS502 Assignment No 5 Solution & Discussion Due Date: 25-01-2012

Question# 1 (5)
Illustrate precisely what you have learned from the course of
Fundamentals of Algorithms (CS-502); your level of analytical
skills has been accelerated up-to which extent ?
Question# 2 (10)
Illustrate the concept of Complexity theory in terms of
Polynomial and Non-deterministic polynomial time algorithms.
Comparison based answer; along with examples of problem
domains of both types; is required.

Read more: CS502 Assignment No 5 Solution & Discussion Due Date: 25-01-2012 - Virtual University of Pakistan http://vustudents.ning.com/group/cs502fundamentalsofalgorithms/forum/topics/cs502-assignment-no-5-solution-discussion-due-date-25-01-2012#ixzz1k0k22hoO


















CS502 Assignment No 5 fall 2011 Download

CS502 Assignment No.3 Solution & Discussion

Recommended book for solving assignment
Cormen, Leiserson, Rivest, and Stein (CLRS) 2001, Introduction to Algorithms, (2nd ed.) McGraw Hill.

Estimated Time 4 hours
To understand the theme of both questions 90 minutes.Question1 solution
implementation maximum time is 90 minutes and for Question2 solution
implementation maximum time is one hour. It all depends upon your sheer
concentration and devotion towards your lecture listening.

Question# 2 (10)
Use the following dynamic programming based recurrence edit distance to find the possible edit scripts while converting PHYSICIAN to STATISICIAN

Question# 2 (10)
You are the project manager in multi-national company and you are asked to deploy
the project for the firm to get the optimal solution and maximum profit in the given
constraints
There are six projects i.e. Tele -Communication Project (P1), Hardware Devices
Production Plant (P2), Software services for the educational institutes (P3), Distance
learning Software Development Centre (P4) , Virtual cell phone development centre
(P5) and Medical diagnoses devices enhancement centre (P6) .Your organization
has Rs.150 billions to invest .If the cost of P1 is Rs.50 billion and profit earned is
Rs.38 Billion, the cost of P2 is Rs.35 billion and profit earned is Rs.22 Billion, the
cost of P3 is Rs.40 billion and profit earned is Rs.25 Billion ,the cost of P4 is Rs.65
billion and profit earned is Rs.58 Billion ,cost of P5 is Rs.55 billion and profit earned
is Rs.45 Billion and the cost of P6 is Rs.60 billion and profit earned is Rs.47 Billion
Your role is to maximize the profit in given amount to launch the projects.
Determine the projects to be selected to earn the maximum profit using 0-1
Knapsack Show complete process.

Read more: CS502 Assignment No.3 Solution & Discussion Due Date:02-01-2012 - Virtual University of Pakistan http://vustudents.ning.com/group/cs502fundamentalsofalgorithms/forum/topics/cs502-assignment-no-3-solution-discussion-due-date-02-01-2012#ixzz1iD73HQOr