[PDF] Notes 2: Introduction to data structures PDF notes2.pdf

Notes 2: Introduction to data structures 2 1 Recursion 2 1 1 Recursive functions Recursion is a central concept in computation in which the solution of a

24 nov 2015 · Array, Stacks, linked list, queue Eg tree, graph Implementation is easy Implementation is difficult Operation on Data Structures

[PDF] Data Structures and Algorithms - School of Computer Science

Introduction These lecture notes cover the key ideas involved in designing algorithms We shall see how they depend on the design of suitable data structures,

[PDF] Basics of Data Structures Introduction to Data Structures

Data Structure is an arrangement of data in a computer's memory (or sometimes on a disk) Data structures include arrays, linked lists, stacks, binary trees, and

[PDF] Data Structures Lecture 1: Introduction - Everything Computer Science

What is a Data Structure Anyway? What kind of operations should your data structure(s) support? http://www cs umd edu/~mount/420/Lects/420lects pdf

[PDF] Introduction to Data Structures and Algorithms

Overview on simple data structures Typical Examples of Elementary Data Structures i e a certain data structure is a stack if the respective axioms hold

[PDF] Basic Introduction into Algorithms and Data Structures

As fundamental data structures, we in- troduce linked lists, trees and graphs Implementations are given in the programming language C Contents 1 Introduction

[PDF] A Practical Introduction to Data Structures and Algorithm Analysis

3 jan 2011 · Steven S Skiena's The Algorithm Design Manual [Ski98] pro- vides pointers to many implementations for data structures and algorithms that

[PDF] LECTURE NOTES ON DATA STRUCTURES - IARE

Y Daniel Liang, “Introduction to Programming using Python”, Pearson 2 Benjamin Baka, David Julian, “Python Data Structures and Algorithms”, Packt Publishers,

[PDF] Notes 2: Introduction to data structures

Notes 2: Introduction to data structures 2 1 Recursion 2 1 1 Recursive functions Recursion is a central concept in computation in which the solution of a

[PDF] Data Structures and Algorithms Using Python

We do this by placing the focus on the data structures and algorithms, while designing the examples to allow the introduction of object-oriented programming if

Notes2:Introductiontodatastructures

2.1Recursion

2.1.1Recursivefunctions

ofthesameproblem.Recursionisaconceptuallydifferentapproachtothinkingaboutnumericalalgorithms. Itstandsin

usuallyconsistsofoneormorerecursivecases(valuesofthe inputsforwhichthefunctioncallsitself)and oneormore

so-calledbasecases(valuesofthe inputsforwhichthefunctionreturnsaresultstriviallywithoutrecurring).Animportant

intf(intn) if (n == 0) // Base case {return1; else {returnn*f(n-1);//Recursivecase Ifyou haveneverencounteredtheconceptofarecursivefunctionbefore,ittakessomethoughttoseethatf(n)=n!. Onewaytounderstandwhatishappeningistowriteout thesetoffunctionexecutionswhichoccurwhenthefunctionis

called.Consider, forexamplewhenwecalculatef(4).Usingbracketstokeeptrackofthelevelsoftherecursionwehave

f(4) = 4 *f(3) //Input3callsrecursivecase = 4 *(3*(f(2))//Input2callsrecursivecase = 4 *(3*(2*f(1))//Input1callsrecursivecase = 4 *(3*(2*(1*f(0))))//Input0callsbase casereturning1 = 4 *(3*(2*(1*1))) //Multiplications nowgo frominside the out = 4 *(3*(2*1)) = 4 *(3*2) = 4 *6 = 24

ducedinSecs.1.2and1.3.Recursionisthenaturalframeworkforthinkingaboutdivide-and-conqueralgorithms. IfF(n)

representsthenumberofFLOPsrequiredtosolve aproblemofsizen,wehaveseenthatfordivide-and-conqueralgo- 12

MA934NumericalMethodsNotes2

inta = 6; //Defineanintaand set itsvalueto be 6 int *ptr=NULL;//Defineapointerptr and set itsvalueto be NULL ptr=&a;//Set ptrtopointto a cout << *ptr<2.2.3Linkedlists

Insomerespectsalinkedlistsislike aconventionallineararrayinthesensethat isstoresasequenceofdataobjects.

elements.Thisisbecausethelistelementsdonotneedtobestored contiguouslyinmemory. implementedaslineararrays.

Therearesomedisadvantagestoo:

•Thebiggestdisadvantageis thatlinkedlistsonlyprovidesequentialaccesstolistelements.Togettonodeirequires

arraytostoreanequivalentamountofdata.

Notes2:Introductiontodatastructures

MA934NumericalMethodsNotes2

classList intn; //Thedata is just anint List *next;//Pointertothenext node inthelist Wecanaddtothisclassamethodwhich,givenapointertoalistand aninteger,insertsanewitemattheheadofthe List *List::insertHead(List*list,intN) List *new_node =newList();//Createanewnode to bethe newhead new_node->n= N; //Assign thedata tothe newnode if(list!=NULL) {new_node->next=list;//Newnodepointstotheprevious list returnnew_node;//Returnapointertothe newlist

pointertoalistand aninteger,insertsanewitematthetailofthelistandthenreturnsapointertothemodifiedlist.One

waytodothisisviarecursion: List *List::insertTail(List*list,intN) if(list==NULL)// Base case List *new_node =newList();//Createanewnode new_node->n=N;//Storethedata returnnew_node;//Return the newnode else//Recursivecase {//Recurseonlist->next list->next=insertTail(list->next,N); returnlist; integerN.Thisisthecorrectanswer.

theintegerNinsertedatitsrear.Giventhisassumption,storingapointertothis Listintolist->nextandreturninglist

themselvesdefinedrecursively.Abasicimplementationoftheaboveclasscanbe downloadedfromtheclasswebsitefor

youtoplayaroundwith.

2.3Binarytrees

Notes2:Introductiontodatastructures

MA934NumericalMethodsNotes2

searchorder: class BinaryTree

Datum data;

BinaryTree*L;

BinaryTree

*R;

2.3.1Binarytreesearch

key value,k,betweenk1andkNwe wishtoreturnthedatavalueassociatedwiththekeyk.Thenaiveapproachwould (wetakethekeytobe aninteger): class BinaryTree intkey;

Datum data;

BinaryTree*L;

BinaryTree

*R;

examiningtherootnode. Ifthetreeisnull,thekeywearesearchingfordoesnotexistinthetree.Otherwise,ifthekey

equalsthatoftheroot,thesearchissuccessfulandwereturnthevalueatthatnode. Ifthekeyislessthanthatoftheroot,

isrepeateduntilthekeyisfoundortheremainingsubtreeisnull.Ifthesearchedkeyisnotfoundbeforea nullsubtreeis

Notes2:Introductiontodatastructures

MA934NumericalMethodsNotes2

BinaryTreesearch(BinaryTreeT,intk)

if (T ==NULL) {returnNULL;// base case else if(T->key== k) {returnT; else if(T->key< k) {return search(T->L, k); else if(T->key> k) {return (T->R, k); LetususeTheorem2.1.1toverifyourexpectationthatbinarytreesearchshouldbe an(O(log(N))operation. ofhalfthesize.Mathematically

F(n)=F?n

2? +4, thereforeincase2andF(n)=O(log(n)). x

iisarealnumberandeachkiisaninteger.Intheapplicationtostochasticsimulation,wehave alistofpossibleevents

whichcanoccurinthesystemlabelledk1,...,kNand anassociatedlistofratesx1,...,xN,atwhichtheseevents {si:i=0,1...N}wheresi=i? j=1x j, (wetakes0=0).Thecomputationalchallengeisthefollowing:givena numberx?(0,sN],canweefficientlyfindi O(N)comparisions. Infactwecan usetheideasofSec.2.3.1todesignadatastructurewhichcansolvethisproblemin

SuchastructureiscalledaFenwicktree. Ifweleaveasidethequestionofhowtobuildthetreestartingfromtheinitial

Notes2:Introductiontodatastructures

MA934NumericalMethodsNotes2

if(T->L==NULL&&T->R==NULL) { // Basecase:we havereacheda leafnode.Return thedatastoredthere returnT->data; else //Recursivecase:decidewhetherto go left orright. doubley=(T->L->data).x;//Get the sumoftheleftchild if(x <= y) { //Searchleftchild return search(T->L, x); else { //Searchright child return search(T->R,x-y); mentsofsearchonaFenwicktreecomparedtonaivelinearsearch.Ifyou havenotusedbinarysearchalgorithmsinyour

Notes2:Introductiontodatastructures

MA934NumericalMethodsNotes2

simulationsis thatonceatreehasbeenbuilt,theoperationsofinsertion,deletionandupdatingofnodescanalsobe done

Thesearemorespecialisetopicswhichwewillnotcoverinthiscoursebutitisgoodtobeawareofthemifyou end up usingthesemethodsinyourresearch.

Bibliography

m19w03/public_html/book.html,2003. [2]J.L.Blue, I.Beichl,andF.Sullivan.Fastermontecarlosimulations.Phys.Rev.E,51(2):R867-R868,1995.

Notes2:Introductiontodatastructures

quotesdbs_dbs20.pdfusesText_26

[PDF] [PDF] Notes 2: Introduction to data structures

Notes2:Introductiontodatastructures

2.1Recursion

2.1.1Recursivefunctions

MA934NumericalMethodsNotes2

Therearesomedisadvantagestoo:

Notes2:Introductiontodatastructures

MA934NumericalMethodsNotes2

2.3Binarytrees

Notes2:Introductiontodatastructures

MA934NumericalMethodsNotes2

Datum data;

BinaryTree*L;

BinaryTree

2.3.1Binarytreesearch

Datum data;

BinaryTree*L;

BinaryTree

Notes2:Introductiontodatastructures

MA934NumericalMethodsNotes2

BinaryTree*search(BinaryTree*T,intk)

F(n)=F?n

Notes2:Introductiontodatastructures

MA934NumericalMethodsNotes2

Notes2:Introductiontodatastructures

MA934NumericalMethodsNotes2

Bibliography

Notes2:Introductiontodatastructures

BinaryTreesearch(BinaryTreeT,intk)