Data Structures And Algorithms

Front 1

Algorithm

Back 1

A finite sequence of unambiguous instructions performed to achieve a goal or compute a desired result

Noth a solution, but a precisely defined procedure for deriving solution

Front 2

Algorithmics

Back 2

The study of algorithms

Front 3

Process

Back 3

A sequence of operations performed to achieve a goal

Front 4

Algorithm vs Process

Back 4

Algorithm:

-each step unambiguously specified

-clearly defined termination

Process:

-higher complexity of work, may contain multiple algorithms as steps

-specification may contain ambiguity ("Increase customer awareness")

-may be continually ongoing ("improve business process")

Front 5

An algorithm should specify:

Back 5

Name and purpose

Input and output

Unambiguous finite sequence of steps

Termination condition or state

Front 6

Examples of Algorithms: Selection Sort

Back 6

Selection Sort

-purpose: sort array of ints in ascending order

-input: array of ints (size = n)

-output: sorted array of ints ascending

-steps:

for each cur = 0 to n-2...

determine min value from cur+1 to n-2

if cur>min, swap the two

output and terminate when done all

Front 7

Examples of algorithms

Back 7

Converting CAD to yen

Selection sort

Front 8

Data structure

Back 8

coherent organization of related data items for storage and usage

organized way to manage large amounts of data efficiently

facilitates design of algorithms

in C++ we use structs or classes to represent data structures

Front 9

Structs

Back 9

typically declared globally (but no mem allocated)

When structure type defined, we can declare variables of this new type and allocate memory:

ex. CDAccountV1 = account;

Front 10

Dot Operator

Back 10

used to access struct or class members (ex. account.balance, account.interestRate)

These members are called member variables

Can also be used to access member function (ex. today.output(); )

Front 11

Classes

Back 11

Focus of classes is on objects (OOP)

Variables of the class type are objects

Members are usually private

Only the function declaration is provided, implementation must be done later

Front 12

Objects

Back 12

Contain data (members) and operations (functions/methods)

Declared as:

Type objectName;

ex. DayOfYear today;

Front 13

Implementing class member functions

Back 13

Can be after main

Must specify class

void DayOfYEar::output(){ ... }

:: is the scope of resolution operator

specifies what class the definition comes from

item before :: is the type qualifier

Front 14

Abstract Data Type (ADT)

Back 14

Collection of data items given a name, purpose and a set of operations that operate on the data items

Only the interface (operations) are exposed, data organization is hidden