CSE 214 : Data Structures

algorithms & data structures practice test / quiz and need the explanation and answer to help me learn.

All assignments must useJava 17 LTS, the latest long-term support release for the Java SE platform. As a development environment, the use of IntelliJ IDEA is required.
Requirements: 123 | Java
CSE214:DataStructures(Fall2023)–AssignmentIInstructor:Dr.RitwikBanerjeeComputerScience,StonyBrookUniversityThisassignmentconsistsoftwoparts,and6pages.Studentsarerequiredtofollowthedevelopmentenvi-ronmentdescribedforthiscourse.Anycodeprovidedtoyouaspartofthisassignmentcanbefoundintheappendixsectionsofthisdocument.Thisassignmentisdueby11:59pm,Sep22(Friday).Rememberthatwheneveryouareimplementingadatastructurecorrespondingtoanabstractdatatype,youcanwriteadditionalmethodsthatarenotrequiredbytheinterface.Theseadditionalmethods,however,arenotapartofthedatatype’s“contract”,andtherefore,mustbeprivate.I.LinkedListTostartoff,youmustimplementausableDoublyLinkedListgenericclass.Weusethisnametoavoidanyconfusionwiththebuilt-inclassprovidedbytheJavalibrary.Afullyfunctioningimplementationrequiresthreeclasses:1.TheDoublyLinkedListclass,whereeachnodemaintainsanextandapreviousreference.ThisclassmustimplementtheListAbstractTypeinterfaceprovidedtoyouaspartofthisassignment(andNOTthebuilt-inlistinterfaceprovidedinJava’slibrary).2.ANodeclass,whichmustbeaprivatestaticclassnestedinsideDoublyLinkedList.3.ADoublyLinkedListIteratorclass,whichmustimplementtheTwoWayListIteratorinterfacepro-videdtoyouaspartofthisassignment.1.(5)TheNodeclasswithitsfieldsandconstructor:TheveryfirststepistounderstandhowtowritetheNodeclassasaprivateclassnestedinsideDoublyLinkedList.Nestedclassescanbestaticornon-static,butinthisassignmentyouwillhavetouseastaticnestedclass.TheNodeclasswillneverbedirectlyusedbyanyexternalclientcode,sofieldsofthisclasscanbepublic(remember,theentireclassisnestedandprivate,sothesefieldscannotbeaccessedexternallyeveniftheyareindividuallydeclaredtobeanythingotherthanprivate).TocreateaDoublyLinkedListwithanyelements,however,youwillneedtowriteaconstructorforthisNodeclass,andanyNodeinstancemusthaveanextandapreviousreferencealongwithitsownelement.2.(15)ImplementingtheCollectionTypemethods:Aswehavediscussedinthelectures,thedatastructureisacompleteimplementationofanabstractdatatype.Inthisassignment,yourDoublyLinkedListdatastructuremustimplementtheListAbstractTypeinterface.Butthisdatatype,inturn,extendstheCollectionTypeinterface.Thus,youmustimplementthefollowingmethodssothattheyfunctioncorrectlyasperthedocumentationprovidedintheCollectionTypeinterfacecode:booleanadd(Eelement);booleanremove(Eelement);intsize();booleanisEmpty();booleancontains(Eelement);3.(15)ImplementingtheListAbstractTypemethods:TheDoublyLinkedListclasswill,ofcourse,alsoneedtoimplementtheotheradditionalmethodsdeclaredintheListAbstractTypeinterface.Thesemethodsaremorespecifictotheconceptofasequentialcollectionofelements,andtherefore,useofanelement’s“position”inalist.YoumustimplementthefollowingmethodssothattheyfunctioncorrectlyasperthedocumentationintheListAbstractTypeinterfacecode:1
CSE214:DataStructures(Fall2023)AssignmentIEget(intindex);Eset(intindex,Eelement);voidadd(intindex,Eelement);voidremove(intindex);4.(15)Implementingatwo-wayiterator:Inquestion1,wedidnotincludeoneveryimportantmethod,whichisinheritedfromthejava.lang.Iterableinterface.Inyourentireimplementationofadoublylinkedlist,IterableistheonlyinterfacereadilyavailablefromacoreJavalibrary(unliketheothertwobuiltseparatelyforthisassignment:CollectionTypeandListAbstractType).TheIterableinterfacerequiresimplementatingamethoddeclaredasIteratoriterator();Butinourcase,aspecialiteratorisneeded,inordertoiterateforwardandbackwardthroughadoublylinkedlist.So,Java’sbuiltiniterator(i.e.,theobjectbeingreturnedbytheabovemethodsignature)isnotenough.So,youareprovidedwithasub-interfacewithadditionalmethods,calledtheTwoWayListIterator.YourDoublyLinkedListclassmustthereforeimplementamethodwiththefollowingsignature:publicTwoWayListIteratoriterator();Theissue,ofcourse,isthatTwoWayListIteratorisaninterface,notaclass!Whichmeanstherehastobeaclassthatimplementsthisinterface.Implementaprivateclassnestedinsideyourlinkedlistclass,calledDoublyLinkedListIterator,toaccomplishthis.Onceagain,sincethisisanestedclass,carefullythinkaboutwhetherornotitshouldbestatic:-Isaniteratorassociatedwithaspecificlistinstance,orisaniteratorsomethingthatis“shared”bythewholeclass?II.HotPotato!ThereareNpeople,numbered1toN,whoaresittinginacircle.Startingatperson1,ahotpotatoispassed.AfterMpasses,thepersonholdingthehotpotatoiseliminated,andthecircleisreducedby1insize(i.e.,thereisnoemptyspotleftaftertheeliminationofaplayer).Thegamecontinueswiththepersonwhowassittingaftertheeliminatedplayerpickingupthehotpotato.Thelastremainingplayerwins.So,ifthegamestartswithN=5andM=0,theplayersareeliminatedimmediatelyintheorder1,2,3,4,andplayer5wins.IfthegamestartswithN=5andM=1,thentheplayersareeliminatedintheorder2,4,1,5,andplayers3wins.Asyoucanprobablyguess,thisgamecanbeimplementedusingalinkedlist,wherethehotpotatobeingpassedaroundcanbethoughtasthe“iteration”onthatlist.Yourtaskistowriteaprogramtoplaythisgameintwodifferentways:5.(25)UseyourownDoublyLinkedListclasstoimplementthecircleofplayers.Thus,youwillalsoneedtouseyourownDoublyLinkedListIteratortosimulatethepasses,andyourownimplementationofmethodssuchasremovetoreflecttheeliminationofplayers.ThismustbeimplementedastheplayWithDoublyLinkedList(int,int)methodprovidedtoyouinHotPotato.java.Youcanaddothermethodstothisclassifyouneed.Theseadditionalmethodsmust,however,beprivate.Thisexerciseismeanttodevelopyourinsightsabouthowtousedatastructuresanddatatypesyouhavebuilt,andattemptstobypassthatgoal(by,say,internallyusingarraysorsomeotherdatastructurereadilyavailablefromJava)willbeviewedasanincorrectsolutiontothisquestion.6.(25)Thesameasthepreviousquestion,butusingJava’sbuiltinjava.util.LinkedListclassalongwithitsiteratorandmethods.ThisimplementationmustbeintheplayWithLinkedList(int,int)methodinHotPotato.java.Thispartoftheassignmentisincludedsothatyougetusedtonotjustbuildingyourowndatastructures,butalsogainexperienceinusingbuiltindatastructuresanddatatypes.Here,too,theuseofanybuiltindatastructuresotherthanlinkedlistwillbeviewedasanincorrectsolutiontothisquestion.2
CSE214:DataStructures(Fall2023)AssignmentIForbothimplementations,youcanassumethatthegamewillbeplayedwithatleasttwoplayers(i.e.,N>1),andthatthelengthofthepasswillalwaysbeanon-negativevalue(i.e.,M≥0).Reallyimportantnotes1.Thecorrectnessofyourcodewillbetestedwithvarioustestcases,andNOTbyreadingthroughyourcode.Inlectures,wehavediscussedtheroleofa“client”code.Forthisassignment(andfutureassignmentsinthiscourse),youshouldthinkofthegrader’scodeasaclientcode.Forexample,thegraderwilltesttheset(intindex,Eelement)methodbycreatingalistusingyouradd(Eelement)methodafewtimes,andthencallingthesetmethod.Thegraderwillnotreadyourcodeline-by-linetoassessitscorrectness!2.Donotthinkofthisassignmentasanimplementationofindividualmethodsputtogether.Manymethodsareinterrelated,andincorrectimplementationofonemethodmayaffectthepointsobtainedinotherplaces.Forexample,ifyouradd(Eelement)methoddoesnotwork,thegradercannotevencreatealistwithyourcode.Inthatcase,thegradersimplycannotgradeanyoftheothermethodseither!Another(lessdrastic)exampleofsuchinterdependence:thesize()methodcanonlybedeemedcorrectifitreportsthecorrectsizeofalistafterseveralcombinationsofadditionsandremovals.So,mistakesintheadd(Eelement)and/ortheremove(Eelement)methodscanaffectthepointsobtainedforthesize()method(e.g.,addtwoitemstoanemptylist,thenremoveoneitem,butacallstosize()stillreturns2).3.TheHotPotatocodealsoshowsyouhowthemainmethodwillcallyourimplementationsofthegame,andtheexpectedoutputs.Theprovidedmainmethodthusservesasaverybasicclientcode,withtwotestcases.Studentsareexpectedtotesttheirowncodewithasmanytestcasesastheywant.4.Anicestringrepresentationofyourlinkedlistmaybeveryusefulfortestingyourowncode,andprintingouttheliststhatyouobtainaftervariousoperations.Toaidyouwiththis,thetoString()methodisprovidedintheappendix.PleaseincludethismethodexactlyasprovidedinyourDoublyLinkedListclass.Whengrading,thismethodwillbeexpectedtobeincluded,anditwillbecalledtotesttherestofyourcodeforthisclass.5.Itmightbehelpfultorememberthatthereisaveryeasywaytotestifyouhaveimplementedtheiter-ator:ifyoucannotuseanenhancedforloop(alsocalledthefor-eachloop)onyourDoublyLinkedList,thatmeansyouhavenotimplementedaniteratorproperly.Averysimpleclientcodefortestingmaybesomethinglikepublicstaticvoidmain(String…args){DoublyLinkedListnums=newDoublyLinkedList<>();System.out.println(nums.toString());//shouldprint”[]”nums.add(1);nums.add(2);System.out.println(nums.toString());//shouldprint”[1,2]”}6.Whattosubmit?Youwillnoticeintheappendixcodesthatyouhavetowriteallyourcodeinapackagecalled“cse214hw1”.Onceyouhavewrittenandtestedallyourcode,simplycreatea.zipofthispackageandsubmititonBrightspace.Recallthatapackageisjustafolderinyourcomputer,sozippingthefilesworksjustlikecompressingandcreatinga.zipofanyotherfolder.DoNOTsubmityourentireJavaproject!!Deviationsfromtheexpectedsubmissionformatand/ortherequirementsmentionedearlierinthisassignmentcarriesvaryingdegreesofscorepenalty(dependingontheamountofdeviation).AppendixA:CollectionType.javapackagecse214hw1;/***DONOTMODIFYTHISCODE!!*@authorRitwikBanerjee*/3
CSE214:DataStructures(Fall2023)AssignmentIpublicinterfaceCollectionTypeextendsIterable{/***Addsthespecifiedelementtothiscollection.Ifthecollectionoffersaparticular*iterationorder,thentheelementisaddedattheendofthecollection.**@paramelementthespecifiedelement*@return{@codetrue}iftheelementwassuccessfullyadded*/booleanadd(Eelement);/***Removesthespecifiedelement(ifitexists)fromthiscollection.Ifthecollection*offersaparticulariterationorder,thenthefirstoccurrenceofthiselement(as*encounteredintheiteration)isremoved.**@paramelementthespecifiedelement*@return{@codetrue}iftheelementwassuccessfullyremovedfromthiscollection*/booleanremove(Eelement);/***@returnthenumberofelementsinthiscollection*/intsize();/***@return{@codetrue}ifthiscollectioncontainsnoelements*/booleanisEmpty();/***Identifieswhetherornotthiscollectioncontainsthespecifiedelement.**@paramelementthespecifiedelement*@return{@codetrue}ifthespecifiedelementwasfoundinthiscollection*/booleancontains(Eelement);}AppendixB:ListAbstractType.javapackagecse214hw1;/***DONOTMODIFYTHISCODE!!*@authorRitwikBanerjee*/publicinterfaceListAbstractTypeextendsCollectionType{/***@paramindexthespecifiedpositioninthislist*@returntheelementfoundatthespecifiedpositioninthislist*/Eget(intindex);/***Replacesthecurrentelementatthespecifiedpositionwiththeprovidednewelement.**@paramindexthespecifiedposition*@paramelementthenewelementprovided*@returntheelementpreviouslyheldatthespecifiedposition*/Eset(intindex,Eelement);/***Addsthespecifiedelementatthespecifiedposition,pushingsubsequentelementsto*onepositionhigher.If{@codeindex==0},theadditionhappensatthefrontofthis*list.If{@codeindex==size()},theelementisaddedasthenewlastelement.4
CSE214:DataStructures(Fall2023)AssignmentI**@paramindexthespecifiedposition*@paramelementthespecifiedelementtobeadded*/voidadd(intindex,Eelement);/***Removestheelementatthespecifiedposition.**@paramindexthespecifiedposition*/voidremove(intindex);}AppendixC:TwoWayListIterator.javapackagecse214hw1;importjava.util.Iterator;importjava.util.NoSuchElementException;/***DONOTMODIFYTHISCODE!!*@authorRitwikBanerjee*/publicinterfaceTwoWayListIteratorextendsIterator{/***@return{@codetrue}ifthereverseiterationhasmoreelements.Inotherwords,*returns{@codetrue}if{@link#previous}wouldreturnanelementratherthan*throwinganexception.*/booleanhasPrevious();/***Returnsthepreviouselementinthislistandmovesthecursorpositionbackward*byone.Thismethodmay,ifneeded,beintermixedwithcallsto{@link#next()}*togobackandforth.**@returnthepreviouselementinthislist*@throwsNoSuchElementExceptioniftheiterationhasnopreviouselements*/Eprevious();/***Insertsthespecifiedelementintothelist.Theelementisinsertedimmediately*beforetheelementthatwouldbereturnedby{@link#next()},ifany,andafter*theelementthatwouldbereturnedby{@link#previous()},ifany.Ifthelist*containsnoelements,thenewelementbecomesthesoleelementonthelist.The*newelementisinsertedbeforetheimplicitcursor:asubsequentcallto*{@codenext}wouldbeunaffected,andasubsequentcallto{@codeprevious}would*returnthenewelement.**@paramelementtheelementtoinsert*@throwsUnsupportedOperationExceptionifthe{@codeadd}methodisnotsupported*bythislistiterator*/voidadd(Eelement);/***Replacesthelastelementreturnedby{@link#next()}or{@link#previous()}with*thespecifiedelement(optionaloperation).*Thiscallcanbemadeonlyifneither{@link#remove()}nor{@link#add(E)}have*beencalledafterthelastcallto{@codenext()}or{@codeprevious}.**@paramelementtheelementwithwhichtoreplacethelastelementreturnedby*{@codenext}or{@codeprevious}5
CSE214:DataStructures(Fall2023)AssignmentI*@throwsUnsupportedOperationExceptionifthe{@codeset}operationisnot*supportedbythislistiterator*@throwsIllegalStateExceptionifneither{@codenext}nor{@codeprevious}*havebeencalled,or{@coderemove}or*{@codeadd}havebeencalledafterthelast*callto{@codenext}or{@codeprevious}*/voidset(Eelement);}AppendixD:PrintingaDoublyLinkedList@OverridepublicStringtoString(){Iteratorit=this.iterator();if(!it.hasNext())return”[]”;StringBuilderbuilder=newStringBuilder(“[“);while(it.hasNext()){Ee=it.next();builder.append(e.toString());if(!it.hasNext())returnbuilder.append(“]”).toString();builder.append(“,”);}//codeexecutionshouldneverreachthislinereturnnull;}AppendixE:HotPotato.javapackagecse214hw1;importjava.util.LinkedList;publicclassHotPotato{publicstaticDoublyLinkedListplayWithDoublyLinkedList(intnumberOfPlayers,intlengthOfPass){returnnull;//TODO}publicstaticLinkedListplayWithLinkedList(intnumberOfPlayers,intlengthOfPass){returnnull;//TODO}publicstaticvoidmain(String…args){//inbothmethods,thelististheorderinwhichtheplayersareeliminated//thelastplayer(i.e.,thelastelementinthereturnedlist)isthewinnerSystem.out.println(playWithDoublyLinkedList(5,0));//expectedoutput:[1,2,3,4,5]System.out.println(playWithLinkedList(5,1));//expectedoutput:[2,4,1,5,3]}}6

Who We Are

We are a professional custom writing website. If you have searched a question and bumped into our website just know you are in the right place to get help in your coursework.

Do you handle any type of coursework?

Yes. We have posted over our previous orders to display our experience. Since we have done this question before, we can also do it for you. To make sure we do it perfectly, please fill our Order Form. Filling the order form correctly will assist our team in referencing, specifications and future communication.

Is it hard to Place an Order?

1. Click on the “Place order tab at the top menu or “Order Now” icon at the bottom and a new page will appear with an order form to be filled.

2. Fill in your paper’s requirements in the "PAPER INFORMATION" section and click “PRICE CALCULATION” at the bottom to calculate your order price.

3. Fill in your paper’s academic level, deadline and the required number of pages from the drop-down menus.

4. Click “FINAL STEP” to enter your registration details and get an account with us for record keeping and then, click on “PROCEED TO CHECKOUT” at the bottom of the page.

5. From there, the payment sections will show, follow the guided payment process and your order will be available for our writing team to work on it.

Need this assignment or any other paper?

Click here and claim 25% off
Discount code SAVE25