<em id="rw4ev"></em>

      <tr id="rw4ev"></tr>

      <nav id="rw4ev"></nav>
      <strike id="rw4ev"><pre id="rw4ev"></pre></strike>
      合肥生活安徽新聞合肥交通合肥房產生活服務合肥教育合肥招聘合肥旅游文化藝術合肥美食合肥地圖合肥社保合肥醫院企業服務合肥法律

      代做COMP10002、c++編程設計代寫
      代做COMP10002、c++編程設計代寫

      時間:2024-04-26  來源:合肥網hfw.cc  作者:hfw.cc 我要糾錯



      The University of Melbourne
      School of Computing and Information Systems
      COMP10002 Foundations of Algorithms
      Semester 1, 2024
      Assignment 1
      Due: 4pm Tuesday 30 April 2024
      Version 1.1
      1 Learning Outcomes
      In this assignment, you will demonstrate your understanding of arrays, pointers, input processing, and
      functions. You will also extend your skills in terms of code reading, program design, testing, and debugging.
      2 The Story...
      Given an array of n **dimensional values, we have learned that sorting the array will enable a fast O(log2 n)-
      time search to look up for a search key (that is, a number to be located in the array). In this assignment,
      we will extend our search capability to an array of 2-dimension values, where the ordering is less obvious.
      Figure 1: A map query example
      Consider digital mapping services like Google Maps. Such services have millions of records of business and points of interest (POIs), if not more. A common query is to show the
      POIs in the mapping app view of a user. See Figure 1
      for example, where a user is querying for cafes in the Melbourne CBD. Such queries happen frequently – Google Maps alone
      serves over 1 billion monthly active users (https://zipdo.co/
      statistics/google-maps/). For services of such a scale, a simple linear search over all POI records for each query is suboptimal.
      In this assignment, we will design an algorithmic solution for more efficient query processing. Our aim is to achieve (approximately) an
      O(log2 n + k)-time search for 2-dimensional points on maps, where n
      represents the total number of POI records in a database, and k represents the number of POIs satisfying a query.
      3 Your Task
      You will be given a skeleton code file named program.c for this assignment. The skeleton code file contains a main function that has been
      completed (which you do not have to modify unless you want to). There
      are a few other functions which are incomplete. You need to add code to
      complete the functions for the following tasks.
      The given input to the program consists of 15 lines of numbers as follows:
      • The first 10 lines contains the IDs (unique integers) and coordinates (real numbers) of 50 POI records
      separated by ‘;’, to run our query algorithms upon. The POI records are sorted by their IDs in
      ascending order, and their IDs are always from 0 to 49 to simplify the assignment. Each line contains
      1
      five POI records. For the sample input shown below, the first record has ID 0, and its coordinates in
      the x- and y-dimensions are 16.4 and 69.4, respectively.
      • The next five lines represent the queries. Each line contains four real numbers representing a query
      range (xlb, ylb, xub, yub), where xlb and ylb represent the lower bounds in the x- and y-dimensions of
      the query range, while xub and yub represent the respective upper bounds. Intuitively, each query
      range is a rectangle whose bottom left corner is at (xlb, ylb) and top right corner is at (xub, yub). You
      may assume that xlb < xub and ylb < yub always hold.
      You may assume that the test data always follow the format above, and that each coordinate value and query
      range bound is in the range of (0, 100). No input validity checking is needed. See below for a sample input.
      0 16.4 69.4; 1 88.7 13.3; 2 1.8 98.8; 3 85.1 96.1; 4 15.4 22.3;
      5 79.4 61.9; 6 97.3 68.1; 7 68.3 9.3; 8 46.8 43.3; 9 87.3 42.3;
      10 38.9 46.5; 11 87.5 34.6; 12 34.7 40.9; 13 5.8 37.4; 14 28.6 55.8;
      15 60.7 70.4; 16 **.5 63.1; 17 76.8 92.1; 18 24.7 4.4; 19 15.3 46.4;
      20 15.5 51.7; 21 55.1 99.5; 22 95.0 13.2; 23 54.0 97.1; 24 6.4 37.8;
      25 66.0 16.4; 26 59.2 88.2; 2**9.4 81.6; 28 79.9 68.5; 29 61.5 0.5;
      30 5.2 69.1; 31 76.9 74.9; ** 29.**0.3; 33 19.5 78.5; 34 12.1 83.4;
      35 35.6 1.2; 36 98.5 97.5; 37 95.**8.4; 38 80.0 **.7; 39 22.2 **.5;
      40 80.7 42.0; 41 9.8 10.9; 42 81.0 93.4; 43 97.5 30.4; 44 28.2 44.1;
      45 37.2 97.0; 46 **.6 9.8; ** 68.5 17.9; 48 65.5 50.0; 49 21.0 48.0;
      11.8 3.5 53.5 28.5
      19.**8.6 **.1 66.8
      16.9 67.6 74.8 93.4
      49.0 70.**4.9 74.9
      75.1 25.1 99.9 49.9
      Figure 2 plots the 50 POIs and the five query ranges in the sample input, where the bottom left point is
      POI #41 at (9.8, 10.9), and the bottom left rectangle (the one in red) is the first query range.
      Figure 2: The sample POIs and query ranges
      3.1 Stage 1: Read the Input and Answer the First Query (Up to 5 Marks)
      Your first task is to understand the skeleton code. Then, you should add code to the stage_one function to
      (1) read input POI IDs and coordinates into the arrays ids and coordinates, respectively, and read query
      ranges into queries, (2) identify all POIs within the first query range using linear search, and (3) print out
      such POIs (print “none” if no such POIs can be found).
      The output for this stage given the above sample input should be (where “mac:” is the command prompt):
      mac: ./program < test0.txt
      Stage 1
      ==========
      POIs in Q0: 4 18
      2
      Here, Q0 refers to the first input query, that is, we use Qi to refer to the i-th input query.
      Hint: To test if a point at (x, y) is within a query range (xlb, ylb, xub, yub), we test the following inequalities:
      xlb ≤ x ≤ xub and ylb ≤ y ≤ yub (1)
      In the sample input above, for POI #4 at (15.4, 22.3) and the first query range (11.8, 3.5, 53.5, 28.5),
      we have:
      11.8 ≤ 15.4 ≤ 53.5 and 3.5 ≤ 22.3 ≤ 28.5
      Thus, POI #4 is within the first query range and is part of the Stage 1 output. The same applies for POI #18.
      As this example illustrates, the best way to get data into your program is to edit it in a text file (with a
      “.txt” extension, any text editor can do this), and then execute your program from the command line,
      feeding the data in via input redirection (using <). In the program, we will still use the standard input
      functions such as scanf to read the data fed in from the text file. Our auto-testing system will feed input
      data into your submissions in this way as well. You do not need to (and should not) use any file operation
      functions such as fopen or fread. To simplify the assessment, your program should not print anything
      except for the data requested to be output (as shown in the output example).
      You should plan carefully, rather than just leaping in and starting to edit the skeleton code. Then, before
      moving through the rest of the stages, you should test your program thoroughly to ensure its correctness.
      You should create sub-functions to complete the tasks. As stated in the marking rubric, you need to create
      at least two self-defined functions in your final submission for the assignment.
      3.2 Stage 2: Sort and Query POIs by the x-coordinates (Up to 10 Marks)
      In Stage 1, we have examined all POI records to identify those within a query range. In the following stages,
      we aim to establish some ordering over the POIs, such that the unpromising POIs can be filtered without
      being examined, and query processing can be accelerated. For Stage 2, we will start by ordering the POIs
      by their x-coordinates.
      Stage 2.1. Modify the given sort_by_x function, such that it takes the arrays of ids and coordinates
      as the input, and sorts both arrays based on the x-coordinates of the POIs in ascending order (that is,
      increasing order) with the insertion sort algorithm. For simplicity, you may assume that the x-coordinates
      of all input POIs are unique (in reality, if there are repeating x-coordinates, we can further sort by the
      y-coordinates). The stage_two function calls the modified sort_by_x function and performs the sorting.
      Stage 2.2. Now further add code to the stage_two function to process all the input queries. For each query,
      we start with a linear scan (Scan 1) to find the POI with the smallest x-coordinate that is greater than or
      equal to xlb of the query range. Let us call this POI the lower bound POI. From this POI, we continue with
      the linear scan (Scan 2), until we reach a POI whose x-coordinate exceeds xub of the query range. For each
      POI visited during Scan 2, we examine whether it is within the query range in the y-dimension (we call this
      a POI-in-query test), if so, it is part of the query answer and is outputted.
      The output for this stage is the IDs of the POIs within each query, and the number of POI-in-query tests
      run for each query. For example, given the above sample input, the sample output of this stage is:
      Stage 2
      ==========
      POIs in Q0: 4 18; No. POI-in-query tests: 17
      POIs in Q1: none; No. POI-in-query tests: 11
      POIs in Q2: 33 39 26 27 15; No. POI-in-query tests: 24
      POIs in Q3: none; No. POI-in-query tests: 1
      POIs in Q4: 38 40 9 11 43; No. POI-in-query tests: 16
      For example, as shown in Figure 2, for Q0, there are 17 points between xlb and xub (that is, the two vertical
      edges) of Q0. Thus, 17 POI-in-query tests need to be run to find the two POIs #4 and #18 within the query
      range. Now the number of POI-in-query tests per query is just up to 24 (for the five input queries), that is,
      fewer than half of all POIs, rather than examining all POIs for a query as done in Stage 1.
      For a challenge and not for submission, see if you can replace Scan 1 with a binary search.
      3
      3.3 Stage 3: Sort POIs by Coordinates of Both Dimensions (Up to 15 Marks)
      Stage 3 further incorporates the y-coordinates into POI ordering. Figure 3 illustrates the idea. We partition
      the space with an m × m regular grid. In this assignment, m = 8. A curve (the black dotted line in the
      figure) goes through each cell in the grid exactly once. The order that the curve goes through the cells gives
      a curve value for each cell. For example, as shown in the figure, the bottom left cell has a curve value of 0.
      The cell to its right has a curve value of 1, while the cell above it has a curve value of 2. The top right cell
      has a curve value of 63 (as there are 8 × 8 = 64 cells in total).
      Figure 3: Curve-based POI ordering
      For a POI with coordinates (x, y), we can calculate the curve value corresponding to the cell that encloses
      the POI (“the curve value of the POI” for short hereafter) as follows. First, we calculate the column number
      (col num) and row number (row num) of the POI using the following equations.
      col num = ⌈
      x
      12.5
      ⌉ − 1; row num = ⌈
      y
      12.5
      ⌉ − 1 (2)
      Here, ⌈z⌉ is the ceiling function. It returns the smallest integer greater than or equal to z. In C, ceil()
      from math.h provides an implementation of this function. The constant 12.5 = 100
      8
      is the width (height) of
      each column (row) – recall that 100 is the coordinate value range and 8 is the number of columns (rows) of
      the grid. For example, for the bottom left point POI #41 at (9.8, 10.9):
      col num = ⌈
      9.8
      12.5
      ⌉ − 1 = 0; row num = ⌈
      10.9
      12.5
      ⌉ − 1 = 0 (3)
      Then, the curve value of the POI can be calculated by calling the cal_curve_value(col_num, row_num)
      function given as part of the skeleton code (you should not modify the given cal_curve_value function; if
      you are interested in what the function does, read Section 13.2 of the textbook on bitwise operators).
      In this stage, you will add code to the stage_three function to calculate the curve values for the POIs
      (by calling the given cal_curve_value function with proper values of col num and row num), and sort
      the POIs by their curve values in ascending order – if there is a tie in the curve values, the POI with a
      smaller ID should be listed earlier. You may create another sorting function again based on the insertion
      sort algorithm. Hint: You may need to use the array curve_values to store the curve values for the POIs.
      The output of your code should be the first five POIs after ordering by their curve values. To align the
      output, use %02d for the POI IDs and %04.1 for the coordinates. See a sample output below.
      Stage 3
      ==========
      POI #41 @ (09.8, 10.9), curve value: 0
      POI #18 @ (24.7, 04.4), curve value: 1
      POI #04 @ (15.4, 22.3), curve value: 3
      POI #35 @ (35.6, 01.2), curve value: 4
      POI #13 @ (05.8, 37.4), curve value: 8
      4
      3.4 Stage 4: Query POIs by Curve Values (Up to 20 Marks)
      This stage implements a query algorithm with the curve values, by adding code to the stage_four function.
      Our query algorithm is based on the following observation. Consider a query range (xlb, ylb, xub, yub). Let
      the curve value of the bottom left corner point (xlb, ylb) be vlb, and that of the top right corner point
      (xub, yub) be vub (these curve values can be calculated in the same way as in Stage 3 using the corner point
      coordinates). Then, for any POI within the query range, its curve value must be in the range of [vlb, vub].
      For example, given query Q0 in Figure 3, vlb = 0 and vub = 24. The curve values of the two POIs in Q0 are
      1 and 3, which are both in [0, 24].
      Based on the observation, for each query range, the query algorithm runs as follows:
      • Step 1. First, calculate and output vlb and vub (use %02d for formatting). Then, run a binary search
      over the curve_values array produced in Stage 3 to locate the curve value greater than or equal to
      vlb that is ranked the earliest in the array. Let the POI corresponding to this curve value be the curve
      value lower bound POI.
      • Step 2. Run a linear scan over the array of POI coordinates (which has been sorted by the curve values
      in Stage 3) starting from the curve value lower bound POI, until reaching a POI whose curve value
      exceeds vub. For each POI visited during the scan, we examine whether it is within the query range
      (that is, to run POI-in-query tests – this time, we need to test the coordinates in both dimensions),
      and if so, it is part of the query answer and its ID is outputted. At the end of this step, we also output
      the number of POI-in-query tests run, like we did in Stage 2.
      Note: You should adapt the binary_search function included in the skeleton code for Step 1 above, to
      output the curve_values array elements that have been compared with during the search process. For
      marking purposes, you are not allowed to use binary search code from other sources, or to create your own
      binary search functions from scratch. If you are not confident with your binary search implementation, you
      can replace it with a linear search for the same purpose. This will cost a 2-mark deduction (the full mark
      of the assignment becomes 18) but will not impact the rest of your assignment implementation.
      The output for this stage given the sample input above is shown below (note the final newline ‘\n’).
      Stage 4
      ==========
      Q0: [00, 24]; curve values compared: 33 16 11 4 1 0
      POIs in Q0: 18 4; No. POI-in-query tests: 19
      Q1: [33, 39]; curve values compared: 33 16 27 29 30
      POIs in Q1: none; No. POI-in-query tests: 6
      Q2: [35, 59]; curve values compared: 33 54 41 36 35 34
      POIs in Q2: 39 33 15 27 26; No. POI-in-query tests: 18
      Q3: [39, 50]; curve values compared: 33 54 41 36 40 36
      POIs in Q3: none; No. POI-in-query tests: 5
      Q4: [28, 31]; curve values compared: 33 16 27 29 28 28
      POIs in Q4: 11 38 43 9 40; No. POI-in-query tests: 5
      Take Q0 in Figure 3 as an example. At Step 1, we calculate vlb = 0 and vub = 24. The binary search over
      the array curve_values will examine 33, 16, 11, 4, 1, and 0 in the array – the last element examined, 0,
      is the element ranked the earliest in curve_values that is greater than or equal to vlb. This curve value
      0 is the first element in the curve_values array. Thus, we perform a linear scan over the POI ids and
      coordinates arrays starting from their first elements. A total of 19 POIs are visited in the process, until
      we reach a POI whose curve value exceeds vub = 24 (see the POIs in Figure 3 in cell 0 to cell 24).
      As you may have observed, even using the ordering based on curve values, there are POIs examined that
      are not exactly within the query ranges (these are called false positives, which need to be filtered during query processing). While the curve-based ordering helps reduce the number of POI-in-query tests in
      general, there is no guarantee that this is always the case, and there is no known solution with such a
      guarantee. The state-of-the-art solution for the problem offers O(

      n + k) query time in the worst case. Refer to https://people.eng.unimelb.edu.au/jianzhongq/papers/TODS2020_RtreeRankSpaceSFC.pdf if
      you are interested in learning more about the problem and solution.
      5
      Open challenge (no answer needed in your assignment submission, but you are welcomed
      to share your thoughts on Ed with private posts): Can you think of other strategies to make 2-
      dimensional range queries even more efficient? How about extending to d-dimensional range queries for any
      integer d > 2?
      4 Submission and Assessment
      This assignment is worth 20% of the final mark. A detailed marking scheme will be provided on LMS.
      Submitting your code. To submit your code, you will need to: (1) Log in to LMS subject site, (2) Navigate to “Assignment 1” in the “Assignments” page, (3) Click on “Load Assignment 1 in a new window”,
      and (4) follow the instructions on the Gradescope “Assignment 1” page and click on the “Submit” link to
      make a submission. You can submit as many times as you want to. Only the last submission made before the
      deadline will be marked. Submissions made after the deadline will be marked with late penalties as detailed
      at the end of this document. Do not submit after the deadline unless a late submission is intended. Two
      hidden tests will be run for marking purposes. Results of these tests will be released after the marking is done.
      You can (and should) submit both early and often – to check that your program compiles correctly on
      our test system, which may have some different characteristics to your own machines.
      Testing on your own computer. You will be given a sample test file test0.txt and the sample output
      test0-output.txt. You can test your code on your own machine with the following command and compare
      the output with test0-output.txt:
      mac: ./program < test0.txt /* Here ‘<’ feeds the data from test0.txt into program */
      Note that we are using the following command to compile your code on the submission testing system (we
      name the source code file program.c).
      gcc -Wall -std=c17 -o program program.c -lm
      The flag “-std=c17” enables the compiler to use a modern standard of the C language – C17. To ensure
      that your submission works properly on the submission system, you should use this command to compile
      your code on your local machine as well.
      You may discuss your work with others, but what gets typed into your program must be individual work,
      not from anyone else. Do not give (hard or soft) copies of your work to anyone else; do not “lend” your
      memory stick to others; and do not ask others to give you their programs “just so that I can take a look
      and get some ideas, I won’t copy, honest”. The best way to help your friends in this regard is to say a
      very firm “no” when they ask for a copy of, or to see, your program, pointing out that your “no”, and their
      acceptance of that decision, is the only thing that will preserve your friendship. A sophisticated program that
      undertakes deep structural analysis of C code identifying regions of similarity will be run over all submissions
      in “compare every pair” mode. See https://academichonesty.unimelb.edu.au for more information.
      Deadline: Programs not submitted by 4pm Tuesday 30 April 2024 will lose penalty marks at the rate
      of 3 marks per day or part day late. Late submissions after 4pm Friday 3 May 2024 will not be accepted.
      Students seeking extensions for medical or other “outside my control” reasons should email the lecturer at
      jianzhong.qi@unimelb.edu.au. If you attend a GP or other health care professional as a result of illness,
      be sure to take a Health Professional Report (HRP) form with you (get it from the Special Consideration
      section of the Student Portal), you will need this form to be filled out if your illness develops into something
      that later requires a Special Consideration application to be lodged. You should scan the HPR form and
      send it in connection with any non-Special Consideration assignment extension requests.

      請加QQ:99515681  郵箱:99515681@qq.com   WX:codinghelp










       

      掃一掃在手機打開當前頁
    1. 上一篇:CHC6186代寫、Java程序設計代做
    2. 下一篇:代寫CS 6476、代做Python/Java程序
    3. 無相關信息
      合肥生活資訊

      合肥圖文信息
      挖掘機濾芯提升發動機性能
      挖掘機濾芯提升發動機性能
      戴納斯帝壁掛爐全國售后服務電話24小時官網400(全國服務熱線)
      戴納斯帝壁掛爐全國售后服務電話24小時官網
      菲斯曼壁掛爐全國統一400售后維修服務電話24小時服務熱線
      菲斯曼壁掛爐全國統一400售后維修服務電話2
      美的熱水器售后服務技術咨詢電話全國24小時客服熱線
      美的熱水器售后服務技術咨詢電話全國24小時
      海信羅馬假日洗衣機亮相AWE  復古美學與現代科技完美結合
      海信羅馬假日洗衣機亮相AWE 復古美學與現代
      合肥機場巴士4號線
      合肥機場巴士4號線
      合肥機場巴士3號線
      合肥機場巴士3號線
      合肥機場巴士2號線
      合肥機場巴士2號線
    4. 幣安app官網下載 短信驗證碼 丁香花影院

      關于我們 | 打賞支持 | 廣告服務 | 聯系我們 | 網站地圖 | 免責聲明 | 幫助中心 | 友情鏈接 |

      Copyright © 2024 hfw.cc Inc. All Rights Reserved. 合肥網 版權所有
      ICP備06013414號-3 公安備 42010502001045

      成人久久18免费网站入口