COMP3506/7505 Homework Task 4

　　10 marks total

　　Overview

　　The goal of this problem set is to understand how to apply the algorithms and data structures

　　that have been taught in this course.

　　You will be required to write a series of algorithms to search through and analyse the data of a

　　social media feed. The following searches will need to be implemented:

　　? A search to find all posts made by a user between two dates

　　? A search to find the first post made by a specific user after a specific date

　　? A search to find the post with the nth highest upvotes

　　? A search to find all posts containing a specific text pattern

　　The intention is for most of the preprocessing to be performed in the constructor of the class,

　　allowing calls to these searches to be as fast as possible. Most of these searches are trivial to

　　implement using a brute-force algorithm. The majority of this task’s marks will be awarded for

　　choosing (and justifying the use of) efficient algorithms and data structures. Simply implementing

　　a brute force solution will result in very few marks, so you are encouraged to think about how to

　　maximise the efficiency of your solution before you begin writing code.

　　You have been supplied with a Java file, FeedAnalyser.java, which is responsible for loading the

　　data file and performing the searches. Stubs and Javadoc comments for each of the search methods

　　have been provided. Your implementation should strictly adhere to the documentation.

　　Other files you have been provided with include:

　　? FeedItem.java - a data class for storing information about feed items

　　? Util.java - containing utility methods for performing various functions, in particular for

　　file parsing (the methods in this class have already been used in the base code - you are not

　　required to use them in your solution)

　　You are permitted to use any programming constructs from the Java Collections Framework (or

　　any other standard Java library) for this task. You should however understand the underlying

　　implementation of any data structures/algorithms you use from the JCF.

　　1

　　Input File

　　The social media data that you are analysing will be initially stored in a csv file. The constructor

　　of FeedAnalyser.java is already partially-implemented to load this data from the file. You are

　　required to modify the constructor so this data is loaded into appropriate data structures.

　　Each line in the file represents a single post in the feed, and is formatted as follows:

　　id,username,date,upvotes,content

　　In this format:

　　? id is a unique integer identifier

　　? username is a string representing the user who posted this data

　　? date is the time the item was posted at (formatted in 24-hour time as dd/mm/yyyy hh:mm:ss)

　　? upvotes is the number of upvotes this post received (downvotes are possible and are represented

　　as negative integers)

　　? content is a (possibly very long) string containing the content of the post

　　For simplicity, you may assume the username and content fields contain only printable ASCII

　　characters (i.e. characters with ASCII values from 32 to 126 inclusive) and do not contain the

　　comma character. You can also assume that the data file is always formatted correctly so there is

　　no need to implement format validation.

　　Your Task

　　1. (4 marks) Implement the four searches as per their Javadoc specifications. You will likely need

　　to modify the constructor and class’ member variables to achieve an efficient implementation.

　　2. (6 marks) Describe any design choices that were made while implementing these searches.

　　In particular you should:

　　? Identify the underlying theoretical algorithms and data structures used by your code

　　and any of the classes from the JCF you have used

　　? State and briefly explain the worst-case time complexity of the constructor and each of

　　your searches in big-O notation

　　? If the worst-case time complexity differs from the expected-case time complexity, also

　　provide the expected-case complexity in big-O notation and explain why these cases

　　differ

　　? Justify why the chosen algorithms and data structures were optimal for efficiently implementing

　　each of the searches (you should discuss both the runtime and memory usage

　　of your implementation) - keep in mind that there may be no “perfect” solution and

　　certain implementations may have certain tradeoffs (which you should identify)

　　? Compare and contrast your design against other potential implementations (including,

　　but not limited to, brute force implementations or implementations with other tradeoffs)

　　2

　　Constraints

　　? You must write your solution in FeedAnalyser.java - do not modify any other files or

　　introduce new packages

　　? You may only use standard Java libraries

　　? You may introduce new member variables or helper methods but these should have the

　　strictest access modifiers possible

　　? Your answer to question 2 should be no longer than 4 pages (at size 12 font and standard

　　line spacing/margins)

　　Submission and Marking

　　Submit two files as a part of your submission. Your solution to question 1 should be in the file

　　FeedAnalyser.java. Your answer to question 2 should be in a PDF file named README.pdf. Do

　　not submit any other files or directories. To preserve anonymity, please do not include your name

　　in any submitted files (it is okay to include your student number).

　　Question 1 will be partially marked by an automated test suite with timeouts present on each of

　　the tests. A sample test suite has been provided in FeedAnalyserTest.java. This test suite is not

　　comprehensive - there is no guarantee that passing these will ensure passing the tests used during

　　marking. It is recommended, but not required, that you write your own tests for your algorithms.

　　Passing the tests also does not guarantee an efficient solution - tutors will make mark deductions

　　if your solution is inefficient. Marks may also be deducted for poor coding style.

　　You should submit README.pdf using Turnitin - this will be manually marked by a tutor. This file

　　should be electronically processed - handwritten solutions will not be accepted. Any asymptotic

　　bounds should be as tight as possible. Your analysis should be as concise as possible, while still

　　achieving the level of required detail (marks may be deducted for overly long answers). You are

　　encouraged to support your analysis, justification, and/or comparison with information from other

　　sources, but you must cite these appropriately (IEEE style is recommended). Using LATEX to

　　write your README is once again recommended but not required.

　　Late Submissions and Extensions

　　Late submissions will not be accepted. It is your responsibility to ensure you have submitted your

　　work well in advance of the deadline (taking into account the possibility of computer or internet

　　issues). See the ECP for information about extensions.

　　Academic Misconduct

　　Students are reminded of the University’s policy on student misconduct, including plagiarism. See

　　the course profile and the School web page for more information:

　　http://www.itee.uq.edu.au/itee-student-misconduct-including-plagiarism.

　　翻譯：

　　COMP3506 / 7505家庭作業(yè)任務(wù)4

　　總分10分

　　概述

　　此問題集的目的是了解如何應(yīng)用

　　本課程中所教授的算法和數(shù)據(jù)結(jié)構(gòu)。

　　您將需要編寫一系列算法來搜索和分析

　　社交媒體供稿的數(shù)據(jù)。需要執(zhí)行以下搜索：

　　?搜索以查找用戶在兩個日期之間發(fā)布的所有帖子

　　?搜索以查找特定用戶在特定日期之后發(fā)布的第一篇帖子

　　?搜索以查找第n個帖子最高投票

　　?搜索以查找所有包含特定文本模式

　　的帖子目的是要在類的構(gòu)造函數(shù)中執(zhí)行大多數(shù)預(yù)處理，

　　允許盡可能快地調(diào)用這些搜索。這些搜索大多數(shù)都不容易

　　使用暴力算法來實現(xiàn)。該任務(wù)的大部分標記將因

　　選擇(并證明使用)有效的算法和數(shù)據(jù)結(jié)構(gòu)而被授予。簡單地實施

　　蠻力解決方案不會產(chǎn)生太多的痕跡，因此鼓勵

　　您在開始編寫代碼之前考慮如何最大程度地提高解決方案的效率。

　　您已經(jīng)獲得了Java文件FeedAnalyser.java，該文件負責(zé)加載

　　數(shù)據(jù)文件并執(zhí)行搜索。提供了每種搜索方法的存根和Javadoc注釋

　　。您的實現(xiàn)應(yīng)嚴格遵守文檔。

　　您提供的其他文件包括：

　　?FeedItem.java-用于存儲有關(guān)提要項目信息的數(shù)據(jù)類

　　?Util.java-包含用于執(zhí)行各種功能(尤其是

　　文件解析)的實用程序方法(此類中的方法已經(jīng)在基本代碼中使用-

　　不需要在解決方案中使用它們)

　　被允許使用Java Collections Framework(或

　　任何其他標準Java庫)中的任何編程構(gòu)造來完成此任務(wù)。但是，您應(yīng)該了解

　　從JCF使用的任何數(shù)據(jù)結(jié)構(gòu)/算法的基礎(chǔ)實現(xiàn)。

　　1、輸入文件

　　您正在分析的社交媒體數(shù)據(jù)將最初存儲在csv文件中。構(gòu)造函數(shù)

　　FeedAnalyser.java的一部分已經(jīng)實現(xiàn)，可以從文件中加載此數(shù)據(jù)。您

　　需要修改構(gòu)造函數(shù)，以便將此數(shù)據(jù)加載到適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)中。

　　文件中的每一行都代表Feed中的單個帖子，其格式如下：

　　id，username，date，upvotes，content采用

　　這種格式：

　　?id是唯一的整數(shù)標識符

　　?用戶名是代表發(fā)布此內(nèi)容的用戶的字符串?dāng)?shù)據(jù)

　　?日期是發(fā)布該項目的時間(格式為24小時制，格式為dd / mm / yyyy hh：mm：ss)

　　?upvotes是此帖子收到的支持的投票數(shù)(可以支持downvotes，并

　　用負整數(shù)表示))

　　?content是一個(可能很長的)字符串，其中包含帖子的內(nèi)容

　　為簡單起見，您可以假設(shè)用戶名和內(nèi)容字段僅包含可打印的ASCII

　　字符(即ASCII值介于32至126之間的

　　字符)，而不包含逗號。您還可以假定數(shù)據(jù)文件始終正確格式化，因此

　　無需實施格式驗證。

　　您的任務(wù)

　　1.(4個標記)根據(jù)其Javadoc規(guī)范實施四個搜索。您可能需要

　　修改構(gòu)造函數(shù)和類的成員變量以實現(xiàn)有效的實現(xiàn)。

　　2.(6分)描述實現(xiàn)這些搜索時所做的任何設(shè)計選擇。

　　特別是，您應(yīng)該：

　　?確定代碼使用的基礎(chǔ)理論算法和數(shù)據(jù)結(jié)構(gòu)

　　以及您使用過的JCF中的任何類

　　用最大O表示法陳述并簡要說明構(gòu)造函數(shù)的最壞情況時間復(fù)雜度和每個搜索

　　?如果最壞情況時間復(fù)雜度與預(yù)期時間不同復(fù)雜性，還

　　以大O表示法提供了預(yù)期的案例復(fù)雜性，并解釋了為什么這些案例

　　有所不同

　　?證明為什么所選算法和數(shù)據(jù)結(jié)構(gòu)最適合有效執(zhí)行

　　每個搜索(您應(yīng)該討論自己的運行時和內(nèi)存使用情況

　　)實現(xiàn))-請記住，可能沒有“完美”的解決方案，并且

　　某些實現(xiàn)可能會有一定的權(quán)衡(您應(yīng)該確定)

　　?將您的設(shè)計與其他可能的實現(xiàn)(包括

　　但不限于蠻力實現(xiàn)或具有其他折衷的實現(xiàn))進行比較和對比

　　2、約束

　　?您必須在FeedAnalyser.java中編寫解決方案-請勿修改任何其他文件或

　　引入新的包

　　?您只能使用標準Java庫

　　?您可以引入新的成員變量或輔助方法，但這些變量應(yīng)具有

　　最嚴格的訪問修飾符

　　?您對問題2的回答不得超過4頁(以12號字體和標準

　　行間距/頁邊距)

　　提交和標記

　　提交兩個文件作為提交的一部分。您對問題1的解決方案應(yīng)在文件中

　　FeedAnalyser.java。您對問題2的答案應(yīng)該在名為README.pdf的PDF文件中。不要

　　提交任何其他文件或目錄。為了保持匿名，請不要

　　在任何已提交的文件中包含您的名字(可以包含您的學(xué)生編號)。

　　自動化測試套件將部分標記問題1，并且每個

　　測試都存在超時。FeedAnalyserTest.java中提供了一個示例測試套件。該測試套件并不

　　全面-無法保證通過這些測試將確保通過

　　標記過程中使用的測試。建議(但不是必需)為算法編寫自己的測試。

　　通過測試也不能保證有效的解決方案-導(dǎo)師將扣除分數(shù)

　　如果您的解決方案效率低下。如果編碼風(fēng)格較差，也可以扣除標記。

　　您應(yīng)該使用Turnitin提交README.pdf，這將由導(dǎo)師手動標記。該文件

　　應(yīng)進行電子處理-手寫解決方案將不被接受。任何漸近

　　邊界都應(yīng)盡可能緊密。您的分析應(yīng)盡可能簡明扼要，同時仍能

　　達到要求的詳細程度(可能因過長的答案而扣分)。我們

　　鼓勵您支持分析，論證和/或與其他

　　來源的信息進行比較，但是您必須適當(dāng)?shù)匾盟鼈?建議使用IEEE樣式)。

　　再次建議使用LATEX 編寫自述文件，但這不是必需的。

　　逾期提交和擴展

　　將不接受逾期提交。您有責(zé)任確保

　　在截止日期之前很好地提交了工作(考慮到計算機或互聯(lián)網(wǎng)

　　問題的可能性)。有關(guān)擴展的信息，請參閱ECP。

　　學(xué)術(shù)不端行為

　　提醒學(xué)生注意大學(xué)關(guān)于學(xué)生不端行為(包括竊)的政策。有關(guān)

　　更多信息，請參見課程資料和學(xué)校網(wǎng)頁：

　　http : //www.itee.uq.edu.au/itee-student-misconduct-includes-plagiarism。

? ? ?昆士蘭大學(xué)COMP3506/COMP7505課程作業(yè)輔導(dǎo)選擇考而思在線一對一輔導(dǎo)