Unit I Data structure and algorithms notes

data structure

1. Data Structures
and Algorithm
INSTRUCTOR:
ELLEN GRACE
PORRAS
FIRST SEMESTER 2022-2023

2. Introduction
Data Structure
•DataStructureisawayofcollectingandorganizingdatainsuchawaythatwecan
performoperationsonthesedatainaneffectiveway.DataStructuresisaboutrendering
dataelementsintermsofsomerelationship,forbetterorganizationandstorage.
•DataStructuresarestructuresprogrammedtostoreordereddata,sothatvariousoperations
canbeperformedoniteasily.Itrepresentstheknowledgeofdatatobeorganizedin
memory.
•Itshouldbedesignedandimplementedinsuchawaythatitreducesthecomplexityand
increasestheefficiency.

3. Characteristics of a Data Structure
3
•Correctness− Data structure implementation should implement its interface correctly.
•TimeComplexity− Running time or the execution time of operations of data structure
must be as small as possible.
•SpaceComplexity− Memory usage of a data structure operation should be as little as
possible.

4. Need for Data Structure
4
As applications are getting complex and data rich, there are three common problems that applications face
now-a-days.
•DataSearch−Consideraninventoryof1million(106)itemsofastore.Iftheapplicationisto
searchanitem,ithastosearchanitemin1million(106)itemseverytimeslowingdownthe
search.Asdatagrows,searchwillbecomeslower.
•ProcessorSpeed−Processorspeedalthoughbeingveryhigh,fallslimitedifthedatagrowsto
billionrecords.
•MultipleRequests−asthousandsofuserscansearchdatasimultaneouslyonawebserver,even
thefastserverfailswhilesearchingthedata.
Tosolvetheabove-mentionedproblems,datastructurescometorescue.Datacanbeorganizedinadata
structureinsuchawaythatallitemsmaynotberequiredtobesearched,andtherequireddatacanbe
searchedalmostinstantly

5. What is an Algorithm?
5
•Algorithmisastep-by-stepprocedure,whichdefinesasetofinstructionstobeexecutedina
certainordertogetthedesiredoutput.Algorithmsaregenerallycreatedindependentof
underlyinglanguages,i.e.analgorithmcanbeimplementedinmorethanoneprogramming
language.
•Incomputerprogrammingterms,analgorithmisasetofwell-definedinstructionstosolvea
particularproblem.Ittakesasetofinput(s)andproducesthedesiredoutput.
Forexample:
Analgorithmtoaddtwonumbers:
•Taketwonumberinputs
•Addnumbersusingthe+operator
•Displaytheresult

6. 6
Letusconsidertheproblemofpreparinganomelette.Toprepareanomelette,wefollowthesteps
givenbelow:
1) Get the frying pan.
2) Get the oil.
a. Do we have oil?
•Ifyes,putitinthepan.
•Ifno,dowewanttobuyoil?
Ifyes,thengooutandbuy.
Ifno,wecanterminate.
3)Turn on the stove, etc...
Whatwearedoingis,foragivenproblem(preparinganomelette),weareprovidingastep-bystep
procedureforsolvingit.Theformaldefinitionofanalgorithmcanbestatedas:Analgorithmisthe
step-by-stepunambiguousinstructionstosolveagivenproblem.

7. Qualities of a Good Algorithm
7
•Inputandoutputshouldbedefinedprecisely.
•Eachstepinthealgorithmshouldbeclearandunambiguous.
•Algorithmsshouldbemosteffectiveamongmanywaystosolveaproblem.
•Analgorithmshouldn'tincludecomputercode.Instead,thealgorithmshouldbewrittenin
suchawaythatitcanbeusedindifferentprogramminglanguages.

8. 8
Fromthedatastructurepointofview,followingaresomeimportantcategoriesofalgorithms−
•Search−Algorithmtosearchaniteminadatastructure.
•Sort−Algorithmtosortitemsinacertainorder.
•Insert−Algorithmtoinsertiteminadatastructure.
•Update−Algorithmtoupdateanexistingiteminadatastructure.
•Delete−Algorithmtodeleteanexistingitemfromadatastructure.

9. Characteristics of an Algorithm
9
Not all procedures can be called an algorithm. An algorithm should have the following
characteristics −
•Unambiguous− Algorithm should be clear and unambiguous. Each of its steps (or
phases), and their inputs/outputs should be clear and must lead to only one meaning.
•Input− an algorithm should have 0 or more well-defined inputs.
•Output− an algorithm should have 1 or more well-defined outputs, and should match
the desired output.
•Finiteness− Algorithms must terminate after a finite number of steps.
•Feasibility− should be feasible with the available resources.
•Independent− an algorithm should have step-by-step directions, which should be
independent of any programming code.

10. Algorithm 1: Add two numbers entered by the user
10
Step 1: Start
Step 2: Declare variables num1, num2 and sum.
Step 3: Read values num1 and num2.
Step 4: Add num1 and num2 and assign the result to sum.
sum←num1+num2
Step 5: Display sum
Step 6: Stop

11. Algorithm 2: Find the largest number among three numbers
11
Step 1: Start
Step 2: Declare variables a,band c.
Step 3: Read variables a,band c.
Step 4: If a > b
If a > c
Display a is the largest number.
Else
Display c is the largest number.
Else
If b > c
Display b is the largest number.
Else
Display c is the greatest number.
Step 5: Stop

12. Agoodalgorithmmaintainsalevelofcorrectnesswhilebeingefficient.
Meaning,thereislittleerror,anditdoesn’ttakemuchtimetocomplete.
Anotherimportantcomponentiscomprehensibility.Wewouldn’tbeable
tousealgorithmssofrequentlyiftheycouldn’tbeunderstood.
Algorithmicandcomputationalthinkingissopervasivethatitgovernsthe
simplestthingsinourdailylives.Herearesomeexamplesofalgorithms
youinteractwitheveryday.
12

13. Recipes
Justlikesortingpapersandeventyingyourshoes,followingarecipeisatypeof
algorithm.Thegoalofcoursebeingtocreateaduplicatedoutcome.Inorderto
completearecipe,youmustfollowagivensetofsteps.Sayyouaremakingbread.
Youneedflour,yeastandwater.Afteryouhaveyouringredients,youneedtocombine
theminacertainwaythatwillcreateapredictableoutcome,inthiscasealoafof
bread.
13

14. Asimpletaskandyetitusesalgorithmicthinking.Whenyouaresorting
officefilesoryourpersonaldocumentsyouareimplementingan
algorithm.Initsmostbasicsense,youarefollowingasetoftasksto
achieveanoutcome.Thereasonwhysortingpapersisagreatexample,is
becauseitshowsthevarietyoftasksandspecificationsalgorithmscan
use.Forinstance,youcansortyourfilesalphabetically,bywordcount,by
date,andcountlessothers.Thegoalistosimplifytheorganizational
processbyusingsmalltasks.
14
Sorting Papers

15. ACTIVITY TIME!
15

16. Write down at least 3 algorithms
you interact with everyday and
present it in front of the class.
16

17. Types of Data Structure
17
Basically,datastructuresaredividedintotwocategories:
•Lineardatastructure
•Non-linear data structure
Lineardatastructures
•Inlineardatastructures,theelementsarearrangedinsequenceoneaftertheother.Since
elementsarearrangedorder,theyareeasytoimplement.
•However, when the complexity of the program increases, the linear data structures might
not be the best choice because of operational complexities

18. 18
Popularlineardatastructuresare:
1.ArrayDataStructure
Inanarray,elementsinmemoryarearrangedincontinuousmemory.Alltheelementsofanarray
areofthesametype.Andthetypeofelementsthatcanbestoredintheformofarraysisdetermined
bytheprogramminglanguage.
An array with each element represented by an index

19. 19
2.StackDataStructure
Instackdatastructure,elementsarestoredintheLIFOprinciple.Thatis,thelastelementstoredin
astackwillberemovedfirst.
Itworksjustlikeapileofplateswherethelastplatekeptonthepilewillberemovedfirst.
In a stack, operations can be performed only from one end (top here).

20. 20
3. Queue Data Structure
Unlike stack, the queue data structure works in the FIFO principle where first element stored in the
queue will be removed first.
It works just like a queue of people in the ticket counter where first person on the queue will get the
ticket first.
In a queue, addition and removal are performed from separate ends.

21. 21
4. Linked List Data Structure
In linked list data structure, data elements are connected through a series of nodes. And each node
contains the data items and address to the next node.
A linked list

22. 22
Unlikelineardatastructures,elementsinnon-lineardatastructuresarenotinanysequence.Insteadthey
arearrangedinahierarchicalmannerwhereoneelementwillbeconnectedtooneormoreelements.
Non-lineardatastructuresarefurtherdividedintographandtree-baseddatastructures.
1.GraphDataStructure
Ingraphdatastructure,eachnodeiscalledvertexandeachvertexisconnectedtoother
verticesthroughedges.
Graph data structure example
Non-linear data structures

23. 23
2.TreesDataStructure
Likeagraph,atreeisalsoacollectionofverticesandedges.However,intreedata
structure,herecanonlybeoneedgebetweentwovertices.
Tree data structure example
Non-linear data structures

24. 24
Now that we know about linear and non-linear data structures, let's see the major differences between
them.
Linear Vs Non-linear Data Structures
LinearDataStructures Non-LinearDataStructures
The data items are arranged in sequential
order, one after the other.
The data items are arranged in non-
sequential order (hierarchical manner).
All the items are present on the single
layer.
The data items are present at different
layers.
It can be traversed on a single run. That
is, if we start from the first element, we
can traverse all the elements sequentially
in a single pass.
It requires multiple runs. That is, if we start
from the first element it might not be
possible to traverse all the elements in a
single pass.
The memory utilization is not efficient.
Different structures utilize memory in
different efficient ways depending on the
need.
The time complexity increases with the
data size.
Time complexity remains the same.
Example: Arrays, Stack, Queue Example: Tree, Graph, Map

25. Thank you
Presenter name: Ellen Grace D. Porras
Email address: [email protected]