代做COMP2013、代写 c++/java，Python 编程

日期：2024-03-17 09:29

COMP2013 Data Structures and Algorithms

Programming Assignment 1 Deadline: 10:00am, 25th March, 2024

Instructions

? Submit the soft-copy of your program to Learn@PolyU

? You can only submit one program file (either C++ or Java or Python),

and the filename must follow the format below.

  Language

C++

Java Python

Problem

Filename format mainStudentID.cpp mainStudentID.java mainStudentID.py

Filename example

main10987654d.cpp main10987654d.java main10987654d.py

              Section 1:

Input: Output:

An array A[0..n–1] (of comparable elements)

The total number of pairs (i, j) such that i < j and A[i] > A[j].

In this problem, the input can be an array of integers or an array of strings.

(1.1) Comparisonforstrings

We use the lexicographical order to compare strings. Let s[x] denote the x-th letter of the string s.

Given two strings s[0..sL–1] and r[0..rL–1], s>r holdsif

? risaprefixofs(i.e.,rL<sLand?p=0..rL-1s[p]=r[p]) OR ? there exists a position k such that s[k]>r[k] and ?p=0..k-1 s[p]=r[p]

Examples:

? charge > balance ? balance > bal

? bbbbbb > bbbbba

(1.2) Examplesfortheproblem Input

Output Explanation

5 5 pairs satisfy the requirement:

(0,1), (2,3), (2,5), (3,5), (4,5).

5 5 pairs satisfy the requirement: (0,1), (2,3), (2,5), (3,5), (4,5).

        Example for an array of integers Example for an array of strings

A[0..6] =

| 31 | 24 | 85 | 76 | 93 | 50 | 93 |

A[0..6] =

| “charge” | “balance” | “wind” | “thunder” | “zoo” | “mile” | “zoo” |

       p. 1

Section 2: Input and Output Format

Here are samples of the input file and the output of your program.

Sample input file “file1.txt” The output on screen (stdout)

    integer

7

31

24

85 76 93 50 93

  5

  Sample input file “file2.txt” The output on screen (stdout)

  string

7

charge

balance

wind

thunder

zoo

mile

zoo

  5

The format of the input file is as follows:

? the 1st line shows the type (either integer or string), ? the 2nd line shows the number of elements,

? each subsequent line shows an element.

The number of elements is in the range 1.. 10000000.

For integers, the elements are in the range 1..10000000.

For strings, the elements have length at most 20 and contain lower-case letters only.

We will run your program by a command line like:

 Language

C++ (after compilation) Java (after compilation) Python

Command line

./mainStudentID input123.txt

java mainStudentID input123.txt python mainStudentID.py input123.txt

          where the argument “input123.txt” is an example of the input filename. Your program should only output the result number.

Please follow the above output format and DO NOT print any extra information.

p. 2

Section 3: Hints

(3.1) Comparisonsforstrings

You are allowed to use operator or standard library function (e.g., in C++, Java, Python) to perform lexicographic comparison for string. Examples:

? C++: https://cplusplus.com/reference/string/string/compare/

? Java: https://docs.oracle.com/javase/tutorial/java/data/comparestrings.html

? Python: https://docs.python.org/3/library/stdtypes.html#comparisons Please test them before using them in your program.

(3.2) Hintsforprogramming

? Use a large enough integer type (e.g., long) to prevent “integer overflow” in counting.

? A simple program is to use nested for-loops. Its time complexity is O(n2). It is acceptable for

small input file but too slow for large input file.

? If you wish to obtain higher marks, try to use the “divide-and-conquer” approach in your

program. It is possible to achieve the time complexity O(n log n) time.

? Some programming tricks can be used to speedup your program by a constant factor.

    p. 3

Section 4: Grading Criteria

(4.1) Namingconventions,compilationandexecutioncommands

? Before submission, rename your program to mainStudentID.cpp,

OR mainStudentID.java, OR mainStudentID.py,

e.g., main10987654d.cpp e.g., main10987654d.java e.g., main10987654d.py

  ? [C++ and Java only] Make sure that you can compile your program using the command: g++ mainStudentID.cpp -o mainStudentID

OR javac mainStudentID.java

o No marks will be given if your program cannot be compiled.

? We will run your program by a command line like: ./mainStudentID input123.txt

OR java mainStudentID input123.txt

OR python mainStudentID.py input123.txt where the argument “input123.txt” is an example of the input filename.

Make sure that you can execute the above commands on the COMP apollo server successfully. Otherwise, no marks will be given. The current versions on apollo are as follows:

g++ (GCC) 4.8.5, javac 1.8.0_20, Python 2.7.5

(4.2) Testfilesforgrading

Total marks: 100%

Your program will be graded by using 10 test files.

? 5 test files for integers

? 5 test files for strings

The running time of your program will be measured on the COMP apollo server.

For each test file,

if your program can produce the correct output within 1 minute, then you get +10 marks.

      p. 4

Appendix

(1) How to activate your COMP account?

Please click the following link to activate your COMP account:

https://acct.comp.polyu.edu.hk/ https://acct.comp.polyu.edu.hk/files/COMPStudentAccountSelfActivation.pdf

(2) How to login the COMP apollo server?

according to the instructions in:

    [Step 1]

Use PuTTY (or any SSH client program)

Enter the host name

csdoor.comp.polyu.edu.hk

Click the “Open” button.

If you see the message “The host key is not cached for this server...”,

just accept to continue.

    p. 5

  [Step 2]

Enter your COMP account username and password.

Note that, when you are entering the password, it is not displayed in PuTTY.

      [Step 3]

Enter the hostname apollo

Then enter your COMP account password (the same as in Step 2).

     [Step 4]

Use WinSCP (or any SFTP client program).

Enter the host name csdoor.comp.polyu.edu.hk Enter your COMP account username and password. Upload your program to the server.

p. 6