1. Homepage
  2. Programming
  3. CSC3100 Data Structures Fall 2022 Programming Assignment II: Special Shortest Path, Median Search Tree, Football Match and Prefix

CSC3100 Data Structures Fall 2022 Programming Assignment II: Special Shortest Path, Median Search Tree, Football Match and Prefix

Contact Us On WeChat
Hong KongCUHKCSC3100Data StructuresSpecial Shortest Path Median Search Tree Football Match and PrefixJava

CSC3100 Data Structures Fall 2022 Programming Assignment II CourseNana.COM

1 Problem 1: Special Shortest Path CourseNana.COM

1.1 Statement CourseNana.COM

City C consists of n nodes, representing different places. There are m edges between these nodes. For the edge ei = (ui , vi , wi ), there is a bidirectional(undirected) trail connecting ui and vi with length of wi. CourseNana.COM

For a path P = {pi}, consisting of edges p1, p2, p3, · · · , pk, the length of each edge is li = wpi . Normally, passing the edge pi with length li will cost li units of energy. Specially, if li = K · li1, then passing this edge will only cost (K 1) · li1 units of energy. CourseNana.COM

Alice is starting from the node 1. Alice wants to know how many units of energy it will take at least to visit the node x, for any x. If x is unreachable from the start point(node 1), you should output 1 as the result. CourseNana.COM

1.2 Input Format CourseNana.COM

The first line consists of three integer numbers n,m,K. The following m lines each consists of three integer numbers u, v, w to describe a bidirectional trail. CourseNana.COM

1.3 Output Format CourseNana.COM

You need to output a line consisting of n integers, each representing the minimum units of energy to reach node i from node 1. CourseNana.COM

2 Problem 2: Median Search Tree 2.1 Statement CourseNana.COM

If the sorted array of all the values in the set is {ai}ni=1, let t = n/2, then the median 2k values are {atk+1, · · · , at+k}. CourseNana.COM

Barbara has got a set of values with size of 2k initially. Barbara wants to do m operations on it. Each operation belongs to the following 3 types: CourseNana.COM

1 w: insert a value w.
2: output all the median 2k values, i.e. atk+p, 1 p 2k.
3 p: delete the p-th value among median 2k values, i.e. atk+p. CourseNana.COM

We guarantee that all the values will be distinct and the size of the set is always at least 2k. 2.2 Input Format CourseNana.COM

The first line consists of two integer numbers m,k. The second line consists of the 2k values in the initial set. Then, the following m lines each consists of the command of an operation. CourseNana.COM

2.3 Output Format CourseNana.COM

You need to output one line for each query(operation 2). Each line consists of 2k positive integers, the median 2k values of the set at that time in ascending order. CourseNana.COM

2.6 Hints CourseNana.COM

You can solve this problem with heaps. CourseNana.COM

3 Problem 3: Football Match 3.1 Statement CourseNana.COM

While the FIFA World Cup is being held in Qatar, BLGG is organizing a football tournament in LGU, too. CourseNana.COM

There are n teams in this tournament, numbered from 1 to n. Each team has its popularity, and the popularity of team i is ai. A match between i and j will gain ai × aj MOD M attractions. CourseNana.COM

When a football team loses a match, it will be eliminated from the tournament. At the end, the team left standing will be the champion of this tournament. CourseNana.COM

BLGG is wondering that what the maximum sum of the attractions of the (n 1) matches. 3.2 Input Format CourseNana.COM

The first line contains two integers n and M. The second line contains n integers a1 , · · · , an . CourseNana.COM

3.3 Output Format CourseNana.COM

Output one integer representing the maximum sum of the attractions of the (n 1) matches. CourseNana.COM

4 Problem 4: Prefix 4.1 Statement CourseNana.COM

You are given n strings s1, s2, · · · , sn and q queries. In ith query, you are given a string ti, please find out how many strings in s1, s2, · · · , sn begins with ti. CourseNana.COM

4.2 Input Format CourseNana.COM

The first line is an integer n.
Each of the next
n lines contains a string, respectively. The (i + 1)th line of input is si. The (n + 2)th line of input is an integer q.
Each of the next
q lines contains a string, respectively. The (n + 2 + i)th line of input is ti. CourseNana.COM

4.3 Output Format CourseNana.COM

Output q lines. The ith line contains the answer of ith query. 4.4 Sample Input/Output CourseNana.COM

4.5 Constraints CourseNana.COM

All strings only contain lowercase letters. CourseNana.COM

Since the input might be very large, fast input method such as BufferedReader in Java is required. CourseNana.COM

A. Requirements CourseNana.COM

Code (90%) CourseNana.COM

The distribution of programming grade is 20%, 20%, 25%, 25% for the four problems respectively. CourseNana.COM

You can write your code in Java, Python, C, or C++. The time limit may vary among different languages, depending on the performance of the language. Your code must be a complete runnable program instead of only a function. We guarantee test data strictly compliance with the requirements in the description, and you do not need to deal with cases where the input data is invalid. CourseNana.COM

We provide a example problem to better illustrate the information above. CourseNana.COM

Report (10%) CourseNana.COM

You also need to write a report to explain the following: What are the possible solutions for the problem? How do you solve this problem?
Why is your solution better than others? CourseNana.COM

Please note that the maximum number of pages allowed for your report is 5 pages. CourseNana.COM

Remember that the report is to illustrate your thinking process. Keep in mind that your report is supposed to show your ideas and thinking process. We expect clear and precise textual descriptions in your report, and we do not recommend that you over-format your report. CourseNana.COM

B. Example Problem: A + B Problem Description CourseNana.COM

Given 2 integers A and B, compute and print A + B CourseNana.COM

Input CourseNana.COM

Two integers in one line: A, and B CourseNana.COM

Output CourseNana.COM

One integer: A + B CourseNana.COM

Sample Input I Sample Output I CourseNana.COM

123 CourseNana.COM

Problem Scale & Subtasks CourseNana.COM

For 100% of the test cases, 0 A,B 106 CourseNana.COM

Solutions CourseNana.COM

Java CourseNana.COM

import java.util.*; CourseNana.COM

public class Example {
public static void main(String[] args) {
CourseNana.COM

int a, b;
Scanner scanner = new Scanner(System.in); a = scanner.nextInt();
b = scanner.nextInt();
scanner.close();
System.out.println(a + b);
CourseNana.COM

} } CourseNana.COM

Python CourseNana.COM

AB = input (). split () CourseNana.COM

A, B = int(AB[0]), print(A + B) CourseNana.COM

C CourseNana.COM

#include <stdio.h> CourseNana.COM

int main(int argc, { CourseNana.COM

int(AB[1]) CourseNana.COM

char *argv[]) CourseNana.COM

int A, B; scanf("%d%d", &A, &B); printf("%d\n", A + B); return 0; CourseNana.COM

} CourseNana.COM

C++ CourseNana.COM

#include <iostream > CourseNana.COM

int main(int argc, char *argv[]) { CourseNana.COM

int A, B;
std::cin>> A >> B;
std::cout<< A + B << std::endl; return 0;
CourseNana.COM

} CourseNana.COM

  CourseNana.COM

Get Expert Help On This Assignment

Scan above qrcode with Wechat

Hong Kong代写,CUHK代写,CSC3100代写,Data Structures代写,Special Shortest Path代写, Median Search Tree代写, Football Match and Prefix代写,Java代写,Hong Kong代编,CUHK代编,CSC3100代编,Data Structures代编,Special Shortest Path代编, Median Search Tree代编, Football Match and Prefix代编,Java代编,Hong Kong代考,CUHK代考,CSC3100代考,Data Structures代考,Special Shortest Path代考, Median Search Tree代考, Football Match and Prefix代考,Java代考,Hong Konghelp,CUHKhelp,CSC3100help,Data Structureshelp,Special Shortest Pathhelp, Median Search Treehelp, Football Match and Prefixhelp,Javahelp,Hong Kong作业代写,CUHK作业代写,CSC3100作业代写,Data Structures作业代写,Special Shortest Path作业代写, Median Search Tree作业代写, Football Match and Prefix作业代写,Java作业代写,Hong Kong编程代写,CUHK编程代写,CSC3100编程代写,Data Structures编程代写,Special Shortest Path编程代写, Median Search Tree编程代写, Football Match and Prefix编程代写,Java编程代写,Hong Kongprogramming help,CUHKprogramming help,CSC3100programming help,Data Structuresprogramming help,Special Shortest Pathprogramming help, Median Search Treeprogramming help, Football Match and Prefixprogramming help,Javaprogramming help,Hong Kongassignment help,CUHKassignment help,CSC3100assignment help,Data Structuresassignment help,Special Shortest Pathassignment help, Median Search Treeassignment help, Football Match and Prefixassignment help,Javaassignment help,Hong Kongsolution,CUHKsolution,CSC3100solution,Data Structuressolution,Special Shortest Pathsolution, Median Search Treesolution, Football Match and Prefixsolution,Javasolution,