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