PRELIM-LESSON 1 Flashcards
the programmatic way of storing data so that data can be used efficiently.
Data Structures
true or false: almost every enterprise application uses various type of structures in one or the other way.
true
systematic way to organize data in order to use it efficiently
data structure
true or false: each data structure has an interface
interface
represent the set of operations that a data structure supports.
interface
only provides the list of supported operations, type of parameters they can accept and return type these operations.
interface
provides the internal representation of a data structure
Implementation
It also provides the definition of the algorithms used in the operations of the data structure.
Implementation
true or false: data structure are used to implement the physical forms of abstract data types.
true
true or false: Data structures are a
crucial part of designing efficient software. They also play a
critical role in algorithm design and how those algorithms are
used within computer programs.
true
examples of how data structures are used:
storing data
managing resources and services
data exchange
ordering and sorting
indexing
searching
scalability
they use algorithms that are tightly coupled with the data structures-such as lists, queues, and mapping from one set of values to another.
software engineers
Data structures are used for efficient data persistence, such
as specifying the collection of attributes and corresponding structures used
to store records in a database management system.
storing data
Core operating system (OS) resources
and services are enabled through the use of data structures such as linked
lists for memory allocation, file directory management and file structure
trees, as well as process scheduling queues.
managing resources and services
Data structures define the organization of information
shared between applications, such as TCP/IP packets
data exchange
Data structures such as binary search trees – also known
as an ordered or sorted binary tree – provide efficient methods of sorting objects,
such as character strings used as tags. With data structures such as priority
queues, programmers can manage items organized according to a specific
priority.
ordering and sorting
Even more sophisticated data structures such as B-trees are used to
index objects, such as those stored in a database.
indexing
Indexes created using binary search trees, B-trees or hash tables
speed the ability to find a specific sought-after item.
searching
Big data applications use data structures for allocating and managing
data storage across distributed storage locations, ensuring scalability and
performance. Certain big data programming environments – such as Apache
Spark – provide data structures that mirror the underlying structure of database
records to simplify querying
scalability
need for data structure
data search
processor speed
multiple request
Consider an inventory of 1 million(106) items of a store. If the
application is to search an item, it has to search an item in 1 million(106) items
every time slowing down the search. As data grows, search will become
slower.
data search
although being very high, falls limited if
the data grows to billion records.
processor speed
As thousands of users can search data simultaneously on
a web server, even the fast server fails while searching the data.
multiple requests
execution time cases
worst case
average case
best case
This is the scenario where a particular data structure operation
takes maximum time it can take. If an operation’s worst case time is ƒ(n) then
this operation will not take more than ƒ(n) time where ƒ(n) represents function
of n.
worst case
This is the scenario depicting the average execution time of an
operation of a data structure. If an operation takes ƒ(n) time in execution, then
m operations will take mƒ(n) time.
average case
This is the scenario depicting the least possible execution time of
an operation of a data structure. If an operation takes ƒ(n) time in execution,
then the actual operation may take time as the random number which would be
maximum as ƒ(n).
best case
are values or set of values
data
refers to single unit of values
data item
data items that cannot be divided into sub item are called as
group items
data items that cannot be divided are called as
elementary items
−An entity is that which contains certain attributes or
properties, which may be assigned values
attribute and entity
Entities of similar attributes form an
entity set
single elementary unit of information representing an attribute of
an entity.
field
collection of field values of a given entity.
record
collection of records of the entities in a given entity set
file
8 common data structures concepts
array
linked lists
stacks
queues
hash tables
trees
heaps
graphs
specialized means of organizing and storing
data in computers in such a way that we can perform operations on
the stored data more efficiently.
data structures
have a wide and
diverse scope of usage across the fields of Computer Science and
Software Engineering.
data structures
a structure of fixed-size, which can hold items of the same
data type. It can be an array of integers, an array of floating-point numbers, an
array of strings or even an array of arrays (such as 2-dimensional arrays).
Arrays are indexed, meaning that random access is possible
array
Used as the building blocks to build other data structures such as array lists,
heaps, hash tables, vectors and matrices.
applications of array
Used for different sorting algorithms such as insertion sort, quick sort,
bubble sort and merge sort.
application of arrays
sequential structure that consists of a sequence of items in
linear order which are linked to each other. Hence, you have to access data
sequentially and random access is not possible. Linked lists provide a simple and
flexible representation of dynamic sets.
linked lists
Used for symbol table management in compiler design.
applications of linked lists
Used in switching between programs using Alt + Tab (implemented using Circular
Linked List).
applications of linked lists
(Last In First Out — the element placed at last can be
accessed at first) structure which can be commonly found in many programming
languages. This structure is named as “stack” because it resembles a real-world
stack — a stack of plates.
stacks
Used for expression evaluation (e.g.: shunting-yard algorithm for parsing and
evaluating mathematical expressions).
applications of stacks
Used to implement function calls in recursion programming
applications of stacks
FIFO (First In First Out — the element placed at first can be
accessed at first) structure which can be commonly found in many programming
languages. This structure is named as “queue” because it resembles a real-world
queue — people waiting in a queue.
queues
use to manage threads in multithreading
applications of queues
Used to implement queuing systems (e.g.: priority queues).
applications of queues
data structure that stores values which have keys
associated with each of them. Furthermore, it supports lookup efficiently if we know
the key associated with the value. Hence it is very efficient in inserting and searching,
irrespective of the size of the data.
hash table
Used to implement database indexes.
* Used to implement associative arrays.
* Used to implement the “set” data structure.
applications of hash tables
a hierarchical structure where data is organized hierarchically and
are linked together. This structure is different from a linked list whereas, in a linked
list, items are linked in a linear order.
trees
application of trees
binary trees
binary search tree
heaps
treaps
Used to implement expression parsers and expression solvers
binary trees
used in many search applications where data are constantly
entering and leaving.
binary search tree
used by JVM (Java Virtual Machine) to store Java objects.
heaps
used in wireless networking
treaps
is a special case of a binary tree where the parent nodes are
compared to their children with their values and are arranged accordingly
heaps
Used in heapsort algorithm.
* Used to implement priority queues as the priority values can be ordered according
to the heap property where the heap can be implemented using an array.
- Queue functions can be implemented using heaps within O(log n) time.
- Used to find thekᵗʰsmallest (or largest) value in a given array.
applications of heaps
consists of a finite set of vertices or nodes and a set of edges
connecting these vertices. The order of a graph is the number of vertices in the graph.
The size of a graph is the number of edges in the graph.
graphs
