ARIZONA STATE UNIVERSITY
CSE 310, SLN 91032 — Data Structures and Algorithms — Fall 2021
Instructor: Dr. . Syrotiuk
Project #2
Milestone due Sunday, 10/17/2021; complete project due Sunday, 10/31/2021
Storm data, provided by the National Weather Service (NWS), contain a chronological listing, by state, of
hurricanes, tornadoes, thunderstorms, hail, floods, drought conditions, lightning, and other weather phe-
nomena. The data also contain statistics on personal injuries and damage estimates. Data is available from
1950 to the present for the United States of America.
This project goal of this project is to implement an application that manages storm event data and uses
it to answer queries meeting given selection criteria. The storm event data will be indexed by a hash table,
a binary search tree (BST), and max-heap as appropriate to support the queries.
Note: This project must be completed individually. Your implementation must use C/C++ and ulti-
mately your code must run on Gradescope which will (eventually) be configured to match the Linux machine
general.asu.edu available to everyone in this course.
Your application is required to implement the BST, hash table, and max-heap and the needed operations
on them yourself. You must do all dynamic memory allocation yourself, using either malloc() and free(),
or new() and delete(). You may not use any external libraries to implement any part of this project, aside
from the standard libraries for I/O, file I/O, string functions, and dynamic memory allocation. If you are in
doubt about what you may use, ask me.
By convention, your program should exit with a return value of zero to signal that all is well; non-zero
values are used to signal abnormal situations.
You must use a version control system as you develop your solution to this project, e.g., GitHub or
similar. Your code repository must be private to prevent anyone from plagiarizing your work.
The rest of this project description is organized as follows. §1 describes the storm and fatality event data
format, and the queries that your storm event application must support. §2 summarizes the requirements for
the storm event application for this project. §3 describes measures to help evaluate the effectiveness of the
data structures used in this application. Finally, §4 describes the submission requirements for the milestone
and the full project deadlines.
1 Storm Event Application: Data and Query Format
Your application, named storm, reads two command line arguments: The first is a four digit start year YYYY,
1950 ≤ YYYY ≤ 2021; the second is n, the number of years of storm data to manage from the start year. For
each year YYYY, there are two input data files: The first is named details-YYYY.csv, a comma separated
value (CSV) file containing the storm event data. The second is named fatalities-YYYY.csv, also a CSV
file, containing the storm fatality data. The format of these data files is described next.
1.1 The Storm and Fatality Event Data Format
Each line of a file details-YYYY.csv contains details of a storm event described by the following 13 fields,
in order. The only exception is the first line which contains the field names, and should be skipped.
1. event id: An identifier assigned by the NWS for a specific storm event; it links the storm event with
the information in the fatalities-YYYY.csv file. Example: 383097.
2. state: The state name, spelled in all capital letters, where the event occurred. Example: GEORGIA.
3. year: The four digit year for the event in this record. Example: 2000.
1
Table 1: Valid Event Types
Event Name Designator Event Name Designator
Astronomical Low Tide Z Hurricane (Typhoon) Z
Avalanche Z Ice Storm Z
Lake-Effect Snow Z
Coastal Flood Z Lakeshore Flood Z
Cold/Wind Chill Z Lightning C
Debris Flow C Marine Hail M
Dense Fog Z Marine High Wind M
Dense Smoke Z Marine Strong Wind M
Drought Z Marine Thunderstorm Wind M
Dust Devil C Rip Current Z
Dust Storm Z Seiche Z
Excessive Heat Z Sleet Z
Extreme Cold/Wind Chill Z Storm Surge/Tide Z
Flash Flood C Strong Wind Z
Flood C Thunderstorm Wind C
Frost/Freeze Z Tornado C
Funnel Cloud C Tropical Depression Z
Freezing Fog Z Tropical Storm Z
Hail C Tsunami Z
Heat Z Volcanic Ash Z
Heavy Rain C Waterspout M
Heavy Snow Z Wildfire Z
High Surf Z Winter Storm Z
High Wind Z Winter Weather Z
4. month name: Name of the month for the event in this record spelled out. Example: January.
5. event type: The event types permitted are listed in Table 1, spelled out.
6. cz type: Indicates whether the event happened in a county/parish (C), zone (Z), or marine (M).
7. cz name: County/Parish, Zone or Marine name assigned to the county or zone. Example: AIKEN.
8. injuries direct: The number of injuries directly related to the weather event. Examples: 0, 56.
9. injuries indirect: The number of injuries indirectly related to the weather event. Examples: 0, 87.
10. deaths direct: The number of deaths directly related to the weather event. Examples: 0, 23.
11. deaths indirect: The number of deaths indirectly related to the weather event. Examples: 0, 4, 6.
12. damage property: The estimated amount of damage to property incurred by the weather event, e.g.,
10.00K = $10,000; 10.00M = $10,000,000. Examples: 10.00K, 0.00K, 10.00M.
13. damage crops: The estimated amount of damage to crops incurred by the weather event e.g., 10.00K
= $10,000; 10.00M = $10,000,000. Examples: 0.00K, 500.00K, 15.00M.
Each line of a fatalities-YYYY.csv file contains information on fatalities associated with a storm event,
described by the following 7 fields, in order. Similar to a details-YYYY.csv file, the first line does not
contain data and should be skipped.
1. fatality id: An identifier assigned by NWS to denote the individual fatality that occurred within a
storm event. Example: 17582.
2. event id: An identifier assigned by NWS to denote a specific storm event; it links the fatality with
the storm event in the details-YYYY.csv file. Example: 383097.
3. fatality type: D represents a direct fatality, whereas I represents an indirect fatality. Example: D.
4. fatality date: Date and time of fatality in MM/DD/YYYY HH:MM:SS format, 24 hour time.
Example: 04/03/2012 12:00:00.
2
Table 2: Direct Fatality Location Table
Abbreviation Location
BF Ball Field
BO Boating
BU Business
CA Camping
CH Church
EQ Heavy Equip/Construction
GF Golfing
IW In Water
LS Long Span Roof
MH Mobile/Trailer Home
OT Other/Unknown
OU Outside/Open Areas
PH Permanent Home
PS Permanent Structure
SC School
TE Telephone
UT Under Tree
VE Vehicle and/or Towed Trailer
5. fatality age: The age of the person suffering the fatality. Example: 38.
6. fatality sex: The gender of the person suffering the fatality. Example: F.
7. fatality location: The fatality locations permitted are listed in Table 2, spelled out. Example: UT
is Under Tree.
1.2 Storm Data Query Format
In the following, <> bracket parameters to the query, while the other strings are literals. By the full project
deadline, there are 4 queries that your storm application must be able to support.
1. find event
If found, it follows the index into the array of storm events for the storm event for the given year to
print the information associated with the event (i.e., the fields of the struct storm event in order,
with each field labelled on a separate line); otherwise it prints “Storm event
If there are no fatalities associated with the event, print “No fatalities” Otherwise, it should print
the fields of each fatality event associated with this event id, with each field on a separate line.
Example: find event 383097 // find storm event with the given event id
2. find max
all, damage type is either damage property or damage crops, and n is an integer ≤ 50.
This query builds a max-heap on the field damage type for either the specific year YYYY, or all years of
storm data specified by the command line parameters. It executes n Delete-Max operations on the
heap, each time printing information for the most expensive storm in terms of the damage it caused to
property or crops. Specifically, for each event print the event id, event type, and amount of damage
of as a dollar amount, on a single line.
Example: find max 1950 damage property 4 // find 4 most expensive storms to property in 1950
find max all damage crops 10 // find 10 most expensive storms to crops in all years
3
3. find max fatality
n is an integer ≤ 50.
This query builds a max-heap on the number of fatalities for either the specific year YYYY or all years
of storm data specified by the command line parameters. It executes n Delete-Max operations on
the heap, each time printing information for the most fatal storm. Specifically, for each fatality print
all fields of the fatality event.
Example: find max fatality 1950 3 // find 3 most fatal storms in 1950
find max fatality all 10 // find 10 most fatal storms in all years
4. range
literal all, field name is either state or month name, and low and high are quoted strings.
To answer this query, construct a binary search tree (BST) for the given year(s) on primary key
field name and secondary key event id, i.e., the tree is ordered first by field name, and for equal
field name then ordered by event id. Then, perform an in-order traversal of the search tree printing
event information for events whose field name is greater than or equal to low and less than or equal
to high. If no applications are found whose field name is in the given range print “No storm events
found for the given range” Otherwise, your application should print for each event within the
range of the search parameters, first ordered by field name, and then ordered by event id, the follow-
ing specific fields: For field name of state, print the state, event id, year, event type, cz type,
and cz name. For field name of month name, print the month name, event id, year, event type,
cz type, and cz name.
Example: range 1950 state “A” “C” // all storms in states alphabetically from A to C in 1950
range all month name “January” “January” // all storms in January in all years
2 Program Requirements for Project #2
1. Write a storm event application, named storm, in C/C++ that reads command line argument consist-
ing of a four digit start year YYYY, 1950 ≤ YYYY ≤ 2021, followed by n, indicating the number of years
of storm data to manage starting with year YYYY. That is, the application is invoked as: storm YYYY
n For example,
storm 1950 1
storm 1950 3
In the first example, the application processes only one year of data from 1950. In the second, the
application processes three years of data, namely from 1950–1952.
2. Provided for you is a file named defns.h in which structures have been defined for storing the storm
and fatality event data with fields matching this format. For each year i, 1 ≤ i ≤ n of storm data,
initialize an array of struct annual storms. This involves:
(a) First initializing an array of struct storm event of size si where si is the number of events in
the file details-YYYYi.csv.
(b) As you initialize each entry in the storm event array, you must also insert a subset of the fields
of the event into a hash table implemented using separate chaining. The hash table is an array
of pointers to struct hash table entry all initialized to Nil. Each hash table entry has three
fields: The event id and year of the storm event, and the index position event index at which
the event is stored in the storm event array.
The hash function is computed as the event id modulo the hash table size. The hash table size
is the first prime number larger than 3× (s1 + · · ·+ sn), where si is the number of storm events in
details-YYYYi.csv, 1 ≤ i ≤ n. (You may find the function in prime.cc useful for this purpose.)
4
(c) Now, process the fatalities-YYYYi.csv file. Hash on the event id of each fatality event to find
the event index in the storm event array. Insert the fatality into a linked list of fatality events
for the corresponding storm event.
3. Once the array(s) and hash table have been initialized, your storm event application is ready to start
processing queries. It reads q, the number of queries, from stdin, followed by q queries, one per line.
Echo the query to stdout, and then process the query. The format of each query as well as the required
output is described in §1.2. The output of each query must also be written to stdout.
Example:
3 // q=3 queries
range 1951 month name “February” “March” // all storms ≥ February and ≤ March in 1951
find event 383097 // find storm event with given event id
find max fatality 1950 10 // find 10 most fatal storms in 1950
4. After processing a query, collect and output the characteristics of the data structures you’ve built as
described in §3.
5. After a query is processed, any max-heap or binary search tree data structures created dynamically
must be deallocated on answering the query.
Sample input files that adhere to the format described in §1.1 ansd §1.2 will be provided on Canvas; use
them to test the correctness of your program in Gradescope.
3 Characteristics of the Data Structures
For a BST constructed to answer a query of the form range
1. Print a count of the total number of nodes in the BST.
2. Print the height of the root of the BST, and the height of its left and its right subtree.
For a max-heap constructed to answer a query of the form find max
form find max fatality
1. Print a count of the total number of nodes in the max-heap.
2. Print the total height of the max-heap, and the height of its left and right subtrees.
After processing all queries, print a summary of the hash table that includes:
1. A table that lists for each chain length `, 0 ≤ ` ≤ `max, the number of chains of length `, up to the
maximum chain length `max that your hash table contains.
2. Compute and print the load factor for the hash table.
4 Submission Instructions
Submissions are always due before 11:59pm on the deadline date. Do not expect the clock on your machine
to be synchronized with the one on Canvas or on Gradescope!
1. The milestone is due on Sunday, 10/17/2021. See §4.1 for requirements.
2. The complete project is due on Sunday, 10/31/2021. See §4.2 for requirements.
It is your responsibility to submit your project well before the time deadline!!! Late projects
are not accepted.
An unlimited number of submissions are allowed. The last submission will be graded.
5
4.1 Requirements for Milestone Deadline
For the milestone deadline, the only query you need to support is the range, i.e., the hash table and heap
need not be constructed yet. Constructing a BST to answer each range query as described in §1.2. In
addition, print the characteristics of the BST as described in §3.
Submission instructions for the milestone as well as a grading rubric will be posted on Canvas. Sample
input will be provided on Canvas.
The milestone is worth 30% of the total project grade.
4.2 Requirements for Complete Project Deadline
For the full project deadline, your application must support all queries described in §1.2. After processing a
query, print the characteristics of the data structure used to answer the query as described in §3.
Submission instructions for the full project, as well as a grading rubric will be posted on Canvas.
6
Storm Event Application: Data and Query Format
The Storm and Fatality Event Data Format
Storm Data Query Format
Program Requirements for Project #2
Characteristics of the Data Structures
Submission Instructions
Requirements for Milestone Deadline
Requirements for Complete Project Deadline