What is “Data Structures”?
What will I learn in this course?
Major Topic Groups
C#Languageand .NET concepts.NET Class LibraryData StructuresAlgorithmsAlgorithm Analysis
16 January 2018
What is "Data Structures"?
2
C# and .NET
C#is similar to bothJavaandC++in many waysThesyntaxis nearly identicalIf you knowJava, you can probably read and understand simpleC#programs with little trainingMajor differences between programming inC#and programming inJavaare theclasslibrariesthey use.NETclass libraryprovides support forC#(and other.NETlanguages such asVisual Basic,F#,IronPython, and evenC++.NET)Javais supported byAWT,Swingand other libraries in addition to the standardJavaAPI libraries
16 January 2018
What is "Data Structures"?
3
Why Learn C#?
Most large companies in the area that hire our CS graduates do some or all of their software development inC#Nineof11companiesrepresentedin our advisory board want graduates to knowC#
16 January 2018
What is "Data Structures"?
4
What Are Data Structures?
Adata structureis acontainerfor holding dataUsually think of adata structureas holdingmultipledataitemsAnarrayis an example of this type ofdatastructureAJavaArrayList <T>is another example of adatastructureWe may sometimes think ofsingleobjectsas beingdatastructuresAstringholds one string of characters that may be manipulated as a whole (input the string, output the string, compare the string, and so forth)Astringmay also be thought of as acollectionof individualcharacters(orwords) that we want to manipulate individually for some taskAnobjectof almost any class may be thought of as acontainerfor the data represented by the object’sattributes
16 January 2018
What is "Data Structures"?
5
Organization of the Data
There are many different ways in which individual data items in a data structure may be organizedStored incontiguousmemory locations (e.g., anarray)Stored innon-contiguous(possiblyrandom) memory locations (e.g., alinkedlist)Storedexternallyin afileordatabaseon aharddrive, a USB drive,or“in the cloud”
16 January 2018
What is "Data Structures"?
6
Organization of the Data
Adata structuremaybeorganizedtofacilitatespecific types ofusageStored infirst-come,first-servedmanner (a waiting line orqueue)Stored inlast-in,firstoutmanner (stack)Stored in order of priority (priority-queue)Stored insortedorderOrganized forefficientstorageandretrievalor for efficientaccesstoparticularitemsOrganized forminimalmemoryusageOrganized forfastestaccess
16 January 2018
What is "Data Structures"?
7
Data Structures
Each type of data structure has its owncharacteristicsThere aretrade-offsin deciding whichdata structureto useMemoryrequirementsEfficiency(speed) of storing, finding, retrieving, or processing the dataEaseofUnderstandingProgrammingTesting/debugging/maintenanceTrade-offs: Afastalgorithmon a given data structure may requiremorememoryand bemoredifficulttounderstand, but asloweralgorithmmay takelessmemoryand beeasiertomaintain
16 January 2018
What is "Data Structures"?
8
Organization
We may have many questions to answer such asDo we need toaccessthe datarandomly(access any item without accessing all those before it, for example) or issequentialaccess sufficient for our needs?Does the data need to be in aspecific ordersuch assortedbyvalue,arrangedbytime(such as people waiting to buy a ticket to a movie),arrangedbypriority(the emergency room has to deal with someone bleeding profusely ahead of someone with a cold even if the person with the cold has been waiting longer), and so forth?Theorganization of the dataand theefficiencywith which we canstore/find/retrieve/processitems becomes more important as the amount of data gets large (it takes a lot longer to sort 1,000,000 items than it does to sort 3 items)
16 January 2018
What is "Data Structures"?
9
Algorithms
For a given data structure, we may need to do certain types of common activities such asAdd datato the data structureRetrieveor removedatafrom the data structureFinda particular data item or items in the data structureRearrange(sort) the data into some order meaningful for a particular task
16 January 2018
What is "Data Structures"?
10
Algorithms
For adata structureto be useful, it must be accompanied byimplementationsof thealgorithmsthat allow one to manipulate the data in the desired waysNotall data structures are createdequalThere is no“best”data structure forallsituationsSome are moreefficientfor specific tasks than others are but the latter group may be more efficient for a different set of tasksOne must choose the appropriate data structure for a given task
16 January 2018
What is "Data Structures"?
11
Algorithm Analysis and Selection
There may be many differentalgorithmsthat can be used to accomplish a specific taskon a particular datastructureOne must be able toanalyzethe differentalgorithmsandchooseonethat is reasonablyefficient for a given taskFor example, there are many different sorting algorithms; howshouldwe choose one that works efficiently for our data
16 January 2018
What is "Data Structures"?
12
Algorithm Limitations
Some algorithms do not make sense for a particular type of data structure, and, thus, no attempt to use them with that type of data structure should be attemptedFor example, what does it mean to sort alinked listofcoloredpixels(does aturquoisepixelcome before or after apucepixel, for example)?Aqueueis organized by thearrivaltimeof the items it contains –sortingaqueueby (say)employeenamewould destroy the ordering required by thequeue– it would no longer be aqueue
16 January 2018
What is "Data Structures"?
13
Choosing an Algorithm
A betterchoice ofalgorithms might be made if one knows something about the data involvedFor example, one type of sorting algorithm may be more efficient if the data is already “close” to being in order while anotheralgorithm maybe more efficient on totally random dataOne may search for a value in an array much more efficiently if one knows the data is sorted than ifthe order of the data is unknown
16 January 2018
What is "Data Structures"?
14
Class Libraries
There are manyclass librariesthat contain good implementations of certain data structures and the algorithms that support themAlibrarymay have aclassthat implements aLinkedList, anotherclassthat implements aQueue, another for aStack, and so forthThe implementations may also contain many useful methods (algorithms)In this course, where possible, we will learn to usedata structuresimplemented in the.NET class librarySome data structures are not implemented in the.NETlibrary, and we will have to build our own including the algorithms for inserting, finding, arranging, and retrieving items
16 January 2018
What is "Data Structures"?
15
Programs
Programs = Data Structures +AlgorithmsWhileprograms contain othercomponentssuch as user interfaces, the heart of any program is the combination of its data and what the program does withthe dataTo design agood program, one must selectappropriatedatastructuresandalgorithmsThepurpose of this course is to enable one to make intelligent decisions about these
16 January 2018
What is "Data Structures"?
16
What Will We Do?
Learn to write programs inC#, using the.NETclass libraryLearn about different types ofdatastructuresThe organization of the data in the data structureWhen using each type is appropriateSelect an appropriate data structure for a given taskIntroduction to elementaryalgorithmanalysistechniquesAnalyze algorithms to determine characteristics such as memory efficiency, execution efficiency, ease of programming including understanding, coding, and maintenanceSelect an algorithm that is appropriate to the task and reasonably efficientLearn about thetrade-offsinvolved in making intelligent decisions concerningdatastructuresandalgorithms
16 January 2018
What is "Data Structures"?
17
0
Embed
Upload