CISC-235 Data Structures W23 Assignment 3

AI悦创原创1v1Python 1v1python数据结构与算法一对一辅导1v1Python 1v1python数据结构与算法一对一辅导大约 7 分钟...约 2245 字

March 25, 2023

General Instructions


Write your own program(s) using Python. Once you complete your assignment, place all Python files in a zip file and name it according to the same method, i.e., “235-1234-Assn3.zip”. Unzip this file should get all your Python file(s).


Then upload 235-1234-Assn3.zip into Assignment 3’s entry on onQ. You may upload several times if you wish. However, onQ keeps only the last uploaded file. The newly uploaded file will overwrite the old file. Please check your files after uploading. We will check the latest submission you made following the required naming.


You must ensure your code is executable and document your code to help TA mark your solution. We suggest you follow PEP81 style to improve the readability of your code.


All data structures involved must be implemented by yourself, except for the built-in data types, i.e., List in Python.


An “I uploaded the wrong file” excuse will result in a mark of zero.


1. Word-Frequency Hash Table (40 points)


In Assignment 2, we created a modified version of AVL tree for saving word frequency (word is the key, frequency is the value associated with key) infor- mation in a given document. In this assignment, we will redesign the solution leveraging two types of hash table, i.e., closed hash table (with linear probing) and open hash table (with lists). You can not use any built-in hash-based data structure offered by Python. You should consider the “deletion” flag for the closed hash table.


Specifically, Your tasks are:


  1. Implement two classes named ClosedHashTable and OpenHashTable. Both classes should have a load from file(self, file path) function. This function aims to read content from a file and save word-frequency infor- mation for all words appearing in the file in the hash table. Note that you cannot calculate the word frequency outside your hash table. In other words, when you scan the word sequence, you should insert the key to the hash table and update its frequency when you see another occurrence of the word. You can reuse your A2’s code to parse a document and generate word/token sequences.

实现两个类ClosedHashTable和opendhashtable。这两个类都应该有一个load from file(self, file path)函数。此函数旨在从文件中读取内容,并将文件中出现的所有单词的词频信息保存在哈希表中。注意,您不能在哈希表之外计算词频。换句话说,在扫描单词序列时,应该将键插入到哈希表中,并在看到单词再次出现时更新其频率。您可以重用A2的代码来解析文档并生成单词/令牌序列。

Test the performance of your ClosedHashTable and OpenHashTable by searching a list S containing K words, where half of the K words are in the hash table. You need first to call your load from file(self, file path) function to initialize your hash table using a given sample test file (named A3test.txt). Varying K by setting it to be 10, 20, 30, 40, 50. Print out the number of steps required for each search. For instance, K=10, means you should create a word list containing 10 words, 5 of them exist in the A3test.txt, and 5 of them do not exist. Then you perform 10 searches on the hash table for the 10 target words. Your search function should return a value indicating whether the search target exists in the hash table and, if it exists, how many steps have been taken to find the key. Hint: you can return -1, indicating the key does not exist in the hash table.

通过搜索包含K个单词的列表S来测试ClosedHashTable和OpenHashTable的性能,其中K个单词中有一半在哈希表中。首先需要调用load from file(self, file path)函数,使用给定的示例测试文件(名为A3test.txt)初始化哈希表。通过设置K为10,20,30,40,50来改变K。打印出每次搜索所需的步骤数。例如,K=10,意味着您应该创建一个包含10个单词的单词列表,其中5个单词存在于A3test.txt中,另外5个单词不存在。然后在哈希表上为这10个目标单词执行10次搜索。搜索函数应该返回一个值,该值指示搜索目标是否存在于哈希表中,如果存在,则表示已经执行了多少步来查找该键。提示:您可以返回-1,表示该键在哈希表中不存在。

To implement the above two functionalities, you need to implement at least an insert and search function for your hash table. You also need to design your hash function and determine the size of your hash table following the tips introduced in class. You are encouraged to explain your design in comments so TAs can quickly get your idea. If you decide to follow an existing hash function, explain that in comments as well.


2. Graph (60 points)

2.1 Random Graph Generation: 10 points


Create a Graph class (and a vertex class if needed). Your graph class should have an initialization function to create a random connected graph with a specified number of vertices, and random weights on all the edges, such that the edge- weights all come from a specified range of integers.


The construction of random graphs is a huge topic and many approaches have been developed. For the purposes of this assignment, I suggest the following very simple method:


Let the set of vertices be {1, 2, ..., n}


for i=2..n:

x = randint(1, i−1) # x is a random integer in the range [1 .. i−1]

let S be a randomly selected sample of x values from the set {1, ..., i−1}

for each s in S:

w = random(10,100)

add an edge between vertex i and vertex s, with weight w

2.2 Compare BFS with Prim’s algorithm: 50 points

Implement two functions within the graph class you created in 2.1. One for Breadth-First Search(BFS) (10 points) and the other for Prim’s Minimum Span- ning Tree algorithm (20 points).

Compare the efficiency of them by performing the below experiments (20 points):

    repeat k times: #k is an input parameter
        generate a random graph with n vertices
        use BFS to find a spanning tree ( let its total weight be B)
        use Prim to find a spanning tree ( let its total weight be P) compute Diff #Diff is the percentage by which B is larger than P
    compute the average of the values of Diff for this value of n

Report the average value of Diff for each value of n.

For example, if B=20, P=10, Diff = (20 − 10)/10 = 100%




AI悦创·推出辅导班啦,包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发、Web、Linux」,全部都是一对一教学:一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然,还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线,随时响应!微信:Jiabcdefh

C++ 信息奥赛题解,长期更新!长期招收一对一中小学信息奥赛集训,莆田、厦门地区有机会线下上门,其他地区线上。微信:Jiabcdefh

方法一:QQopen in new window


贡献者: AndersonHJB
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
  • 按正序
  • 按倒序
  • 按热度