We have been working very hard since 2009 to facilitate in your learning Read More. We can't keep up without your support. Donate Now.

www.vustudents.ning.com

 www.bit.ly/vucodes + Link For Assignments, GDBs & Online Quizzes Solution www.bit.ly/papersvu + Link For Past Papers, Solved MCQs, Short Notes & More

# Assignment_4 CS502 - Fundamentals of Algorithms Spring 2015 due date is 7th August 2015.

Fundamentals of Algorithms

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

Views: 7364

Attachments:

### Replies to This Discussion

kuch smjh nh aa ra krna kia h :(

read tw kr liya bt agay kia krna kia chahty hn sir ye nh smjh aya ya hm usy apny words n kesy write krain

write comprehensive summary of any three of the discussed shortest path algorithms in your own words.

4 algorithms hein ap koi sey 3 select kr k apni words mein lekh dey ,PDF file ko read kry sath mein chapter # 8 , jo b algorithm select kia hai start mein thorra os k bare mein btae like definition k basically is mein krte  kia hein ,then os k advantages bta dein agr koi important steps mentions hein un k bare mein lekh dey

but what is the need of PDF file.Why they sent it???

pdf file read kary us main aap ko shortests path k koi sy 3 topic discuss karny hai like dijkstra algorithm floyd-warshall algorithm in ko read kar k apny words main likhy but 2 page sy zayda na hoo

Smj kb aye ga?????

koi to solution dy dy jisy ati hy :(

Spring 2015
Assignment No. 03
Total Marks: 15
Lesson No. 25-35
Objectives
To assess the students’ knowledge of stylistic accuracy and key concepts of Business English
Instructions
1. The assignments sent after the Due Date will not be accepted.
2. The corrupt files will be marked zero.
3. The assignments should be zoomed in at 100%.
4. Plagiarism will NOT be tolerated. Plagiarism means taking credit for someone else’s work by presenting it as your own.
5. No marks will be awarded for copied assignments and the case may be referred to the discipline committee for a suitable action.
6. No assignment will be accepted through e-mail.
7. The font color should be preferably black and font size should be 12 Times New Roman.

Q. 1. Recall the directions for writing INSTRUCTIONS and correct the sentences given in the table. An example is given for guidance. (10)

For example:
Accidental covering of antenna area should be avoided as connectivity problems may be caused.
Correction:
Avoid accidental covering of antenna area as it may cause connectivity problems.

Sr Instructions Corrections

1 Screen protector should not be used as it may cause breakdowns.
2 The power button should be pressed for locking or unlocking the device
4 To start Web search the menu button should be touched and held on home screen.
5 Home button should be pressed to get back to main menu.

Question No.2
By removing the choppiness, improve the following sentences. (2,1,1,1 =5)
1. She took music classes. She had no sense of rhythm. She finally gave up the idea of becoming a musician.
2. The boy asked his father a question. The boy is five years old. The question was
4. I like dogs. Dogs make good pets. Dogs are friendly and loyal.
5. I like movies. I go to movies every weekend. I like action movies best.

1   INTRODUCTION

THE shortest path problem is a problem of finding the shortest path or route from a starting point to a final destination. Generally, in order to represent the shortest path problem we use graphs.  A graph is a mathematical abstract object, which contains sets of vertices and edges.  Edges connect pairs of vertices.  Along the edges of a graph it is possible to walk by moving from one vertex to other vertices.  Depending on whether or not one can walk along the edges by both sides or by only one side determines if the graph is a directed graph or an undirected graph.  In addition, lengths of edges are often called  weights,  and  the  weights  are  normally  used  for calculating the shortest path from one point to another point. In the real world it is possible to apply the graph theory to different  types  of  scenarios.

For  example,  in  order  to represent  a  map  we  can  use  a  graph,  where  vertices represent cities and edges represent routes that connect the cities.  If routes are one-way then the graph will be directed; otherwise, it will be undirected. There exist different types of algorithms that solve the shortest path problem.  However, only several of the most popular conventional shortest path algorithms along with one that uses genetic algorithm are going to be discussed in this paper, and they are as follows:

1.   Dijkstra’s Algorithm

2.   Floyd-Warshall Algorithm

3.   Bellman-Ford Algorithm

4.   Genetic Algorithm (GA)

Other than GA, nowadays, there are also many intelligent shortest path algorithms that have been introduced in several past research papers. For example, the authors in [1] used a heuristic method for computing the shortest path from one point to another point within traffic networks.

Dijkstra’s Algorithm: Explanation and Implementation

For each vertex within a graph we assign a label that determines the minimal length from the starting point s to other vertices v of the graph. In a computer we can do it by declaring an array d[]. The algorithm works sequentially, and in each step it tries to decrease the value of the label of the vertices. The algorithm stops when all vertices have been visited. The label at the starting point s is equal to zero (d[s]=0); however, labels in other vertices v are equal to infinity (d[v]=∞), which means that the length from the starting point s to other vertices is unknown. In a computer we can just use a very big number in order to represent infinity. In addition, for each vertex v we have to identify whether it has been visited or not. In order to do that, we declare an array of Boolean type called u[v], where initially, all vertices are assigned as unvisited (u[v] = false). The Dijkstra’s algorithm consists of n iterations. If all vertices have been visited, then the algorithm finishes; otherwise, from the list of unvisited vertices we have to choose the vertex which has the minimum (smallest) value at its label (At the beginning, we will choose a starting point s). After that, we will consider all neighbors of this vertex (Neighbors of a vertex are those vertices that have common edges with the initial vertex). For each unvisited neighbor we will consider a new length, which is equal to the sum of the label’s value at the initial vertex v (d[v]) and the length of edge l that connects them. If the
resulting value is less than the value at the label, then we have to change the value in that label with the newly obtained value.

d [ neighbors ] = min ( d [ neighbors ] , d[ v ] + l ) (1)

After considering all of the neighbors, we will assign the initial vertex as visited (u[v] = true). After repeating this step n times, all vertices of the graph will be visited and the algorithm
finishes or terminates. The vertices that are not connected with the starting point will remain by being assigned to infinity. In order to restore the shortest path from the starting point to other vertices, we need to identifyarray p [], where for each vertex, where v ≠ s, we will store the number of vertex p[v], which penultimate vertices in the shortest path. In other words, a complete path from s to v is equal to the following statement

P = ( s , … , p [ p [ p [ v ] ] ] , p [ p [ v ] ] , p [ v ] , v ) (2)

Floyd-Warshall Algorithm: Explanation and Implementation

Consider the graph G, where vertices were numbered from 1 to n. The notation dijk means the shortest path from i to j, which also passes through vertex k. Obviously if there is exists edge between vertices i and j it will be equal to dij0, otherwise it can assigned as infinity. However, for other values of dijk there can be two choices: (1) If the shortest path from i to j does not pass through the vertex k then value of dijk will be equal to dijk-1 . If the shortest path from i to j passes through the vertex k then first it goes from i to k, after that goes from k to j. In this case the value of dijk will be equal to dikk-1 + dkjk-1. And in order to determine the shortest path we just need to find the minimum of these two statements:

dij0 = the length of edge between vertices i and j (3)

dijk = min (dijk-1, dikk-1 + dkjk-1) (4)

Genetic Algorithm (GA)

Intelligent algorithms have been introduced in finding optimal shortest paths in many situations that require the systems to search through a very large search space within limited time frame and also in accommodating an ever-changing environment. One of these algorithms is GA. By definition, genetic algorithms are a class or group of ―stochastic search algorithms‖ that are based on biological evolution [8]. GA is mostly used for optimization problems. It uses several genetic operations such as selection, crossover, and mutation in order to generate a new generation of population, which represents a set of solutions (chromosomes) to the current problem. In addition, on average, this new generation is supposed to be better in terms of their overall fitness value as compared to the previous population. Each individual or chromosome within the population will be assigned a fitness value, which is calculated based on a pre-determined fitness function that measures how optimal its solution is in solving the current problem. In order to solve the shortest path problem using the GA [9], we need to generate a number of solutions, and then choose the most optimal one among the provided set of possible solutions. In order to solve the problem, an initial population that forms the first set of chromosomes to be used in the GA is randomly created. Each chromosome represents one possible solution to the current problem at hand. After that, they (chromosomes) are estimated using certain fitness function, which determines how well the solutions are. Taking into account the fitness value of each solution or chromosome, some chromosomes or individuals will be selected (selection operation), and the basic genetic operations such as crossover and mutation are applied on these chromosomes. Then, the fitness value of each chromosome is re-calculated, and the best solutions are selected to be considered for the next generation. This process continues until the criteria of the

given problem will not be achieved. Thus we can identify the following stages of a GA:

Step 1: Determine the fitness function; in our case we need to maximize the following function f(Chk) = (∑edge)-1, where Chk is k-th chromosome and ∑edge is the sum of edges from starting point to final destination.

Step 2: Create initial population - a population thatcontains n individuals. At this stage we do not need tocreate fittest individuals, because it is probable that GA will transfer them into viable population. Inorder to create chromosomes for initial population, we will produce random paths from the starting point to final destination.

Step 3: Selection - the stage of GA that is used to selecttwo chromosomes for genetic operations such as crossover and mutation. There are different types of selection methods; however, the Roulette Wheel selection method is chosen in order to solve the shortest path problem.

Step 4: Crossover - the process of reproduction wheredescendants are inherit traits of both parents mixingthem in some way. Individuals for reproduction will be chosen from whole population (not from the survivors in the first iteration), because we need to keep diversity of individuals, otherwise entire population will be hammered with single copies of one individual. There exist different types of crossover methods; however, for our problem we will use the simplest method, which is called single crossover.

Step 5: Mutation - the act of changing the value of somegene. Mutation keeps the genetic diversity of the population by changing genes of selected chromosome.

If the fittest chromosome does not change after a specific number of iterations, which was described above, then the algorithm will terminate; the most optimal solution is automatically the fittest chromosome among the whole population. Fig. 4 illustrates the flowchart of the shortest path problem’s solution using GA. This diagram is a framework that will be used for the implementation of GA in finding the shortest path or route in a given map of a city named Almaty in Kazakhstan, which is part of our current and future works. The GA used here is quite general in nature except for the part where loops might be introduced while executing GA in finding the most optimal solution; all loops must be removed because loops must not exist in a path.

thanks a lot khan g

## Latest Activity

+M.Tariq Malik liked Fatima's discussion mgt503
7 hours ago
+M.Tariq Malik liked Fatima's discussion MGT503 short notes
7 hours ago
MUHAMMAD IHSAN ULLAH and maria shams are now friends
7 hours ago
Fatima posted discussions
7 hours ago
7 hours ago
+M.Tariq Malik posted discussions
7 hours ago
8 hours ago
нαρρү cнαη∂α] •._.•´¯)'s discussion was featured

8 hours ago

1

2