Data Structure and Algorithm

Data Structure

Storing and organizing data in a computer

Primitive

• these are basic data structures and are directly operated upon by machine instructions 

Non - Primitve

These are derived from primitive data structures.

Homogeneous

• all elements are same type

Heterogenenous

• elements are of different types. 

Static

•  the size of this data structure cannot be changed after the initial allocation, like matrices.

Dynamic

The size can be changed dynamically, like in a list.

Linear

•  this data structure maintains a linear relationship between its elements, e.g., array.

non Linear

• this data structure does not maintain any linear relationship between its elements, e.g., in a tree.

main memory (RAM)

where instructions (programs) and data are stored; volatile means may be lost once the computer is powered down.

Cache Memory

•  is used to store frequently used instructions and data that either is, will be, or has been used by the CPU. A segment of the CPU’s cache memory is called a register ( a small amount of memory that is used to temporarily store instructions and data.

Persistent Storage

• used to store instructions and data in external devices such as a hard disk; non-volatile; commonly used by the operating system as virtual memory (a technique an OS uses to increase the main memory capacity beyond the RAM).

Reserving memory

• Data used by a program is stored in memory and manipulated by various data structure techniques, depending on the nature of the program.

Abstract Data Type (ADT)

• It is a keyword of a programming language that specifies the amount of memory needed to store data and the kind of data that will be stored in that memory location.

Algorithm

• is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output.

Priori Analysis

• This is a theoretical analysis of an 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.

Posterior Analysis

• This is an empirical analysis of an algorithm. The selected algorithm is implemented using a programming language. This is then executed on the target computer In this analysis, actual statistics like running time and space required, are collected.

Space Complexity

an algorithm represents the amount of memory space required by the algorithm in its life cycle.

Time Complexity

• an algorithm represents the amount of time required by the algorithm to run to completion.

Asymtotic Analysis

An algorithm refers to defining the mathematical foundation/framing of its run-time performance.

O Notation

• It measures the worst-case time complexity or the longest amount of time an algorithm can possibly take to complete.

Omega notation

• It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete.

Theta

• way to express both the lower bound and the upper bound of an algorithm's running time. 

Array

a collection of items stored in contiguous memory locations. The idea is to store multiple items of the same type together.

Arraylist

 a part of collection framework and is present in java.util package.  It provides a dynamic way of manipulating data

Arraylist()

• used to build an empty arraylist 

Arraylist(Collection C)

• Used to build an array list initialized with the elements

Arraylist(Int capacity)

• Used to build an array list with initial capacity being specified. 

Stack

a way to group things together by placing one thing on top of another and then removing things one at a time from the top of the stack.

L I F O

Last in, First Out

Push

• operation adds to the top of the list, hiding any items already on the stack, or initializing the stack if it is empty. 

Pop

• operation removes an item from the top of the list and returns this value to the caller. A pop either reveals previously concealed items or results in an empty list.

Push()

• operation is used both to initialize the stack and to store values to it. It is responsible for inserting (copying) the value into the array and for incrementing the element counter (size).

Pop()

• operation is responsible for removing a value from the stack, and decrementing the value of size. 

Size()

operation is an operation to determine the size (number of items) of

Peek()

• operation is a method that looks at the item at the top of a stack. 

Search()

• is a method that returns the position (in number) of an item from the top of a stack. 

Empty()

 is a method that tests if a stack object is empty or not.

Infix Expression

• <Operand><Operator><Operand>

Postfix expression

<Operand><Operator><Operand>