Data Structure Class Notes - 1

Data - Plural form of datum, are simply values or set of values.

Data Item - Single unit of values.

Group Items - Data items that are divided into sub-items. Example: Students name - first, last, middle

Elementary Items - Data items that are not divided. Example: Students ID

Attributes	ID	Name	Grade
Values	1001	Mr. X	A+
	1002	Mr. Y	A

An entity is something that has certain attributes which may be assigned values. e.g. each student

Entities with similar attributes form an entity set. e.g. All students with grade is entity set

Data --------> Processing --------> Information

Information - meaningful or processed data

Field - a single elementary unit of information representing an attribute of an entity. e.g. ID, Name

Record - collection of field values of a given entity. e.g. One row contains 1001, Mr. X, A+ is one record

1.       Fixed-length records

2.       Variable-length records

File - collection of records of the entities in a given entity set. e.g. All values with attributes

Primary Key - specific field which uniquely determine the record in the file. e.g. ID field

Data Structure - The logical or mathematical model of a particular organization of data is called a data structure.

Arrays, Linked lists, Trees, Stack, Queue, Graph

Data Structure Operations

1.       Traversing - Accessing and processing each record exactly once

2.       Searching - Finding the location of the record with a given key or keys

3.       Inserting - Adding a new record to the structure

4.       Deleting - Removing a record from the structure

5.       Sorting - Arranging the data in some given order

6.       Merging  - Combining the records in two different sorted files into a single sorted file

Algorithm - a well-defined list of steps for solving a particular problem.

Complexity - Time required to execute the algorithm is proportional to the number of comparisons

Time-space tradeoff:

The time-space tradeoff refers to a choice between algorithmic solutions of a data processing problem that allows one to decrease the running time of an algorithmic solution by increasing the space to store the data and vice versa.