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.
请加QQ：99515681 邮箱：99515681@qq.com WX：codehelp
