CC4 - chapter 1 and 2 Flashcards
– machine that manipulates data.
Computer
–Concealing of the implementation details of data object from the outside world
Data encapsulation / information hiding
– 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
Data type
– storing and organizing data in a computer so that it can be used efficiently.
Data structure
– may be organized in many different
Data
CHARACTERISTICS OF ALGORITHM
- Provides description of elements in terms of data types
- Defines the relationship among individual
Elements - Valid operations and parameters to be passed
- Error conditions associated with the operations
DATA STRUCTURE OPERATIONS
- traversing
- searching
- inserting
- deleting
– accessing each record exactly once so that certain items in the record may be processed.
Traversing – retrieving/visiting
– finding the location of the record
Searching – insert
– adding new records to the structure.
Inserting – update
– removing
Deleting – remove
– used by os, Compilers, dbms, data communications
data structure/+ algorithms
– its elements form a sequence
- Array
- Stack – lifo
- Queue – fifo
- Linked list
Linear data structure
– represent data containing a hierarchical relationship between elements
- Tree & graph
Non-linear data structure
Quick insertion, very fast access if
Slow search, Slow deletion, index is known, Fixed size
Arrays
Quicker search than unsorted array. Slow insertion and deletion, Fixed size
Ordered Array
Provides last-in first-out access Slow access to other items
Stack
Provides first-in first-out access Slow access to other items
Queue
Quick insertion and quick deletion Slow search
Linked List
Quick search, insertion and Deletion algorithm is deletion if tree remains balance complex.
Binary Trees
Very fast access if key known, Fast Slow deletion, access slow if key not known, inefficient memory usage
Hash Table
Fast insertion, deletion. Access to Slow access to other items
Heap
Models real world situation Some algorithms are slow access.
Graph
Algorithm – finite set of instructions that takes some raw data as input and transforms it in to refined data.
Algorithm
ALGORITHM STEPS
- input
- output
- definiteness
- finiteness
- effectiveness
– zero or more quantities are externally supplied
Input
– at least one quantity is produced
Output
– each instruction is clear and unambiguous
Definiteness
– algorithm terminates after a fi nite number of steps
Finiteness
– every instruction must be basic enough to be carried out
Effectiveness
COMMON TYPES OF ALGORITHM
- searching
- sorting
- compression
- fast Fourier transforms
- encoding
- geometric
- pattern matching
- parsing
– search for a given item in large data collection
Searching
– arrange data items
Sorting
Compression – reduce the size of data and program files
Compression
– designed for digital signal processing
Fast fourier transforms
– encryption of data
Encoding
– identification of geometric shapes
Geometric
– comparing images and shapes
Pattern matching
– identify different programming constructs
Parsing
CLASSIFICATION OF ALGORITHM
- iterative
- divide and conquer
- greedy
- back tracking
– repeated in loops until the goal is achieved
Iterative
– fragmented into subproblems which are solved partially
Divide and conquer
– an immediately available best solution at each step is chosen
Greedy
– all possible solutions are explored
Back tracking
EXPRESSING AN ALGORITHM
- natural language
- graphic representations
- programming language
– must be well defined and unambiguous
Natural language
– flowcharts
Graphic representations
– low level implementation must be removed and replaced by natural language
Programming language
- Limitation of recursion (only factorials, ackermann, fibonacci, …)?
- A tool for theorician?
- Theorem: ‘’any program that can be written using assignment, th
- E ifelse statement and the while statement can also be written using assignment, if-else and recursion.’’
- Example: Fibonacci – f(0)=f(1)=1 – f(n) = f(n1)
+ f(n2)
Recursive algorithm
- Stated as a function relating the length to the number of steps
- Is the time and space it uses
Complexity
2 CRITERIA FOR PERFORMANCE ANALYSIS
- space complexity
- time complexity
– the amount of memory needed by a program to run to completion
Space complexity
– the amount of computer time needed by a progra m to run to completion
Time complexity
TWO PHASES IN PERFORMANCE EVALUATION
- performance analysis
- performance measurement
– priori estimate
Performance analysis
– priori testing fixed
Performance measurement
part – independent. Memory does not change
variable
part – dependent. Memory do change
asymptotic
– helps to compare algorithms worst case running
notation
– 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 finite, ordered sequence of data itemsknown as elements.
List
– each element has a positionin the list.
“ordered”
– number of elements currently stored
Length of the list
T/F:
There are two standard approaches to implementing lists, the arraybased list, and the linked list.
true
T/F:
- The beginning of the list is called the tail, and the end of the list is called the Head.
false (baligtad)
– it is a collection of homogenous,
Ordered andfinite set of elements. It is a linear data structure. Its data type can be primitive, composite or other data types.
Array
– same element type and have the same structure
Homogenous
– organized in sequence.
Ordered
– fixed number of elements.
Finite
ADVANTAGES OF AN ARRAY
- An array uses a single variable to
Represent a large set of homogenous data collection. - An array provides direct access to a storage address for an element.
Therefore, retrieval of an element is extremely fast. - The elements on an array can be
Manipulated easily using an index. Thus, processing of array is flexible. - It is easy to create and initialize an array.
Arrays are good at implementing iterative algorithms. - Multi-dimensional arrays facilitate grouping of data collection into hierarchical structure
ACCESSING ARRAY
- index
- index set
- lower/upper bound
- array name/index
*bracket notation
– array the position of an element
Index
– range of values for the index
Index set
– smallest and largest value in of index
Lower and upper bound
– individual elements of an array
Array name and array index
DISADVANTAGES OF AN ARRAY
- Array size cannot be increased or decreased during runtime.
- Insertion and deletion operations on arrays are not efficient.
- For very large data sets, the program may run out of the storage space
ARRAY OPERATION
- retrieving
- adding
- deleting
- inserting
- traversing
– -it is also called accessing
**Retrieving **
- To retrieve an element we must know the index value
– inserts new element in a position specified by the index
- aka assigning
Adding
– deleting operation removes an existing element with the given index.
Deleting
– it adds new element in a specified position, without replacing any existing element the position is specified in terms of index value or position relative to an existing element.
Inserting
– involves accessing and processing an array element exactly once
- aka visiting
Traversing
- Two-dimension arrays can be used to store and process strings
- A string is a sequence of characters
- In c/c++, a string contains a null terminating character
- In several applications, we need to store a group of related strings
- 2-d arrays provide a convenient and
- Simple mechanism for storing elements
- Since in 2-d arrays, all rows must have the same number ofharacters, storage space may be wasted if some of the
- Strings have shorter lengths
String arrays
