CC4 Mid 1, 2, 3 Flashcards
Get me from home to work
Balance my checkbook
Simulate a jet engine
Graduate from SPU
Solving Problems
Designing programs (architecture, algorithms)
Writing programs
Verifying programs
Documenting programs
Using a computer to help solve problems
Data Structure and Algorithm Design Goals
Correctness
Efficiency
Robustness
Reusability
Adaptability
A computer is a machine that manipulates data.
The prime aim of data structure includes to study how data is organized in a computer, how it is manipulated, how it is retrieved, and how it can be utilized, resulting in more efficient programs.
Data Representation
the concealing of the implementation details of data object from the outside world
Data Encapsulation or Information Hiding
the SEPARATION between specification of a data object and its implementation
Data Abstraction
a collection of objects and set of operations that act on those objects
Primitive
Composite
Data Type
Data may be organized in many different ways, the logical or mathematical model of a particular organization of data in memory or on disk is called
Data Structure
are used for manipulation of data.
Algorithms
Accessing each record exactly once so that certain items in the record may be processed.(This accessing or processing is sometimes called ‘visiting” the records.)
Traversing
FINDING the location of the record with a given key value, or finding the locations of all records, which satisfy one or more conditions.
Searching
Adding new records to the structure.
Inserting/Append
Removing a record from the structure.
Deleting
Used by OS, compilers, DBMS, data communications
Image processing, digital signal processing, simulations, numerical computations, cryptography, data compressions and genetic studies
Usage of Data Structures / Data Structures +Algorithm
Mainly to represent data containing a hierarchical relationship between elements
Tree
Graph
Its elements form a sequence or in other words a linear list.
Array
Stack
Queue
Linked List
Quick insertion, very fast access if index is known
Arrays
Quicker search than unsorted array.
Ordered Array
Provides last in first out access
Stack
Provides first in first out access
Queue
Quick insertion and quick deletion
Linked List
Quick search, insertion and deletion if tree remains balance
Binary Trees
Very fast access if key known, Fast insertion
Hash Table
Fast insertion, deletion. Access to largest item
Heap
Models real world situation
Graph
Zero or more quantities are externally supplied
Input
At least one quantity is produced
Output
Each instruction is clear and unambiguous
Definiteness
If we trace out the instructions of an algorithm, then, for all cases, the algorithm terminates after a FINITE number of steps
Finiteness
every instruction must be basic enough to be carried out, in principle, by a person using only pencil and paper. Its not enough that each operation be definite as in (3): it also must be feasible.
Effectiveness
must be well defined and unambiguous (what about portability?)
Natural Language
flowcharts (only for small and simple algorithms)
Graphic Representation
low level implementation must be
removed and replaced by natural language
Programminglanguages
‘Any program that can be written using assignment,
the if else statement and the while statement can also be written using assignment, if-else and recursion.’’
Theorem
the amount of memory needed by a program to
run to completion
Space Complexity
the amount of computer time needed by a
program to run to completion
Time complexity
a PRIORI estimates;
Performance Analysis
a POSTERIORI testing.
Performance Measurement
This is a THEORITICAL analysis of an algorithm. Efficiency of an algorithm is measured by assuming that all other factors, for example, processor speed, are constant and have no effect on the implementation.
A Priori Analysis
This is an EMPIRICAL analysis of an algorithm. The selected algorithm is implemented using programming language. This is then executed on target computer machine. In this analysis, actual statistics like running time and space required, are collected.
A Posterior Analysis
independent of the characteristics (e.g. number, size) of
the inputs and outputs
instruction space (space of the code itself)
space for constants, … –
Fixed Part
dependent on the particular problem instance being
solved, hence on the inputs and outputs characteristics
variables whose size depends on inputs/outputs,
recursion stacks (when it depends on inputs/outputs).
Variable Part
Types of Analysis
Worst Case Running Time
Average Case Running Time
Best Case Running Time
is the longest running time for any input of size n
Worst Case Running
Often it is assumed that all inputs of a given size are equally likely.
Average Running Time
rarely occurs in practice comparatively with the first and second case.
Best Case Running Time
is a way of solving a problem or calculation in less time by using more storage space (or memory), or by solving a problem in very little space by spending a longtime.
Time Space Tradeoff
Is a conclusion of homogenous, ordered, and finite set of elements
Array
Implies all elements must be off the SAME TYPE and have the same structure
Homogenous
Means that elements are organized in sequence
Finite
Are BUILT into a programming language with no extra definition needed in the part of the programmer
Primitive data type
T or F
An array uses a single variable to represent a large set of homogenous data collection
True
T or F
An array provides direct access to a storage area for an element
True
T or F
The elements on an array can be manipulated easily using an index
True
T or F
It is easy to create and initialize an array
True
T or F
Arrays are good at implementing iterative algorithms
True
T or F
Number dimensional arrays facilitate grouping of data collection into hierarchical structure
True
T or F
Array size cannot be undressed or decreased during runtime
True
T or F
Insertion and deletion in arrays are not efficient
True
For every large data sets the may run out of the storage space
True
In an array the position of an element is identified by a variable called
Index
The range of values is for the INDEX is referred to as
Index Set
Smallest value in of index is called ____ and largest ____
Lower bound, Upper bound
Individual elements of an array are identified by an ____ and _____
Array name, array index
Represents arrangement of data elements in the MEMORY
Storage structure
ADDRESS of the first elements is called
Base address
Retrieving, it is also called
Accessing
The last element points to
NULL
removes all elements of the list (disposes the list)
Delete List
returns the NUMBER of elements in the list
Count
also called as growable array, resizable array, DYNAMIC table, or array list
Dynamic Array
Advantage of linked lists is that they can
be expanded in
constant time
Disadvantage of linked lists is
access time to individual elements
function takes a linked list as input and counts the number of nodes in the LIST.
List Length
