Lecture notes on Data Structures

what is data structures and algorithms and lecture notes for data structures and algorithms
AustinCraig Profile Pic
AustinCraig,Germany,Professional
Published Date:09-07-2017
Your Website URL(Optional)
Comment
TheNeedforDataStructures Aprimaryconcernofthiscourseiseciency. Datastructuresorganizedata )moreecientprograms.Youmight believethatfastercomputersmakeitunnecessarytobe COURSENOTES concernedwitheciency.However... More powerfulcomputers)morecomplex CS2604: applications. DataStructuresandFileProcessing Morecomplexapplicationsdemandmore JavaEdition calculations. CliordA.Shaer Complexcomputingtasksareunlikeour everydayexperience.Soweneedspecial DepartmentofComputerScience VirginiaTechtraining c Copyright 1998 Anyorganizationforacollectionofrecordscan besearched,processedinanyorder,or modied.Ifyouarewillingtopayenoughintimedelay. Ex:Simpleunorderedarrayofrecords. Thechoiceofdatastructureandalgorithm canmakethedierence betweenaprogram runninginafewsecondsormanydays. 1EciencySelectingaDataStructure Asolutionissaidto beecient ifitsolvestheSelectadatastructureasfollows: problemwithinitsresourceconstraints.Alt: 1.Analyzetheproblemtodeterminethe Betterthanknownalternatives(\relatively"ecient) resourceconstraintsasolutionmustmeet. spaceThesearetypicalcontraintsforprograms 2.Determinethebasicoperationsthatmust time besupported.Quantifytheresource constraintsforeachoperation. Thisdoesnotmeanalwaysstriveforthemostecient program.Iftheprogramoperateswellwithinresource 3.Selectthedatastructurethatbestmeets constraints,thereisnobenettomakingitfasterorsmaller. theserequirements. Thecostofasolutionistheamountof Typicallywantthe\simplest"datastruturethatwillmeet resourcesthatthesolutionconsumes. requirements. Somequestionstoask:Thesequestionsoftenhelp tonarrowthepossibilities Arealldatainsertedintothedatastructure atthebeginning,orareinsertions interspersedwithotheroperations? Candata bedeleted?Ifso,amorecomplex representationistypicallyrequired Arealldataprocessedinsomewell-dened order,orisrandomaccessallowed? 23DataStructurePhilosophy GoalsofthisCourse Eachdatastructurehascostsandbenets. 1.Reinforcetheconceptthattherearecosts andbenetsforeverydatastructure.A Rarelyisonedatastructurebetterthan worldviewtoadopt anotherinallsituations. 2.Learnthecommonlyuseddatastructures. Adatastructurerequires: Theseformaprogrammer’sbasicdata spaceforeachdataitemitstores,Data+ structure\toolkit."The\nutsandbolts"ofthe Overhead course timetoperformeachbasicoperation, 3.Understandhowtomeasurethe programmingeort.Somedata eectivenessofadatastructureor structures/algorithmsmorecomplicatedthanothers program. Thesetechniquesalsoallowyoutojudge Eachproblemhasconstraintsonavailable themeritsofnewdatastructuresthat spaceandtime. youorothersmightinvent.Toprepare Onlyafteracarefulanalysisofproblemyouforthefuture characteristicscanweknowthebestdata structureforthetask. Bankexample: Startaccount:afewminutes Transactions:afewseconds Closeaccount:overnight 45Denitions AbstractDataTypes (ADT):adenitionfora AbstractDataType Atype isasetofvalues. datatypesolelyintermsofasetofvaluesand Ex:Integer,Boolean,Float asetofoperationsonthatdatatype. Adatatypeisatypeandacollectionof EachADToperationisdenedbyitsinputs operationsthatmanipulatethetype. andoutputs. Ex:Addition Encapsulation:hideimplementationdetails Adataitemorelementisapieceof informationorarecord. Adatastructureisthephysical implementationofanADT. Physicalinstantiation EachoperationassociatedwiththeADTis Adataitemissaidto be amemberofadata implementedbyoneormoresubroutinesin type. theimplementation. Datastructureusuallyreferstoan Asimpledataitemcontainsnosubparts. organizationfordatainmainmemory. Ex:Integer Filestructure:anorganizationfordataon Anaggregatedataitemmaycontainseveral peripheralstorage,suchasadiskdriveortape. piecesofinformation. AnADTmanagescomplexitythrough Ex:Payrollrecord,citydatabaserecord abstraction:metaphor.Hierarchiesoflabels Ex:transistorsgatesCPU.Inaprogram,implementan ADT,thenthinkonlyabouttheADT,notitsimplementation 67 Logicalvs.PhysicalForm Problems Dataitemshavebothalogical andaphysicalProblem:ataskto beperformed. form. Bestthoughtofasinputsandmatching outputs. Logicalform:denitionofthedataitemwithin Problemdenitionshouldinclude anADT.Ex:Integersinmathematicalsense:+,− constraintsontheresourcesthatmay be consumedbyanyacceptablesolution.But Physicalform:implementationofthedataitem NOconstraintsonHOWtheproblemissolved withinadatastructure.16/32bitintegers:overow Problems,mathematicalfunctions DataType Afunctionisamatching betweeninputs (thedomain)andoutputs(therange). ADT: Aninputtoafunctionmay besingle DataItems: Type number,oracollectionofinformation. LogicalForm Operations Thevaluesmakingupaninputarecalled theparameters ofthefunction. Aparticularinputmustalwaysresultinthe DataStructure: sameoutputeverytimethefunctionis DataItems: StorageSpace computed. PhysicalForm Subroutines Inthisclass,wefrequentlymoveaboveandbelow\theline" separatinglogicalandphysicalforms. 89AlgorithmsandPrograms MathematicalBackground LookoverChapter2,readasneededdependingonyour Algorithm:amethodoraprocessfollowedto familiaritywiththismaterial. solveaproblem.Arecipe SetconceptsandnotationSethasnoduplicates, sequencemay Analgorithmtakestheinputtoaproblem Recursion (function)andtransformsittotheoutput.A mappingofinputtooutput Inductionproofs Aproblemcanhavemanyalgorithms. LogarithmsAlmostalwaysuselogtobase2.Thatisour Analgorithmpossessesthefollowingproperties: defaultbase. 1.Itmust becorrect.Computesproperfunction Summations 2.Itmust becomposedofaseriesof concretesteps.Executablebythatmachine 3.Therecan benoambiguityastowhich stepwill beperformednext. 4.Itmust becomposedofanitenumberof steps. 5.Itmustterminate. Acomputerprogram isaninstance,or concreterepresentation,foranalgorithmin someprogramminglanguage. Wefrequentlyinterchangeuseof\algorithm"and\program" thoughtheyareactuallydierentconcepts 1011EstimationTechniques AlgorithmEciency Knownas\backoftheenvelope"or\backof Thereareoftenmanyapproaches(algorithms) thenapkin"calculation.tosolveaproblem.Howdowechoosebetween them? 1.Determinethemajorparametersthataect theproblem. Attheheartofcomputerprogramdesignare 2.Deriveanequationthatrelatesthe two(sometimesconicting)goals: parameterstotheproblem. 1.Todesignanalgorithmthatiseasyto 3.Selectvaluesfortheparameters,andapply understand,codeanddebug. theequationtoyieldanestimatedsolution. 2.Todesignanalgorithmthatmakesecient useofthecomputer’sresources. Example: Howmanylibrary bookcasesdoesittaketo Goal(1)istheconcernofSoftware storebookstotalingonemillionpages? Engineering. Estimate: Goal(2)istheconcernofdatastructuresand pages/inchguess500 algorithmanalysis. feet/shelfguess4(actually,3) Whengoal(2)isimportant,howdowe shelves/bookcaseguess5(actually,7) measureanalgorithm’scost? Unitscheck:pages/inft/shelfshelf/bkcase) pages/bkcase 1213HowtoMeasureEciency? ExamplesofGrowthRate Example1:As ngrows,howdoesT(n)grow? 1.Empiricalcomparison(runprograms). static int largest(int array) // Find largest val Diculttodo\fairly."Timeconsuming. int currLargest = 0; // Store largest val 2.AsymptoticAlgorithmAnalysis. for (int i=0; iarray.length; i++) // For each elem if (arrayi currLargest) // if largest currLargest = arrayi; // remember it Criticalresources: return currLargest; // Return largest val Time.Space(disk,RAM).Programmer’seort.Easeofuse (user’seort). Cost: T(n)=cn +csteps 1 2 Example2:AssignmentstatementConstantcost Example3: Factorsaectingrunningtime: sum = 0; for (i=1; i=n; i++) Machineload.OS.Compiler.Problemsize.Specicinput for (j=1; j=n; j++) valuesforgivenproblemsize. sum++; 222 Cost: T(n)=cn +cRoughly nsteps,withsumbeing nat 1 2 theend.Ignorevariousoverheadsuchasloopcounter increments. Formostalgorithms,runningtimedependson \size"oftheinput. Runningtimeisexpressedas T(n)forsome function Toninputsize n. 1415GrowthRateGraph Best,WorstandAverageCases n 2isanexponentialalgorithm.10nand20ndieronlyb ya constant. Notallinputsofagivensizetakethesame n2 22n5nlogn 1400 time. 1200 Sequentialsearchfor Kinanarrayof n 20n 1000 integers: 800 Beginatrstelementinarrayandlookat eachelementinturnuntil Kisfound. 600 10n 400 BestCase:Findatrstposition:1compare 200 WorstCase:Findatlastposition: ncompares 0 1020304050 0 AverageCase:(n +1)=2compares n2 22n Whileaveragetimeseemsto bethefairest 400 measure,itmay bediculttodetermine. 20n 300 Dependsondistribution.Assumptionforaboveanalysis: Equallylikelyatanyposition. 5nlogn Whenisworstcasetimeimportant? 200 Realtimealgorithms 10n 100 0 051015 1617 InputsizenFasterComputerorAlgorithm? AsymptoticAnalysis:Big-oh Whathappenswhenwebuyacomputer10 Denition:For T(n)anon-negativelyvalued timesfaster?Howmuchspeedup?10times.Morefunction, T(n)isinthesetO(f(n))ifthere important:Howmuchincreaseinproblemsizeforsametime?existtwopositiveconstants cand nsuchthat 0 Dependsongrowthrate. T(n)cf(n)forallnn. 0 0 0 T(n) n nChange n=n 2 Usage:ThealgorithmisinO(n)inbest, 0 10n1;00010;000 n =10n10 average,worstcase. 0 20n5005;000 n =10n10 p Meaning:Foralldatasetsbigenough(i.e., 0 5nlogn2501;84210nn10n7:37 p nn),thealgorithmalwaysexecutesinless 0 2 0 2 n70223 n=10n3:16 than cf(n)stepsinbest,averageorworst n 0 21316 n=n +3 −− case. 2 0 For n ,ifn=1000,then nwouldbe1003 Mustpickoneofthesetocompletethestatement.Big-oh n:Sizeofinputthatcan be processedinone notationappliestosomesetofinputs. hour(10,000steps). UpperBound. 0 n:Sizeofinputthatcan be processedinone 22 Example:if T(n)=3nthen T(n)isinO(n). houronthenewmachine(100,000steps). 2 Compare T(n)=nto T(n)=nlogn.Forn58,itisfasterto Wishtightestupperbound: 232 havethe( nlogn)algorithmthantohaveacomputerthatis While T(n)=3nisinO(n),wepreferO(n). 10timesfaster. 23 ItprovidesmoreinformationtosayO(n)thanO(n) 1819Big-ohExample Big-Omega Example1.Findingvalue Xinanarray.AverageDenition:For T(n)anon-negativelyvalued casefunction, T(n)isintheset( g(n))ifthere existtwopositiveconstants cand nsuchthat T(n)=c n=2.cisaconstant.Actualvalueisirrelevant0 s s T(n)cg(n)forallnn. 0 Forallvaluesofn1, c n=2c n. s s Therefore,bythedenition, T(n)isinO(n)for Meaning:Foralldatasetsbigenough(i.e., n =1and c=c. s 0 nn),thealgorithmalwaysexecutesinmore 0 than cg(n)steps. 2 Example2. T(n)=cn +cninaveragecase 1 2 LowerBound. 2222 c n+c nc n+c n (c+c)nforall 121212 n1. 2 Example: T(n)=cn +cn. 1 2 2 T(n)cnfor c=c+cand n =1. 2 2 120 cn +cncnforalln1. 1 2 1 2 for 2 T(n)cn c=cand n =1. 10 Therefore, T(n)isinO(n)bythedenition. 2 Therefore, T(n)isin( n)bythedenition. Example3: T(n)=c. WesaythisisinO(1). RatherthanO(c) Wantgreatestlowerbound. 2021 ThetaNotation RunningTimeofaProgram Asymptoticanalysisisdenedforequations.Needtoconvert Whenbig-Ohandmeet,weindicatethisbyprogramtoanequation. using(big-Theta)notation. a=b; Example1: Denition:Analgorithmissaidto be( h(n)) Thisassignmenttakesconstanttime,soitis ifitisinO(h(n))anditisin( h(n)). (1).Not( c)notationbytradition Forpolynomialequationson T(n),wealwayshave.There isnouncertainty,a\complete"analysis. Example2: SimplifyingRules: sum = 0; for (i=1; i=n; i++) sum += n; 1.If f(n)isinO(g(n))and g(n)isinO(h(n)), 2 ) then f(n)isinO(h(n)).( n)(eventhoughsumis n 2.If f(n)isinO(kg(n))foranyconstant Example3: k0,then f(n)isinO(g(n)).Noconstant sum = 0; 3.If f(n)isinO(g(n))and f(n)isin 112 for (j=1; j=n; j++) // First for loop O(g(n)),then(f+f)(n)isin for (i=1; i=j; i++) // is a double loop 212 sum++; O(max(g(n), g(n))).Droploworderterms 12 for (k=0; kn; k++) // Second for loop Ak = k; 4.If f(n)isinO(g(n))and f(n)isin 112 P O(g(n))then f(n)f(n)isin 2 212Firststatementis(1).Doubleforloop isi =(n ).Final O(g(n)g(n)).Loops2 12 forloop is( n).Result:( n). 2223MoreExamples BinarySearch Example4. Position0123456789101112131415 sum1 = 0; Key11132126293640414551545665727783 for (i=1; i=n; i++) // First double loop for (j=1; j=n; j++) // do n times sum1++; sum2 = 0; for (i=1; i=n; i++) // Second double loop static int binary(int K, int array, for (j=1; j=i; j++) // do i times int left, int right) sum2++; // Return position in array (if any) with value K 2 int l = left-1; Firstloop,sumis n.Secondloop,sumis(n+1)(n)=2.Both int r = right+1; // l and r are beyond array bounds 2 are( n). while (l+1 = r) // Stop when l and r meet Example5. int i = (l+r)/2; // Look at middle of subarray if (K arrayi) r = i; // In left half sum1 = 0; if (K == arrayi) return i; // Found it for (k=1; k=n; k=2) if (K arrayi) l = i; // In right half for (j=1; j=n; j++) sum1++; return UNSUCCESSFUL; // Search value not in array sum2 = 0; for (k=1; k=n; k=2) for (j=1; j=k; j++) sum2++;Analysis:Howmanyelementscan beexamined P P lognlogn−1intheworstcase?(log n) k Firstis n =(nlogn).Secondis2 =(n). k=1 k=0 2425 OtherControlStatementsAnalyzingProblems Typicallydoalotofthisinasenioralgorithmscourse. whileloop:analyzelikea forloop. Upperbound:Upperboundofbestknown algorithm. ifstatement:Takegreatercomplexityof then/elseclauses. Lowerbound:Lowerboundforeverypossible algorithm. Ifprobabilitiesareindependentof n. Theexamplessofarhavebeeneasyinthatexactequations switchstatement:Takecomplexityofmost alwaysyield.Thus,itwashardtodistinguishandO. expensivecase. Followingexampleshouldhelptoexplainthedierence Ifprobabilitiesareindependentof n. boundsareusedtodescribeourlevelofuncertaintyaboutan Subroutinecall:Complexityofthesubroutine. algorithm. Example:Sorting 1.CostofI/O:( n) 2 2.Bubbleorinsertionsort:O(n) 3.Abettersort(Quicksort,Mergesort, Heapsort,etc.):O(nlogn) 4.Weprovelaterthatsortingis( nlogn) 2627MultipleParametersSpaceBounds Ex:256colors(8bits),10001000pixels Spaceboundscanalso beanalyzedwith Computetherankorderingforall Cpixel asymptoticcomplexityanalysis. valuesinapictureof Ppixels. Time:Algorithm for (i=0; iC; i++) // Initialize count counti = 0; Space:DataStructure for (i=0; iP; i++) // Look at all of the pixels countvalue(i)++; // Increment proper value count Space/TimeTradeoPrinciple: sort(count); // Sort pixel value counts Onecanoftenachieveareductionintimeis oneiswillingtosacricespace,orviceversa. Ifweuse Pasthemeasure,thentimeis Encodingorpackinginformation ( PlogP). Booleanags Tablelookup Moreaccurateis( P+ClogC). Factorials DiskBasedSpace/TimeTradeoPrinciple: Thesmalleryoucanmakeyourdiskstorage requirements,thefasteryourprogramwillrun. 2829Lists ListADT Studentsshouldalreadybefamiliarwithlists.Objectives:use alganalysisinfamiliarcontext,compareimplementations. interface List // List ADT public void clear(); // Remove all Objects Alistisanite,orderedsequenceofdata public void insert(Object item); // Insert at curr pos itemscalledelements. public void append(Object item); // Insert at tail public Object remove(); // Remove/return curr Thepositionsareordered,NOTthevalues. public void setFirst(); // Set to first pos Eachlistelementhasadatatype. public void next(); // Move to next pos public void prev(); // Move to prev pos public int length(); // Return curr length Theemptylistcontainsnoelements. public void setPos(int pos); // Set curr position public void setValue(Object val); // Set current value Thelengthofthelististhenumberof public Object currValue(); // Return curr value elementscurrentlystored. public boolean isEmpty(); // True if empty list public boolean isInList(); // True if in list public void print(); // Print all elements Thebeginningofthelistiscalledthehead, // interface List theendofthelistiscalledthetail. ThisisanexampleofaJavainterface.AnyJavaclassusing thisinterfacemustimplementallofthesefunctions.Note Sortedlistshavetheirelementspositionedin thatthegenerictype\Object"isbeingusedfortheelement ascendingorderofvalue,whileunsortedlists type. havenonecessaryrelationship betweenelement valuesandpositions. Notation:( a;a ; :::; a) 01 n−1 Whatoperationsshouldweimplement? Add/deleteelemanywhere,nd,next,prev,testforempty. 3031ListADTExamples Array-BasedListInsert List:(12 ;32;15) Pushitemsup/down.Cost:( n). MyLst.insert(element); Insert23: Theaboveisanexampleuseoftheinsertfunction. \element"isanobjectofthelistelementdatatype. 1312208313122083 Assume MyPoshas32ascurrentelement: 012345012345 MyLst.insert(99);(a)(b) Put99beforecurrentelement,yielding(12,99,32,15). 2313122083 Processanentirelist: 012345 (c) for (MyLst.setFirst(); MyLst.isInList(); MyLst.next()) DoSomething(MyLst.currValue()); 3233Array-BasedListClass Array-BasedListClass(cont) public void append(Object it) // Insert at tail class AList implements List // Array-based list Assert.notFalse(numInList msize, "List is full"); listArraynumInList++ = it; // Increment list size private static final int defaultSize = 10; private int msize; // Maximum size of list public Object remove() // Remove and return Object private int numInList; // Actual list size Assert.notFalse(isEmpty(), "No delete: list empty"); private int curr; // Position of curr Assert.notFalse(isInList(), "No current element"); private Object listArray; // Array holding list Object it = listArraycurr; // Hold removed Object for(int i=curr; inumInList-1; i++) // Shift down AList() setup(defaultSize); // Constructor listArrayi = listArrayi+1; AList(int sz) setup(sz); // Constructor numInList; // Decrement list size return it; private void setup(int sz) // Do initializations msize = sz; numInList = curr = 0; public void setFirst() curr = 0; // Set to first listArray = new Objectsz; // Create listArray public void prev() curr; // Move curr to prev public void next() curr++; // Move curr to next public int length() return numInList; public void clear() // Remove all Objects from list public void setPos(int pos) curr = pos; numInList = curr = 0; // Simply reinitialize values public boolean isEmpty() return numInList == 0; public void insert(Object it) // Insert at curr pos public void setValue(Object it) // Set current value Assert.notFalse(numInList msize, "List is full"); Assert.notFalse(isInList(), "No current element"); Assert.notFalse((curr =0) && (curr = numInList), listArraycurr = it; "Bad value for curr"); for (int i=numInList; icurr; i) // Shift up listArrayi = listArrayi-1; public boolean isInList() // True if curr within list listArraycurr = it; return (curr = 0) && (curr numInList); numInList++; // Increment list size // Array-based list implementation 3435LinkClass LinkedListPosition Dynamicallocationofnewlistelements.headcurrtail 20231215 class Link // A singly linked list node private Object element; // Object for this node (a) private Link next; // Pointer to next node Link(Object it, Link nextval) // Constructor headcurrtail element = it; next = nextval; Link(Link nextval) next = nextval; // Constructor 2023101215 Link next() return next; Naiveapproach:Pointtocurrentnode.Currentis12.Want Link setNext(Link nextval) return next = nextval; (b) Object element() return element; toinsertnodewith10.Noaccessavailabletonodewith23. Object setElement(Object it) return element = it; Howcanwedotheinsert? headcurrtail 20231215 (a) headcurrtail 2023101215 (b) Altimplementation:Pointtonodeprecedingactualcurrent node.Nowwecandotheinsert.Alsonoteuseofheader node. 3637LinkedListImplementation LinkedListInsertion public class LList implements List // Linked list private Link head; // Pointer to list header private Link tail; // Pointer to last Object in list // Insert Object at current position protected Link curr; // Position of current Object public void insert(Object it) Assert.notNull(curr, "No current element"); LList(int sz) setup(); // Constructor curr.setNext(new Link(it, curr.next())); LList() setup(); // Constructor if (tail == curr) // Appended new Object private void setup() tail = curr.next(); tail = head = curr = new Link(null); public void setFirst() curr = head; curr public void next() if (curr = null) curr = curr.next(); ...... 2312 public void prev() // Move to previous position Link temp = head; Insert10:10 if ((curr == null) (curr == head)) // No prev curr = null; return; // so return (a) while ((temp = null) && (temp.next() = curr)) curr temp = temp.next(); curr = temp; ...... 2312 3 public Object currValue() // Return current Object 10 if (isInList()) return null; 12 return curr.next().element(); (b) public boolean isEmpty() // True if list is empty return head.next() == null; // Linked list class 3839

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.