CC4 - chapter 1 and 2 Flashcards by Maurriel de Leon

– machine that manipulates data.

Computer

How well did you know this?

Not at all

Perfectly

–Concealing of the implementation details of data object from the outside world

Data encapsulation / information hiding

How well did you know this?

Not at all

Perfectly

– separation between specification of a data object and its implementation

Data abstraction

How well did you know this?

Not at all

Perfectly

– a collection of objects and set of operations that act on those objects

Data type

How well did you know this?

Not at all

Perfectly

– storing and organizing data in a computer so that it can be used efficiently.

Data structure

How well did you know this?

Not at all

Perfectly

– may be organized in many different

Data

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

DATA STRUCTURE OPERATIONS

traversing
searching
inserting
deleting

How well did you know this?

Not at all

Perfectly

– accessing each record exactly once so that certain items in the record may be processed.

Traversing – retrieving/visiting

How well did you know this?

Not at all

Perfectly

– finding the location of the record

Searching – insert

How well did you know this?

Not at all

Perfectly

– adding new records to the structure.

Inserting – update

How well did you know this?

Not at all

Perfectly

– removing

Deleting – remove

How well did you know this?

Not at all

Perfectly

– used by os, Compilers, dbms, data communications

data structure/+ algorithms

How well did you know this?

Not at all

Perfectly

– its elements form a sequence
- Array
- Stack – lifo
- Queue – fifo
- Linked list

Linear data structure

How well did you know this?

Not at all

Perfectly

– represent data containing a hierarchical relationship between elements
- Tree & graph

Non-linear data structure

How well did you know this?

Not at all

Perfectly

Quick insertion, very fast access if
Slow search, Slow deletion, index is known, Fixed size

Arrays

How well did you know this?

Not at all

Perfectly

Quicker search than unsorted array. Slow insertion and deletion, Fixed size

Ordered Array

How well did you know this?

Not at all

Perfectly

Provides last-in first-out access Slow access to other items

Stack

How well did you know this?

Not at all

Perfectly

Provides first-in first-out access Slow access to other items

Queue

How well did you know this?

Not at all

Perfectly

Quick insertion and quick deletion Slow search

Linked List

How well did you know this?

Not at all

Perfectly

Quick search, insertion and Deletion algorithm is deletion if tree remains balance complex.

Binary Trees

How well did you know this?

Not at all

Perfectly

Very fast access if key known, Fast Slow deletion, access slow if key not known, inefficient memory usage

Hash Table

How well did you know this?

Not at all

Perfectly

Fast insertion, deletion. Access to Slow access to other items

Heap

How well did you know this?

Not at all

Perfectly

Models real world situation Some algorithms are slow access.

Graph

How well did you know this?

Not at all

Perfectly

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**