Software Development Part 2 Flashcards
sequential file structure
- contains consecutive records and is read starting from beginning
- typical of data on magnetic tape
indexed sequential file
- a file with a separate index file to help locate records more quickly random file structure
-random file structure
- allows access to any record without starting at beginning of file
indexing
a means of specifying the order of records without actually changing their physical order
index file (key file or keyword file)
ordered list of items with references to the complete record
key field (record index)
field in the record that is indexed
sorting routine
- places data in ascending or descending numerical or alphabetical order
sorting routine
- puts dat in order
- -> from highest from lowest numerically
- -> from lowest to highest numerically
- -> alphabetically
- -> reverse alphabetically
common methods
- successive minima
- bubble sort
- insertion sort
successive minima
- list is searched to find smallest element
- smallest element is brought to top of list
- process is repeated for remaining elements
- n(n-1)/2 comparisons needed to sort n items
- when n is large n^2/2 is sometimes used as approximation
bubble sort
- first and second elements in list are compared
- if first is larger, positions are switched
- second and third elements are the compared, and so on
- process continues till end of list is reached, constituent one pass through data
- process repeated until one pass through the data results in no exchanges
- so called because smaller elements “bubble” to top of list
- on average, n^2/2 comparisons needed
insertion sort
- elements are ordered by rewriting them in proper sequence
- after the proper position of an element is found, all elements below that position are bumped down one places
- the vacancy is filled by the inserted element
- About n^2/ 2 comparisons are needed at most
- average number of comparisons is about n^2 /4
linear search (sequential search)
- finds an element if a group of records is randomly organized
- at best, one comparison is required
- at worst, n comparisons are required in a list of n elements
- average of n/2 comparisons
binary search
- faster than linear search if records are in ascending or descending order
- checks middle element, then removes half of list from consideration
- checks middle element from remainder of list, and so on
- maximum number of required comparisons in a list of n elements is log2 (2 is subscript down) n= log n/ log 2
hashing function
- procedure by which a numeric or nonnumeric key is converted into a record number
- for example, may convert each customer’s name into an integer, so that records for that customer are stored at that location number
collision
- occurs when hashing function assigns same record number to different keys
- chaining, linear probing, and double hashing are techniques used to resolve such collisions
database
- can be implemented as
- indexed file
- linked list
- tree structure
- records are written in and remain in order of entry
- various methods use to locate needed records
indexed file
= keeps all data in one data file
- maintains one separate key file for each key field (may be one or more key fields)
- searches in key file to find record number corresponding to a given piece of data
- updates key files each time records are added to data file
flat file
- only one file (no separate index file)
- has only one key field by which records are located
linked list
- a technique for locating records in a flat file
- each record contains pointer to next record in key sequence
- two pointers change whenever a record is added or deleted
binary tree structure
- each record contains two pointers, to next higher and next lower record in key sequence
-records are referred to as nodes; first record is root node - node above is called parent; node below is child or offspring
- number of comparisons needed is
1 + (log n / log 2)
hierarchical database
- contains records in an organized, structured format
- organizes records according to one or more indexing schemes
- each field within a record not normally directly accessible
relational database
- stores all information in the equivalent of a matrix
- no index files, pointers, and so on needed to find, read, edit or select information
- information can be accessed directly by referring to field name or field value
artificial intelligence (AI)
- the capacity of a machine to
- -> absorb and organize new data
- -> learn new concepts
- -> reason logically
- -> respond to inquiries
expert systems
- learn rules from sets of events that are entered whenever they occur
- once the rules are learned, can give advice, make predictions and diagnoses, or draw conclusions
testability
determines:
- ability to detect and correct errors
- verify limiting operation
- determine functionality
software fault tolerance
designed into a system by
- synchronizing operations
- implementing checkpoints
- logging
- programming recovery techniques