Homework 4
Home Up Work My Stuff UMKC

 

Homework #4 - Individual or Group
Due Date: February 21st
Points: 75

For each of the following data structures based on the class readings (both text and notes), determine the attributes and operations necessary from a programming language specification approach for each of the following application areas. Then assess feasibility of including each of those data structures based on the implementation issues for storage representation and storage management.

Arrays
Multidimensional arrays
Slices (substructure of an array)
Records
Lists
Character strings
Pointers
Sets
Files (pick one type of file)
Variant records

 

  1. Real-time system for monitoring kidney dialysis machine.

  2. Event driven system for traffic light control.

  3. Inventory system.

 

Arrays

        Attributes:

        -homogenous elements
        -binding to subscript value ranges and binding to storage:

  1. Static

  2. Fixed Stack-Dynamic

  3. Stack-Dynamic

  4. Heap-Dynamic

        -indexed elements

        Operations:

        -initialization
        -random or sequential access to elements
        -catenation
        -operations on array as a unit

        
 

 

Multidimensional arrays

        Attributes:

        -homogenous elements
        -binding to subscript value ranges and binding to storage:

  1. Static

  2. Fixed Stack-Dynamic

  3. Stack-Dynamic

  4. Heap-Dynamic

        -indexed elements
        -column-major or row-major order

        Operations:

        -initialization
        -random or sequential access to elements
        -catenation
        -operations on array as a unit


 

Slices (substructure of an array)

        -same properties as arrays
        -need mechanism to specify reference to particular slice

 

Records

        Attributes:
        -heterogeneous elements
        -fixed number of fields
        -field references

  1. Fully qualified

  2. Elliptical

Operations
-assignment
-"move corresponding"    

    
        

Lists

        Attributes:
        -fixed data type
        -length is limited to available space
        -singly-linked, doubly-linked
        
        Operations
        -insertion
        -deletion
        -whole data structure operations


        

Character Strings

        Attributes:
        -sequence of characters, therefore homogenous components    
        -static, limited dynamic or dynamic length
        -elements can be indexed

        Operations:
        -simple pattern matching
        -catenation
        -relational operations
        -length determination
        -copying
        -insertion and deletion of elements

Pointers

        Attributes:
        -used to reference other variables
        -dynamic storage management
        -contain memory addresses or nil
      

        Operations:
        -assignment
        -dereferncing
        -pointer arithmetic


Sets

        Attributes:
        -homogenous components (base type)
        -limited number of elements
        -limited flexibility

        Operations:
        -set union
        -set intersection
        -set equality

Data Files 

        Attributes:
        -limited in size to the space available
        -data can be accessed sequentially
        -data can be homogenous and heterogeneous

        Operations:
        -read/write
        -open/close
        -append
        -search

Variant records

        Attributes:
        -heterogeneous components
        -each construct includes type indicator (tag)
        -size of storage determined by largest variant
        -linear storage organization

        Operations:
        -assignment
        -access
        

 

Considerations:

Real-time system for monitoring kidney dialysis machine.

This system needs speed, reliability and ability to store, access and update a variety of records. Memory requirements are not critical. There is no need to search records.

Event driven system for traffic light control.

This system needs speed and reliability, but there is no need to store complicated records since it is event-driven. There may be a need to store some constant values such as time intervals .Memory requirements are critical.

Inventory system.

This system needs reliability and ability to store and access large complicated records. The speed is important, but not critical. Search is an important part of the system.

Based on the above requirements the following table illustrates the usage of the data structures in described applications:

Using Data Structures in Various Applications
Kidney Dialysis Machine

(Real-Time )

 Traffic Light Control

(Event driven)

 Inventory System
Arrays Arrays can be used to store data. Since there is no need for searches, arrays are very efficient. Arrays can be used to store process constants. Arrays can be used to store data, if it is not involved in searches.
Multidimensional arrays Can be used if necessary, but are not efficient due to large overhead. There is no need for complicated storage structures. Can be used with the same reservation as above.
Slices (substructure of an array) Can be used if necessary to reference parts of arrays. Can be used, but not needed. Can be used with arrays to access groups of elements.
Records Can be used to group data. Can be used but not needed. Very useful and efficient way to store inventory. Provides for better access and readability.
Lists Efficient way to insert and delete data. Very useful for real-time system. Can be used to store events sequence. Efficient way insert and delete data, however searches are sequential and, therefore, slow.
Character strings Can be used to produce readable output. Not necessary, system does not produce output, unless some record keeping is required. Needed to produce output, describe data and allow searches.
Pointers Fast memory management, decrease reliability. Not needed. Needed for better efficiency and memory management.
Sets Efficient but not flexible. Not needed. Not needed. Not needed.
Data Files Needed for some operations. Limited usage due to slow access. Not needed. Integral part of an inventory system to store output and databases.
Variant records May be needed to store process constants but decrease reliability. Not recommended. Not needed. Not needed.

 

e-mail Mikhail Viron

Write to Your Representative