C dynamic programming assignment keyword out of context
a3_writeup Page1of5 SoftwareEngineering265 SoftwareDevelopmentMethods Spring2020 Assignment3 Due:Friday,March20,11:55pmbysubmissionviagit (nolatesubmissionsaccepted) Programmingenvironment ForthisassignmentpleaseensureyourworkexecutescorrectlyontheLinux machinesinELWB238.Youarewelcometouseyourownlaptopsanddesktopsfor muchofyourprogramming;ifyoudothis,giveyourselfafewdaysbeforethedue datetoironoutanybugsintheCprogramyouhaveuploadedtotheBSEng machines.(Bugsinthiskindofprogrammingtendtobeplatformspecific,and somethingthatworksperfectlyathomemayendupcrashingonadifferent hardwareconfiguration.) Individualwork Thisassignmentistobecompletedbyeachindividualstudent(i.e.,nogroupwork). Naturallyyouwillwanttodiscussaspectsoftheproblemwithfellowstudents,and suchdiscussionisencouraged.However,sharingofcodefragmentsisstrictly forbiddenwithouttheexpresswrittenpermissionofthecourseinstructor (Zastre).Ifyouarestillunsureaboutwhatispermittedorhaveotherquestions aboutwhatconstitutesappropriatecollaboration,pleasecontactmeassoonas possible.(Code-similarityanalysistoolswillbeusedtoexaminesubmitted programs.) Questions Ifyouhaveanyquestionsabouttheassignment,pleasepostthemtoourcourse’s channelatrocket.csc.uvic.ca(i.e.,RocketChat).ByusingthisSlack-like environment,Icannotonlyprovideanswerstoqueriesbutalsogiveeachofyoua chancetowriteanswerstoquestionsfromfellowstudents. Page2of5 Objectivesofthisassignment • RevisittheCprogramminglanguage,thistimeusingdynamicmemory. • UseGittomanagechangesinyoursourcecodeandannotatetheevolutionof yoursolutionwithmessagesprovidedduringcommits. • Testyourcodeagainstthe20providedtestcasesfromassignment#2. • Usevalgrindtodeterminehoweffectiveyoursolutionisinitsmanagement ofdynamicmemory. kwoc3.c:UsingC’sheapmemoryforKWOC Inassignment2youusedPythontoimplementanextendedversionoftheKWOC scheme(i.e.,wordswithidenticalspellingbutdifferentlettercasewereconsidered thesamekeyword).Forthisassignmentyouaretowriteanimplementationcalled kwoc3toprovidethesamefunctionality,butthistimeusingCandusingdynamic memory. Wewill,however,re-introducetworestrictionsoninputinordertohelpyouwith yourproblemsolvingforyoursolution.Thatis: • Youmayassumethatkeywordswillbeatmost40characterslong,andyou mayuseacompile-timeconstanttorepresentthis. • Youmayassumethelengthofanyinputlinewillbeatmost100characters, andyoumayuseacompile-timeconstanttorepresentthis. Notethatthereisnorestrictionorupperlimitonthenumberofdistinctkeywordsor exceptionswords,noristhereanyrestrictiononthenumberoflinesofinput.(This issimilartoassignment#2.)Thatis,youarenotpermittedtouseanycompile-time constantsforthese.Putdifferently,youarenotpermittedtostaticallydeclare arrayslargeenoughtoholdallthekeywords,exceptionwords,andinput lines. Thereforeinordertostorekeywords,exceptionwords,andinputlines,youmustto useeitherlinked-listsordynamically-sizedarraysorboth. Inadditiontotheserequirementsforyourimplementation,theprogramitselfnow consistsofseveralfiles,someofwhichareCsourcecode,andoneofwhichisfor buildmanagement. • kwoc3.c:Themajorityofyoursolutionwillmostlikelyappearinthisfile. Somedemocode(protectedwithan#ifdef DEBUGconditional-compilation directive)showshowasimplelistconsistingofwordscanbeconstructed, traversed,anddestroyed. Page3of5 • emalloc.[ch]:Codeforsafecallstomalloc(),asisdescribedinlectures,is availablehere. • linky.[ch]:Typedefinitions,prototypes,andcodeforthesingly-linkedlist implementationdescribedinlectures.Youarepermittedtomodifythese routinesoraddtotheseroutinesinordertosuityoursolution.Regardlessof whetherornotyoudoso,however,youarefullyresponsibleforany segmentationfaultsthatoccurastheresultofthiscode’soperation. • makefile:Thisautomatesmanyofthestepsrequiredtobuildthekwoc3 executable,regardlessofwhatfiles(.cor.h)aremodified.TheUnixmake utilitywillbedescribedinlectures. Starterversionsofthesefilesareinthe/home/zastre/seng265/a3directory. Youmustensureallofthesefilesareinthea3/directoryofyourrepo,and mustalsoensurethatallofthesefilesareproperlyadded,committed,and pushed. Acalltokwoc3willuseidenticalargumentstothatfromthefirstassignment.Inthe examplesbelow,theoutputofkwoc3isalsobeingcomparedwithwhatisexpected: ./kwoc3 in14.txt -e english-2.txt | diff out14.txt - ./kwoc3 -e latin-2.txt in18.txt | diff out18.txt - Afewmoreobservations: • Allallocatedheapmemoryisautomaticallyreturnedtotheoperatingsystem upontheterminationofaUnixprocessorprogram(suchaskwoc3).Thisis trueregardlessofwhethertheprogrammerusesfree()todeallocate memoryintheprogramornot.However,itisalwaysagoodpracticetowrite ourcodesuchthatwedeallocatememoryviafree()–thatis,onenever knowswhentheircodemaybere-usedinthefuture,andhavingtorewrite existingcodetoproperlydealwiththedeallocationofmemorycanbe difficult.Aprogramwhereallmemoryisproperlydeallocatedbythe programmerwillproduceareportfromvalgrindstatingthatallheap blockswerefreeandthattheheapmemoryinuseatexitis“0bytesin0 blocks”.valgrindwillbediscussedduringtheduringlabs. • Youmustnotuseprogram-scopeorfile-scopevariables. Page4of5 • Youmustmakegooduseoffunctionaldecomposition.Phrasedanother way,yoursubmittedworkmustnotcontainoneortwogiantfunctions whereallofyourprogramlogicisconcentrated. Exercisesforthisassignment • Withinyourgitrepoensurethereisana3/subdirectory.(Fortestingplease usethefilesprovidedforassignment#2.)Allfilesdescribedearlierinthis documentmustbeinthatsubdirectory.Notethatstarterversionsofallthese filesareavailableforyouinthe/home/zastre/seng265/a3directory. • Writeyourprogram.Amongstothertasksyouwillneedto: • readtextinputfromafile,linebyline. • implementrequiredmethodsforthesolution,alongwithanyother methodsyoubelievearenecessary. • extractsubstringsfromlinesproducedwhenreadingafile • write,test,anddebuglinked-listroutines • write,test,anddebugroutinesfordynamically-sizedarrays. • Usethetestfilesandlistedtestcasestoguideyourimplementationeffort. Refrainfromwritingtheprogramallatonce,andbudgettimetoanticipate when“thingsgowrong”. • Forthisassignmentyoucanassumealltestinputswillbewell-formed(i.e., ourteachingassistantwillnottestyoursubmissionforhandlingofinputor forargumentscontainingerrors).Ihadwantedtothrowsomeerrorhandling atyou,butIthinkyouhaveyourhandsfullenoughwithwranglingCinto behavingwellwithdynamicmemory. Whatyoumustsubmit • Thesevenfileslistedearlierinthisassignmentdescription(kwoc3.c, emalloc.c,emalloc.h,listy.c,listy.h,,makefile). • Anyadditionalsource-codefilesthatyouintroduceforyoursolution.You musttakeresponsibilityforensuringsuchfilesareinyourgitproject.If thesefilesaremissing,thentheteachingteamwillbeunabletobuildandtest yoursolutionforA#3. Page5of5 Evaluation Ourgradingschemeisrelativelysimple. • “A”grade:Asubmissioncompletingtherequirementsoftheassignment whichiswell-structuredandveryclearlywritten.Alltestspassandtherefore noextraneousoutputisproduced.valgrindproducesareportstatingthat noheapblocksorheapmemoryisinuseattheterminationofkwoc3. • “B”grade:Asubmissioncompletingtherequirementsoftheassignment. kwoc3canbeusedwithoutanyproblems;thatis,alltestspassandtherefore noextraneousoutputisproduced.valgrindstatesthatsomeheapmemory isstillinuse. • “C”grade:Asubmissioncompletingmostoftherequirementsofthe assignment.kwoc3runswithsomeproblems. • “D”grade:Aseriousattemptatcompletingrequirementsfortheassignment. kwoc3runswithquiteafewproblems;somenon-trivialtestspass. • “F”grade:Eithernosubmissiongiven,orsubmissionrepresentsverylittle work,ornotestspass.