assignment作业 | 数据结构 – COIS 3020H: Data Structures and Algorithms II

2024-08-09

COIS 3020H: Data Structures and Algorithms II

assignment作业 – 该题目是值得借鉴的数据结构代写的题目

ass代做 assignment代写 代写assignment


COIS 3020H: Data Structures and Algorithms II

assignment 2: Augs and Autos

(100 marks)

(due Monday, March 13, 2023 at 23:59 EST)
Notes
  1. Late assignments will be deducted 10% per day up to five days (including weekends).
  2. Form teams of 2 or 3 to complete the assignment. Solo assignments will not be accepted.
  3. Teams can be different from Assignment 1. Use the Discussion Board on Blackboard to help connect with classmates.

Part A: Trie, Trie Again (50 marks)

Suppose that the three methods below are added to both the r-way and ternary tree implementations of the Trie classes on Blackboard.

ListPartialMatch(string pattern): Return all keys that match the given pattern. A pattern is defined as a string with letters and stars where each star represents a wildcard character. Therefore, the pattern ad would return all four-letter keys whose second and fourth characters are a and d, such as card and band (6 marks each).

ListAutocomplete(string prefix):Return the list of keys that begin with the given prefix (3 marks each).

ListAutocorrect(string key):Return the list of keys that differ from the given key by one letter. Try to be as efficient as possible. (8 marks each)

Requirements:

  1. Populate each Trie with the 1000 most common keys (words) in the English language. (7 marks)
(a) Using the link below, cut and paste the 1000 keys into a file.

https://www.ef.com/ca/english-resources/english-vocabulary/top-1000-words/

(b) Input each key from the file, convert it to lower case, and insert it into each Trie. Assume the
value associated with a key is a random integer.
  1. Implement the three methods above for each implementation of the Trie class.
  2. Thoroughly test the three methods. (9 marks)

Part B: Augmented Skip List (30 marks)

Suppose that the twoRankmethods below are added to the Skip List class on Blackboard.

int Rank(T item):Return the rank of the given item.

T Rank(int i):Return the item with the given rank i.

Requirements:

  1. Describe in a separate document what additional data is needed and how that data is used to support an expected time complexity ofO(logn) for each of theRankmethods. Show as well that the methodsAddandRemovecan efficiently maintain this data as items are added and removed. (8 marks)
  2. Re-implement the methodsAdd andRemoveof the Skip List class to maintain the augmented data. Using theContainsmethod, ensure that added items are distinct. (6 marks)
  3. Implement and test the two newRankmethods. (16 marks)

Part C: Minimum Gap (20 marks)

Suppose that theMinGapmethod below is added to the Treap class on Blackboard.

int MinGap( ):Return the absolute difference between the two closest numbers in the treap. For exam- ple, if the numbers are{ 2 , 5 , 7 , 11 , 12 , 15 , 20 }thenMinGapwould return 1, the absolute difference between 11 and 12.

Requirements:

  1. Describe in a separate document what additional data is needed and how that data is used to support an expected time complexity ofO(1) for theMinGapmethod. Show as well that the methodsAdd andRemovecan efficiently maintain this data as items are added and removed. (6 marks)
  2. Re-implement the methodsAddandRemoveof the Treap class to maintain the augmented data in expectedO(logn) time. (6 marks)
  3. Implement and test theMinGapmethod. (4+4 marks)