HW5 Solution


Category: Tag:


To help track down a hacker who has compromised multiple user accounts, we would like to display (potentially suspicious) activities during a certain period of time. How would you design an e cient tool for the task?

The goal of HW5 is to manage the activities and allow the user to specify a time range to display the corresponding activities. Also, we would like the user to be able to add and remove activities (e.g. from di erent sources such as log les from applications, the network, the operating system). To improve e ciency, your implementation uses a Skip List that includes the following operations:

get(key) // if key exists, return value associated with key; otherwise, return NULL

put(key, value) // if key doesn’t exist, add entry and return NULL; otherwise, replace value and return the old value remove(key) // if key exists, remove entry and return its value; otherwise, return NULL

ceilingEntry(key) // return the entry with the smallest key greater than or equal to key; return null if no such entry exists

oorEntry(key) // return the entry with the largest key less than or equal to key; return null if no such entry exists subMap(key1, key2) // return all entries with key such that key1 key key2

Use getRandHeight() in fakeRandHeight.c (FakeRandomHeight in java) for put(key, value) (to facilitate eaiser debugging and testing) [gcc -o hw5 hw5.c fakeRandHeight.c]. You may rewrite/modify doublyLinkedList.c/h (DoublyLinkedList.java). Program les are on the course website. We will be evaluating your submission on code01. t.edu; we strongly recommend you to ensure that your submission runs on code01. t.edu.

Input: Input is from the command-line arguments for hw5.c (HW5.java):

lename of actions, each line has one of the following actions: { DisplayActivity time

{ AddActivity time activity { DeleteActivity time

{ DisplayActivitiesBetweenTimes startT ime endT ime { DisplayActivitiesFromStartTime startT ime

{ DisplayActivitiesToEndTime endT ime { DisplayAllActivities

{ PrintSkipList

For simplicity, times are in HHMMSS format (HH is 00-23, MM and SS are 00-59) [leading zeros are optional]. You may assume the times are unique. Sample input is on the course website.

Output: Output goes to the standard output (screen), each line has a result for the corresponding action:

DisplayActivity time activity=none

AddActivity time activity [existingT imeError] DeleteActivity time activity=noT imeError

DisplayActivitiesBetweenTimes startT ime endT ime time1:activity1 … or none

DisplayActivitiesFromStartTime startT ime time1:activity1 … or none

DisplayActivitiesToEndTime endT ime time1:activity1 … or none

DisplayAllActivities time1:activity1 … or none PrintSkipList

(Sh) empty

(S1) time1:activity1 …

(S0) time1:activity1 …

Sample output is on the course website.

Submission: Submit hw5.c (HW5.java) that has the main method and other program les. Submissions for Individual and GroupHelp have the same guidelines as HW1.

Note the late penalty on the syllabus if you submit after the due date and time as speci ed at the top of the assignment.