INF 503 Large-scale Data Structures And Organization

Reference no: EM132839594

INF 503 Large-scale Data Structures And Organization - Northern Arizona University

Problem - Fun with direct access arrays

Create a class called FASTAreadset_DA. The purpose of the class will be to contain a FASTA read set (similar to homeworks #1 and #2) and all of the functions needed to operate on this set. Use the direct access hash table data-structure to store the genomic sequences of the given read dataset (hint: use an array of Boolean values - bool[] for your hash table). You will need to read in the genomic sequence fragments (feel free to ignore / discard all headers), covert them to a radix notation number (hint: try using an unsigned int to store the radix value), and flip the proper Boolean in the hash array to TRUE. If the Boolean is already "ON" (i.e. you are seeing a duplicate fragment), you'll need to record this ‘collision'.

At minimum, the class must contain:
• A constructor
• A destructor
• A function to search the hash table for a given 16-mer sequence
• A function to insert a given 16-mer sequence into the hash table
• Private variables to store the total # of collisions and # of elements stored in the array

A. Getting started: read in the read data set into your data structure
• What is the size of your hash table?
• How many collisions did you observe?
• How many unique sequences did you observe (number of "ON" Boolean values)?
• What is the load (αT) in your hash table?
B. Search time in direct access arrays: read in the genome sequence provided above, iterate through all 16-mers found in the genome, and use them to query the read set (similar to what you did in HW#2, problem 2B).
• How many genome 16-mer fragments were found in your read set?
• How long did it take to complete the entire search process (all 16-mers)?

Problem #2: The hash table with chaining
Create a class called FASTAreadset_Chain. Use the hash table data-structure to store the genomic sequences of the given read dataset (hint: you will need to provide the size of the hash table). If you have a duplicate sequence fragment or a duplicate hash value, use chaining method to resolve collisions. Resizing is optional - you can hard-code the proper hash table size through the constructor. Use Radix / division scheme for hash function implementation.
At minimum, the class must contain:
• A constructor
• A destructor
• A function to search the hash table for a given 16-mer sequence
• A function to insert a given 16-mer sequence into the hash table
• A private variable to set the hash table size
• A private variable to count the number of collisions during hash table creation

A. Assessing the impact of the hash table size. For this you will need to set the hash table to a fixed value (m, see below) and read in the read set to populate the hash table. Set the size of your hash table (m) to 10 thousand, 100 thousand, 1 million, and 10 million elements.
• For each of your 4 hash table sizes, how many collisions did you observe while populating the hash?
• For each of your 4 hash table sizes, how long did it take you to read the sequence fragment file?
• Do the results make sense? Explain.

B. Searching in the chain-linked hash table. Set the hash size to 10,000,000 and populate it using the read set. Read in the genome, iterate through all 16-mers found in the genome, and use them to query the read set (similar to what you did in HW#2, problem 2B).
• How many genome 16-mer fragments were found in your read set?
• How long did it take to complete the entire search process (all 16-mers)?
• How does that compare to the direct access array search times you've implemented as part of problem 1B?

Attachment:- Direct access arrays.rar

Reference no: EM132839594

Questions Cloud

Offensive and defensive strategies : Determine whether to pursue offensive or defensive strategies to improve an organization's market position

Prepare extraordinary item portion of financial statement : First Bank Corporation has an effective tax rate of 35%. Prepare the extraordinary item portion of First Bank Corporation's financial statement

Describe the benefits of the guidance approach : For this assignment, create a digital brochure that could be emailed to families explaining the guidance approach and its importance for teaching children.

Prepare the journal entry for the debt service fund : Prepare the journal entry for the debt service fund to reflect the transfer of funds from the General Fund to the debt service fund in anticipation

INF 503 Large-scale Data Structures And Organization : INF 503 Large-scale Data Structures And Organization Assignment Help and Solution, Northern Arizona University - Assessment Writing Service

Create an activity that demonstrates the oral language : Create an activity that demonstrates the oral language or listening enhancing feature of the literature selection. Consider diverse learners. You will use this.

Who has the final responsibility for positions taken : She pays alimony to her former husband. Who has the final responsibility for positions taken with respect to the controversial matters on the tax return?

What is the value on November : What is the value on November 8, 2000 of making quarterly payments of $260 over 11 years if the first payment is on February 8, 2009

Customer responsiveness and innovation : How do these resources enable Southwest to improve one or more of the following: ef-ficiency, quality, customer responsiveness and innovation?

User Account

All Pages