COMP2013代做、代寫Data Structures and Algorithms
            COMP2013代做、代寫Data Structures and Algorithms

            時(shí)間:2024-04-24  來源:  作者: 我要糾錯(cuò)



            COMP2013 Data Structures and Algorithms
            Programming Assignment 2 Deadline: 10:00am, 22th April, 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 Filename format Filename example
            C++ mainStudentID.cpp main10987654d.cpp
            Java mainStudentID.java main10987654d.java
            Python mainStudentID.py main10987654d.py
            - We only accept file types in .cpp, .java, .py. We do not accept file types like .ipynb, .h, etc.
            Section 1. Problem
            You have n pipes with lengths in meters. You need to connect all these pipes into one pipe. You can
            connect two pipes into one at a time. For two pipes with length i and j meters respectively, the cost to
            connect them is 𝑡𝑡(𝑖𝑖,𝑗𝑗) = 𝑚𝑚𝑚𝑚𝑚𝑚(𝑖𝑖,𝑗𝑗) + 3; the connected pipe has length i+j meters.
            The task is to minimize the total cost to connect all n pipes into one pipe, where the total cost is the sum
            of all connection costs.
            Example: you have 4 pipes in length 6, 5, 2, 8. After connecting all pipes, you will get one pipe with
            length 21 meters. Your task is to minimize the total cost to connect these pipes into one. There can be
            different ways to perform the connections. Given 4 pipes, there are  
            4
            2  ×  
            3
            2  = 18 ways to perform the
            connections, and below shows one possible way (not with optimal cost),
            - Connect pipes with length 6,5 first, with cost 9, and result in three pipes with length 11,2,8
            - Then connect pipes with length 11, 2, with cost 14, and result in two pipes with length 13, 8
            - Then connect pipes with length 13, 8, with cost 16, and result in one pipe with length 21.
            - The total cost of the connections above is 9+14+16=39.
            For this example, an optimal way to connect pipes should have minimum cost 34.
            Given n pipes, implement a greedy algorithm that can correctly obtain the minimum total cost to connect
            them into one pipe, adhering to the requirements above. Your program should have time complexity
            O(nlogn). (You do not need to prove the optimality of your greedy algorithm.)
            Section 2. input and output of your format
            In the table below, it shows a sample of the input file and the output of your program. Your program
            should take as input a filename (e.g., file1.txt), and then read the integers (one integer per line) in the file.
            These integers are the length of pipes. The number of non-empty lines in the file is the number of pipes
            you need to handle.
            Your program will output an integer value to the screen, which is the minimum cost obtained by your
            program.
            Sample input file “file1.txt” The output on screen (stdout)
            6 34
            5
            2
            8
            We will run your program by a command line like:
            where the argument “file1.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.
            Notes:
            - We will use 10 test cases to grade your program
            - The pipe length is positive integer in range [1, 1000]
            - In a test case, the number of pipes is at most 10000.
            Implementation Instructions:
            In your implementation, you can use existing libraries that support data structures like list, stack, queue,
            min-heap, max-heap, priority-queue, etc. (In other words, you do not need to implement these
            fundamental data structures)
            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
            Section 3: Grading Criteria
            Naming conventions, compilation and execution commands
             Before submission, rename your program to
             mainStudentID.cpp, e.g., main10987654d.cpp
             OR mainStudentID.java, e.g., main10987654d.java
             OR mainStudentID.py, 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.
            Language Command line
            C++ (after compilation) ./mainStudentID file1.txt
            Java (after compilation) java mainStudentID file1.txt
            Python python mainStudentID.py file1.txt
             We will run your program by a command line like:
             ./mainStudentID file1.txt
             OR java mainStudentID file1.txt
            OR python mainStudentID.py file1.txt
            where the argument “file1.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
            Test files for grading
            Total marks: 100 marks
            Your program will be graded by using 10 test files.
            For each test case, if your program can return the correct output within 1 minute, it is a successful case
            and you get 10 marks. Otherwise, this is a failed case with 0 marks.
            - The running time of your program will be measured on the COMP apollo server.
            If your program is not a greedy approach, extra 50 marks will be deducted from the total marks you
            get from the 10 test cases above. Final grade of the assignment is in the range [0,100].
            Appendix
            (1) How to activate your COMP account?
            Please click the following link to activate your COMP account:
            https://acct.comp.polyu.edu.hk/
            according to the instructions in:
            https://acct.comp.polyu.edu.hk/files/COMPStudentAccountSelfActivation.pdf
            (2) How to login the COMP apollo server?
            [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.
            [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.

            請(qǐng)加QQ:99515681  郵箱:99515681@qq.com   WX:codinghelp









             

            標(biāo)簽:

            掃一掃在手機(jī)打開當(dāng)前頁
          1. 上一篇:代寫DTS101TC、代做Python設(shè)計(jì)編程
          2. 下一篇:CS 161代做、Java/Python程序代寫
          3. 無相關(guān)信息
            昆明生活資訊

            昆明圖文信息
            蝴蝶泉(4A)-大理旅游
            蝴蝶泉(4A)-大理旅游
            油炸竹蟲
            油炸竹蟲
            酸筍煮魚(雞)
            酸筍煮魚(雞)
            竹筒飯
            竹筒飯
            香茅草烤魚
            香茅草烤魚
            檸檬烤魚
            檸檬烤魚
            昆明西山國(guó)家級(jí)風(fēng)景名勝區(qū)
            昆明西山國(guó)家級(jí)風(fēng)景名勝區(qū)
            昆明旅游索道攻略
            昆明旅游索道攻略
          4. 福建中專招生網(wǎng) NBA直播 短信驗(yàn)證碼平臺(tái) 幣安官網(wǎng)下載 WPS下載

            關(guān)于我們 | 打賞支持 | 廣告服務(wù) | 聯(lián)系我們 | 網(wǎng)站地圖 | 免責(zé)聲明 | 幫助中心 | 友情鏈接 |

            Copyright © 2025 kmw.cc Inc. All Rights Reserved. 昆明網(wǎng) 版權(quán)所有
            ICP備06013414號(hào)-3 公安備 42010502001045

            主站蜘蛛池模板: 国产激情一区二区三区四区| 精品国产日韩亚洲一区91| 不卡一区二区在线| 曰韩精品无码一区二区三区| 亚洲熟妇无码一区二区三区导航| 国产91精品一区| 亚洲AV无码国产一区二区三区 | 亚洲av无码一区二区乱子伦as| AV无码精品一区二区三区| 99国产精品一区二区| 无码人妻一区二区三区在线水卜樱 | 久久精品视频一区二区三区| 国产成人精品一区在线 | 国产高清一区二区三区视频| 日韩最新视频一区二区三| 台湾无码一区二区| 中文字幕一区一区三区| 中文字幕一区一区三区| 午夜影院一区二区| 99精品国产高清一区二区麻豆| 日韩一区精品视频一区二区| 2014AV天堂无码一区| 丝袜人妻一区二区三区网站| 成人免费区一区二区三区| 国产一区二区内射最近更新| 一区二区乱子伦在线播放| 污污内射在线观看一区二区少妇 | 亚洲av午夜精品一区二区三区| 日韩精品人妻av一区二区三区 | 精品性影院一区二区三区内射 | 国产精品亚洲一区二区三区久久| 怡红院一区二区在线观看| 日本精品一区二区在线播放| 国产一区中文字幕| 熟妇人妻系列av无码一区二区 | 黑人一区二区三区中文字幕| 国产成人av一区二区三区在线| 无码毛片一区二区三区视频免费播放 | 亚洲欧洲专线一区| 免费一本色道久久一区| 午夜视频久久久久一区 |