Basic concepts of data structures and algorithms

Data Structures and Algorithms

1. Basic Conceptsof
Data Structures and Algorithms
New Wave Analytica
We Find Solutions in Data

2. Outline
•What is Data Structures?
•Classification of Data Structure According to Type, Elements, Size and Relationship
•Whatisan Abstract Data Type?
•Abstract Data Type Groups
•Algorithm
•Basic Categories of Algorithm
•AlgorithmAnalysis
•Asymptotic analysis
New Wave Analytica

3. What is Data Structure?
•Incomputerscience,adatastructureisaparticularwayofstoringandorganizing
datainacomputersothatitcanbeusedefficiently.
•DataStructuresaregenerallybasedontheabilityofacomputertofetch(retrieve)
andstoredataatanyplaceinitsmemory,specifiedbyanaddress–abitstringthat
canbeitselfstoredinmemoryandmanipulatedbytheprogram.
New Wave Analytica

4. Classification of
Data Structure According to Type
•Primitive–these are basic data structures and are directly operated upon machine
instructions, e.g., integer, character.
•Non-primitive–these are derived from primitive data structures, e.g., array.
New Wave Analytica

5. Classification of
Data Structure According to Elements
•Homogeneous–in this data structure, all elements are of the same type, e.g. array.
•Heterogeneous–in this data structure, elements are of different types, e.g., structure.
New Wave Analytica

6. Classification of
Data Structure According to Size
•Static–the size of this data structure cannot be changed after the initial allocation, like
matrices.
•Dynamic–the size can change dynamically, like in lists.
New Wave Analytica

7. Classification of
Data Structure According to Relationship
•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.
New Wave Analytica

8. What is an Abstract Data Types?
•Itisakeywordofaprogramminglanguagethatspecifiestheamountofmemory
neededtostoredataandthekindofdatathatwillbestoredinthatmemory
location.
•ThenumberofbytesreservedforanADTvaries,dependingontheprogramming
languageusedtowritetheprogramandthetypeofcomputerusedtocompilethe
program.
New Wave Analytica

9. Abstract Data Type Groups
•Integer
•Floating-point
•Character
•Boolean
New Wave Analytica

10. Algorithm
•Analgorithmisastep-by-stepprocedure,whichdefinesasetofinstructionstobe
executedinacertainordertogetthedesiredoutput.Algorithmsaregenerallycreated
independentofunderlyinglanguages,i.e.analgorithmcanbeimplementedinmore
thanoneprogramminglanguage.
New Wave Analytica

11. Basic Categories of Algorithm
•Search− Algorithm to search an item in a data structure.
•Sort− Algorithm to sort items in a certain order.
•Insert− Algorithm to insert an item in a data structure.
•Update− Algorithm to update an existing item in a data structure.
•Delete− Algorithm to delete an existing item from a data structure.
New Wave Analytica

12. Algorithm Analysis
Theefficiencyofanalgorithmcanbeanalyzedattwodifferentstages,before
implementation,andafterimplementation.Theyarethefollowing
•APrioriAnalysis−ThisisatheoreticalanalysisofanEfficiencyofanalgorithmismeasured
byassumingthatallotherfactors,forexample,processorspeed,areconstantandhaveno
effectontheimplementation.
•APosteriorAnalysis−Thisisanempiricalanalysisofanalgorithm.Theselectedalgorithm
isimplementedusingaprogramminglanguage.ThisisthenexecutedontargetcomputerIn
thisanalysis,actualstatisticslikerunningtimeandspacerequired,arecollected.
New Wave Analytica

13. Asymptotic Analysis
•Asymptoticanalysisofanalgorithmreferstodefiningthemathematical
foundation/framingofitsrun-timeperformance.Usingasymptoticanalysis,wecanvery
wellconcludethebestcase,averagecase,andworst-casescenarioofanalgorithm.
•Thetimerequiredbyanalgorithmfallsunderthefollowingtypes:
•Best Case− Minimum time required for program
•Average Case− Average time required for program
•Worst Case− Maximum time required for program
New Wave Analytica