Summary
Summary Data structure and algorithim
- Course
- Institution
This document describes data structure, algorithm, types of data structure and data models.
[Show more]
Seller
Follow
simondemash
Content preview
ICS 2105 Data Structure and Algorithms NotesData Structure
The term data structure is used to describe the way data is stored, and the term algorithm is used
to describe the way data is processed. Data structures and algorithms are interrelated. Choosing a
data structure affects the kind of algorithm you might use, and choosing an algorithm affects the
data structures we use.
Data structure is a representation of logical relationship existing between individual elements of
data. In other words, a data structure defines a way of organizing all data items that considers not
only the elements stored but also their relationship to each other. The term data structure is used
to describe the way data is stored. To develop a program of an algorithm we should select an
appropriate data structure for that algorithm. Therefore, data structure is represented as:
Algorithm + Data structure = Program.
Definition:
A data structure is a particular way of organizing data in a computer so that it can be
used efficiently. Simply it is a scheme for storing related data in memory so it can be retrieved
quickly. Data structures provide a means to manage large amounts of data efficiently, such as
large databases and internet indexing services.
A data structure is an arrangement of data in a computer's memory or even disk storage. An
example of several common data structures are arrays, linked lists, queues, stacks, binary trees,
and hash tables.
The concept of data structure is,
• How to store a collection of objects in memory,
• What operations we can perform on that data,
• The algorithms for those operations, and
• How time and space efficient those algorithms are.
Data structures are divided into two types:
• Primitive data structures and Non-primitive data structures.
Primitive Data Structures are the basic data structures that directly operate upon the machine
instructions. They have different representations on different computers. Integers, floating point
numbers, character constants, string constants and pointers come under this category.
, Non-primitive data structures are more complicated data structures and are derived from
primitive data structures. They emphasize on grouping same or different data items with
relationship between each data item. Arrays, lists and files come under this category.
Data Organizing Principles
Ordering:
• Put keys into some order so that we know something about where each key is relative to the
other keys.
• Phone books are easier to search because they are alphabetized.
Linking:
• Add pointers to each record so that we can find related records quickly. E.g. The index in the
back of book provides links from words to the pages on which they appear.
Data Type. Data type of a variable is the set of values that the variable may assume. Basic data
types are int, char float, etc
Data models.
A data model is an abstract model that organizes elements of data and standardizes how they
relate to one another and to the properties of the real world entities. For instance, a data model
may specify that the data element representing a person be composed of a number of other
elements which, in turn, represent the description of the person and define its characteristics.
A data model can sometimes be referred to as a data structure, especially in the context
of programming languages.
The main aim of data models is to support the development of information systems by providing
the definition and format of data. According to West and Fowler (1999) "if this is done
consistently across systems then compatibility of data can be achieved. If the same data
structures are used to store and access data then different applications can share data.
Types of data models
Conceptual data model : describes the semantics of a domain, being the scope of the model.
For example, it may be a model of the interest area of an organization or industry. This
consists of entity classes, representing kinds of things of significance in the domain, and
relationship assertions about associations between pairs of entity classes. A conceptual
schema specifies the kinds of facts or propositions that can be expressed using the model. In
that sense, it defines the allowed expressions in an artificial 'language' with a scope that is
limited by the scope of the model.
, Logical data model : describes the semantics, as represented by a particular data
manipulation technology. This consists of descriptions of tables and columns, object oriented
classes, and XML tags, among other things.
Physical data model : describes the physical means by which data are stored. This is
concerned with partitions, CPUs, tablespaces, and the like.
Examlpe
Defining data structure of data stored in a database system.
CREATE TABLE employee (
EmployeeID VARCHAR(10) NOT NULL,
Last_Name VARCHAR(20) NOT NULL,
First_name VARCHAR(18) NOT NULL,
Soc_Sec VARCHAR(11) NOT NULL,
Date_of_Birth DATE,
Salary NUMBER) ;
CREATE TABLE dependant (
Last_Name VARCHAR(20) NOT NULL,
First_name VARCHAR(18) NOT NULL,
Soc_Sec VARCHAR(11) NOT NULL,
Date_of_Birth DATE,
EmployeeID VARCHAR(10) NOT NULL);
Algorithm
Definitions
An algorithm is a finite sequence of instructions, each of which has a clear meaning and can be
performed with a finite amount of effort in a finite length of time. No matter what the input
values may be, an algorithm terminates after executing a finite number of instructions. In
addition every algorithm must satisfy the following criteria:
Input: there are zero or more quantities, which are externally supplied;
Output: at least one quantity is produced;.
Definiteness: each instruction must be clear and unambiguous;
Finiteness: if we trace out the instructions of an algorithm, then for all cases the
algorithm will terminate after a finite number of steps;
Effectiveness: every instruction must be sufficiently basic that it can in principle be
carried out by a person using only pencil and paper. It is not enough that each operation
be definite, but it must also be feasible.
Algorithms, in everyday life we could simply call a sequence of actions. A finite sequence of
steps (commands, instructions) for solving a certain sort of problems is called an algorithm if it
can provide the solution to the problem after executing a finite number of steps.
, Algorithm. A finite sequence of instructions, each of which has a clear meaning and can be
executed with a finite amount of effort in finite time. Ie whatever the input values, an algorithm
will definitely terminate after executing a finite number of instructions.
Each algorithm has an input and an output. These are special sets of data in a special format.
The input is a set of data that has to be given prior to beginning the execution of the algorithm
but can be empty in some cases (e.g., the algorithm “open the entrance door” has no further
input, the algorithm itself determines the task). The output is a set of data, as well, however, it is
never an empty set. The output depends on the algorithm and the particular input. Both the input
and the output can be of any kind of data: numbers, texts, sounds, images, etc..
Algorithm can be broken up into steps coming from the following three basic classes of
structural elements:
Sequence is a series of actions to be executed one after another to get the solution.
Selection is a kind of decision where only one of a given set of actions can be executed,
and the algorithm determines the one.
Iteration (also called repetition) means a frame that regulates the repeat of an action
depending on a condition. The action is called the body of the iteration loop.
This means that all low or high level algorithms can be formulated as a series of structural
elements consisting only of the three types above. Hence, for any algorithm description method it
is enough to be able to interpret the three types above.
External memory data structure: A data structure that is efficient even when accessing
most of the data is very slow, such as, on a disk. The external memory could be magnetic
tape or even main memory if the cache is very fast.
Passive data structure: A data structure that is only changed by external threads or
processes, in contrast to an active data structure
Active data structure: A data structure with an associated thread or process that performs
internal operations to give the external behavior of another, usually more general, data
structure. For example, a queue is usually considered to be unbounded. However, actual
queues provided by the hardware or operating system may be significantly limited.
Changing the writing and reading processes to use a bounded queue makes those
applications more complicated. However, an active queue can accept input from the
writer through a system queue, and save items in memory or on disk if the system queue
for the reader is full. When the reader's queue has space, items can be retrieved and put
back in the queue. Although there are now three components, rather than just the writer
and reader, the high level abstraction is very simple and clear.
Persistent data structure: n computing, a persistent data structure is a data
structure that always preserves the previous version of itself when it is modified. Such
data structures are effectively immutable, as their operations do not (visibly) update the
structure in-place, but instead always yield a new updated structure.
A data structure is partially persistent if all versions can be accessed but only the newest
version can be modified. The data structure is fully persistent if every version can be
both accessed and modified. If there is also a meld or merge operation that can create a
new version from two previous versions, the data structure is called confluently
persistent. Structures that are not persistent are called ephemeral
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller simondemash. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $15.49. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
83822 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now