首页 >
> 详细

CSCI 2520 Data Structures and Applications

Assignment Four

Deadline: 23:55, May. 16, 2020

Total Marks: 100

Submission:

In this Assignment, you need to answer question 1 and question 2 in one pdf file. For question 3 and

4, you need to provide .c file for each question, which can be compiled and give the correct answer,

the name should be q3.c and q4.c respectively.

Then compress all 4 files (one pdf file for q1 q2 and three .c files for q3 and q4 respectively) as one

zip named as your_student_id_assign4.zip and submit it via Blackboard.

1. Shortest-Path Algorithm (20 marks)

Use Dijkstra’s algorithm to calculate the shortest distance from VS to all vertices and the shortest

path from VS to VF.

Note: Please use the table used in lecture (Shortest-Path Algorithm) to represent each step.

Example:

Initial Step Step 1

2. Minimum Spanning Tree (20 marks)

Given an undirected graph, find the minimum spanning tree. The number of the edge connecting

vertex a and vertex b is ab. Like the edge with weight 1 in the graph, its number is 02.

(1) Use Prim’s Algorithm starting from vertex 0 to find the minimum spanning tree, write the

number of the edge added into the minimum spanning tree in turn (if there are many edges

satisfy requirement, choose the edge with minimum number). Please use the table used in

lecture (Prim’s Algorithm) to represent each step.

Example:

Initial Step Step 1

(2) Use Kruskal’s Algorithm and write the number of the valid edge with minimum merging cost

in turn (if there are many edges satisfy requirement, choose the edge with minimum number).

3. The diameter of a graph (30 marks)

Definition: The distance d(u, v) between two vertices u and v is defined as the length of a

shortest path from u to v. The diameter of a graph is the greatest distance between any pair of

vertices.

Now give you a undirected graph, get the diameter of the graph.

The first line of input is the number of nodes N and edges M. Next M lines, contains three

positive integers x, y, w means an undirected edge between vertex x and vertex y with length w.

(The data guarantees that the graph is connected.)

Input:

5 7

1 2 3

1 4 4

4 5 2

2 3 3

3 5 1

1 3 2

3 4 1

Output:

4

4. The power of the team. (30 marks)

We want to build the best team to solve a problem. Now there are n great people on the

waiting list. Everyone has different strengths and weaknesses. The power of the team is the sum of

the strength of the teammate multiplied by the minimum weakness of the team.(Cannikin Law).

Since the budget is not sufficient, we can only choose at most k people. You need to solve this

problem by finding the maximum power of the team you can have.(Hint: use heap to solve it)

The first line of input is n and k. (1<= k <= n <= 10000)

The following two lines are the strengths and weaknesses of the n people. All the values are

less than 10000.

For example:

Input:

5 3

1 2 3 4 5

5 4 3 2 1

Output:

18

(There are two different ways to get the answer. You can choose the 1, 2, 3 and 2, 3, 4 )

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Csse1001 Assignment 3 2021-01-10
- Comp3506/7505 Homework 4 – Graph Algo 2021-01-10
- Unix & C Programming (Comp1000) Assign... 2021-01-10
- Ece 209 Program 3: Market 2021-01-10
- Informatics 1 — Functional Programming 2021-01-10
- Cisc/Cmpe 452/Cogs400 Assignment 2 2021-01-10
- Fit2100 Operating Systems Assignment #... 2021-01-10
- Csci 1100 — Homework 5 2021-01-10
- Comp9444 Neural Networks And Deep Lea... 2021-01-10
- Assignment Case: German Credit 2021-01-10
- 48024 Applications Programming Assign... 2021-01-10
- Cs 405/805-001: Computer Graphics Ass... 2021-01-10
- Cse 434, Sln 70608 — Computer Networks 2021-01-10
- Corpfin 2503 - Business Data Analytics 2021-01-10
- Cis 455 / 555: Internet And Web System... 2021-01-10
- Cs110留学生编程代写、代做c++程序实验、Program程序语言调试帮做 2021-01-10
- Csc8021程序代做、代写networks编程语言、代做c/C++，Jav 2021-01-10
- 代写program编程语言、代做python，C++，Java程序设计帮做j 2021-01-10
- R编程课程代写、代做program程序语言、R程序实验代做代写databas 2021-01-09
- Data编程设计代做、代写java程序语言、Java程序实验调试代写r语言程 2021-01-09