Programming in C
A3.dvi School of Computer Science University of Guelph CIS*3490 The Analysis and Design of Algorithms Winter 2023 Instructor: Fangju Wang Assignment 3 (100%) For this assignment, you are required to write programs in C. No pseudocode. Question 1 (40%) You have a list of n open intervals (a1, b1), (a2, b2), ..., (an, bn) on the integer line. An open interval (a, b) comprises all the points (integers) strictly between its endpoints a and b, i.e., (a, b) = {x|a < x="">< b)}. (the points do not include a and b.) find the maximum number of these intervals that have a common point. for example, for the intervals (0, 5), (-1, 3), (-2, 3), (3, 6), this maximum number is 3. 3 intervals (0, 5), (-1, 3), (-2, 3) have common point 1 or 2. no more than 3 intervals have a common point. write the following programs for finding the maximum number of the intervals that have a common point: 1.1 a program to implement a brute force algorithm. (15%) 1.2 a more efficient program based on the presorting technique. (25%) when a program is executed, it prompts for a file name, reads in the file containing intervals, and finds the maximum number of the intervals that have a common point. finally the program reports the number and a common point. a program is required to report the running time for searching, i.e. finding the number, (in 1.1 for searching, and in 1.2 for sorting and searching). the running time should not include the time for reading the file. you can use file data a3 q1 1.txt to develop/test your programs. a different data file will be used to grade your programs. the numbers of intervals and data formats of the two data files will be the same. question 2 (60%) write the following programs for string search: 2.1 a program to implement a brute force algorithm. (10%) 2.2 a program to implement the horspool’s algorithm. (20%) 2.3 a program to implement the boyer-moore algorithm. (20%) the text is in file data a3 q2.txt, which has 44049 lines of strings. a search pattern includes the 52 upper and lower case letters only. search is case-sensitive. when a program is executed, 1 it reads in the text, prompts for a pattern, finds all the occurrences of the pattern in the text, and reports the total number of occurrences found. don’t remove any symbols (characters) from the text. a program is required to report the number of pattern shifts and running time for each search. the running time of your horspool’s and boyer-moore programs should include the time for creating tables. the file data a3 q2.txt will be used to grade your programs. you may hard-code the file name in your programs. 2.4 analyze performance of your brute force and horspool programs. (10%) the performance parameters are the number of pattern shifts and running time. to compare two programs, choose ten search patterns of different lengths, and search them by using the programs separately. for each pattern, calculate the ratios of the performance parameters of the two programs. then, for all the ten patterns, calculate average ratios, and compare and analyze the performance of the two programs in terms of the ratios. very briefly write your comparison and analysis in the readme file submitted with your programs. note: write your own code for this assignment. no code from any source is allowed. due time: 08:00am, monday march 13, 2023. submit your work as a tar file to moodle. 2 a3_guide.dvi school of computer science university of guelph cis*3490 the analysis and design of algorithms winter 2023 instructor: fangju wang assignment 3 guide you can develop your programs using any c system, as long as your programs can be correctly compiled and executed on the socs linux server. you are allowed to use standard library functions. your programs should be submitted as a tar file containing files like readme.txt, p11.c, p12.c, p21.c, p22.c, p23.c, makefile. any compilation warning will result in a mark deduction. there will be some marks allocated for documentation. each file should have a comment at the beginning containing your name, id, date, and the assignment number. the readme file should contain the following: • name, id and assignment number • a brief and clear description of how to compile and run your programs. • comparison and analysis for q2.4. each function should have a brief comment describing its purpose. also, any section of code where it is not easily apparent what the code does should have a short comment. hints for individual questions: 1 you may visualize the example in the handout by drawing the integer line at the bottom, and above it a short line representing an interval. visualizing the example may help you understand the problem and develop algorithms. 1.1 find the minimum and maximum endpoints (integers) of all the intervals. scan the integer line between the minimum and maximum. for each of the points, check all the intervals to see how many intervals include it. 1.2 you may sort the endpoints of all the intervals, and also find the minimum and maximum of the endpoints. by scanning the sorted endpoints of intervals you can find the maximum number. 1 1.1, 1.2 the output could be something like: brute force program for finding max number of intervals the maximum number of intervals: 15057 the intervals include point: 21713 time for finding the maximum number: 6236 ms 2.1, 2.2, 2.3 you can follow the algorithms in the text. the output could be something like: a brute force program for string search. enter a pattern: maintain count: 137 shifts: 2988194 execution time = 14 ms in searching a pattern, the counts of different algorithms must be the same. the numbers of shifts of different implementations of the same algorithm could differ slightly. 2 18534 37057 35350 35355 9853 39297 14807 34713 12492 24432 22176 28324 17472 22547 40571 41371 28691 32721 8073 27922 2203 12561 7656 36225 6846 17478 6652 7446 10824 44055 22475 38101 13067 27766 23089 28030 22005 43697 12608 34524 23605 34243 18030 38875 13425 15845 36068 41153 3405 42783 5660 22682 10268 29990 15269 40196 1281 4009 3948 21191 12378 41780 37429 40163 13148 24060 16640 34210 22949 29695 2084 23386 20862 40155 32687 41332 12507 33234 15798 29077 7861 31687 18905 39526 15727 35865 10733 38385 15472 30933 26544 43051 28775 37415 19235 39821 19201 36650 30390 39664 9690 21820 39862 42003 8325 39829 20404 27667 12928 28128 13622 34347 10322 19681 8883 12100 19493 25014 7475 40256 5327 6850 22185 33070 41005 42888 18008 30677 16416 32760 10730 14130 11847 25688 6755 31576 5859 35502 8311 33101 3576 42932 3991 22645 9211 11681 33421 34311 28907 42451 27867 33119 4856 5852 4551 23617 3291 9487 19872 37155 26769 32598 2775 7230 9710 43828 6906 39239 3606 43903 3237 38901 661 40010 9583 25705 7668 18114 35425 40764 15483 24073 21236 26247 4856 31439 23934 33011 13768 44671 26186 39386 28769 33532 3106 33627 37821 41623 36610 37511 33094 42868 40878 43038 22411 30492 7328 36090 4512 39411 11063 28910 10626 27611 15040 30753 11167 16145 4412 28344 10246 29761 22041 43777 13899 25308 5981 32396 21326 26454 19374 41543 15891 37433 1546 19170 16785 26932 10867 37371 20963 29642 14389 22594 9422 31491 2625 26911 18367 31471 28121 29991 8331 16979 26709 27691 14602 32161 9753 31932 31517 41260 11086 29699 5192 24070 13159 38831 5388 30065 5853 17017 25792 26229 12439 29715 13158 34313 10149 16130 797 43933 15552 35722 9855 18796 41323 41797 30195 33790 b)}.="" (the="" points="" do="" not="" include="" a="" and="" b.)="" find="" the="" maximum="" number="" of="" these="" intervals="" that="" have="" a="" common="" point.="" for="" example,="" for="" the="" intervals="" (0,="" 5),="" (-1,="" 3),="" (-2,="" 3),="" (3,="" 6),="" this="" maximum="" number="" is="" 3.="" 3="" intervals="" (0,="" 5),="" (-1,="" 3),="" (-2,="" 3)="" have="" common="" point="" 1="" or="" 2.="" no="" more="" than="" 3="" intervals="" have="" a="" common="" point.="" write="" the="" following="" programs="" for="" finding="" the="" maximum="" number="" of="" the="" intervals="" that="" have="" a="" common="" point:="" 1.1="" a="" program="" to="" implement="" a="" brute="" force="" algorithm.="" (15%)="" 1.2="" a="" more="" efficient="" program="" based="" on="" the="" presorting="" technique.="" (25%)="" when="" a="" program="" is="" executed,="" it="" prompts="" for="" a="" file="" name,="" reads="" in="" the="" file="" containing="" intervals,="" and="" finds="" the="" maximum="" number="" of="" the="" intervals="" that="" have="" a="" common="" point.="" finally="" the="" program="" reports="" the="" number="" and="" a="" common="" point.="" a="" program="" is="" required="" to="" report="" the="" running="" time="" for="" searching,="" i.e.="" finding="" the="" number,="" (in="" 1.1="" for="" searching,="" and="" in="" 1.2="" for="" sorting="" and="" searching).="" the="" running="" time="" should="" not="" include="" the="" time="" for="" reading="" the="" file.="" you="" can="" use="" file="" data="" a3="" q1="" 1.txt="" to="" develop/test="" your="" programs.="" a="" different="" data="" file="" will="" be="" used="" to="" grade="" your="" programs.="" the="" numbers="" of="" intervals="" and="" data="" formats="" of="" the="" two="" data="" files="" will="" be="" the="" same.="" question="" 2="" (60%)="" write="" the="" following="" programs="" for="" string="" search:="" 2.1="" a="" program="" to="" implement="" a="" brute="" force="" algorithm.="" (10%)="" 2.2="" a="" program="" to="" implement="" the="" horspool’s="" algorithm.="" (20%)="" 2.3="" a="" program="" to="" implement="" the="" boyer-moore="" algorithm.="" (20%)="" the="" text="" is="" in="" file="" data="" a3="" q2.txt,="" which="" has="" 44049="" lines="" of="" strings.="" a="" search="" pattern="" includes="" the="" 52="" upper="" and="" lower="" case="" letters="" only.="" search="" is="" case-sensitive.="" when="" a="" program="" is="" executed,="" 1="" it="" reads="" in="" the="" text,="" prompts="" for="" a="" pattern,="" finds="" all="" the="" occurrences="" of="" the="" pattern="" in="" the="" text,="" and="" reports="" the="" total="" number="" of="" occurrences="" found.="" don’t="" remove="" any="" symbols="" (characters)="" from="" the="" text.="" a="" program="" is="" required="" to="" report="" the="" number="" of="" pattern="" shifts="" and="" running="" time="" for="" each="" search.="" the="" running="" time="" of="" your="" horspool’s="" and="" boyer-moore="" programs="" should="" include="" the="" time="" for="" creating="" tables.="" the="" file="" data="" a3="" q2.txt="" will="" be="" used="" to="" grade="" your="" programs.="" you="" may="" hard-code="" the="" file="" name="" in="" your="" programs.="" 2.4="" analyze="" performance="" of="" your="" brute="" force="" and="" horspool="" programs.="" (10%)="" the="" performance="" parameters="" are="" the="" number="" of="" pattern="" shifts="" and="" running="" time.="" to="" compare="" two="" programs,="" choose="" ten="" search="" patterns="" of="" different="" lengths,="" and="" search="" them="" by="" using="" the="" programs="" separately.="" for="" each="" pattern,="" calculate="" the="" ratios="" of="" the="" performance="" parameters="" of="" the="" two="" programs.="" then,="" for="" all="" the="" ten="" patterns,="" calculate="" average="" ratios,="" and="" compare="" and="" analyze="" the="" performance="" of="" the="" two="" programs="" in="" terms="" of="" the="" ratios.="" very="" briefly="" write="" your="" comparison="" and="" analysis="" in="" the="" readme="" file="" submitted="" with="" your="" programs.="" note:="" write="" your="" own="" code="" for="" this="" assignment.="" no="" code="" from="" any="" source="" is="" allowed.="" due="" time:="" 08:00am,="" monday="" march="" 13,="" 2023.="" submit="" your="" work="" as="" a="" tar="" file="" to="" moodle.="" 2="" a3_guide.dvi="" school="" of="" computer="" science="" university="" of="" guelph="" cis*3490="" the="" analysis="" and="" design="" of="" algorithms="" winter="" 2023="" instructor:="" fangju="" wang="" assignment="" 3="" guide="" you="" can="" develop="" your="" programs="" using="" any="" c="" system,="" as="" long="" as="" your="" programs="" can="" be="" correctly="" compiled="" and="" executed="" on="" the="" socs="" linux="" server.="" you="" are="" allowed="" to="" use="" standard="" library="" functions.="" your="" programs="" should="" be="" submitted="" as="" a="" tar="" file="" containing="" files="" like="" readme.txt,="" p11.c,="" p12.c,="" p21.c,="" p22.c,="" p23.c,="" makefile.="" any="" compilation="" warning="" will="" result="" in="" a="" mark="" deduction.="" there="" will="" be="" some="" marks="" allocated="" for="" documentation.="" each="" file="" should="" have="" a="" comment="" at="" the="" beginning="" containing="" your="" name,="" id,="" date,="" and="" the="" assignment="" number.="" the="" readme="" file="" should="" contain="" the="" following:="" •="" name,="" id="" and="" assignment="" number="" •="" a="" brief="" and="" clear="" description="" of="" how="" to="" compile="" and="" run="" your="" programs.="" •="" comparison="" and="" analysis="" for="" q2.4.="" each="" function="" should="" have="" a="" brief="" comment="" describing="" its="" purpose.="" also,="" any="" section="" of="" code="" where="" it="" is="" not="" easily="" apparent="" what="" the="" code="" does="" should="" have="" a="" short="" comment.="" hints="" for="" individual="" questions:="" 1="" you="" may="" visualize="" the="" example="" in="" the="" handout="" by="" drawing="" the="" integer="" line="" at="" the="" bottom,="" and="" above="" it="" a="" short="" line="" representing="" an="" interval.="" visualizing="" the="" example="" may="" help="" you="" understand="" the="" problem="" and="" develop="" algorithms.="" 1.1="" find="" the="" minimum="" and="" maximum="" endpoints="" (integers)="" of="" all="" the="" intervals.="" scan="" the="" integer="" line="" between="" the="" minimum="" and="" maximum.="" for="" each="" of="" the="" points,="" check="" all="" the="" intervals="" to="" see="" how="" many="" intervals="" include="" it.="" 1.2="" you="" may="" sort="" the="" endpoints="" of="" all="" the="" intervals,="" and="" also="" find="" the="" minimum="" and="" maximum="" of="" the="" endpoints.="" by="" scanning="" the="" sorted="" endpoints="" of="" intervals="" you="" can="" find="" the="" maximum="" number.="" 1="" 1.1,="" 1.2="" the="" output="" could="" be="" something="" like:="" brute="" force="" program="" for="" finding="" max="" number="" of="" intervals="" the="" maximum="" number="" of="" intervals:="" 15057="" the="" intervals="" include="" point:="" 21713="" time="" for="" finding="" the="" maximum="" number:="" 6236="" ms="" 2.1,="" 2.2,="" 2.3="" you="" can="" follow="" the="" algorithms="" in="" the="" text.="" the="" output="" could="" be="" something="" like:="" a="" brute="" force="" program="" for="" string="" search.="" enter="" a="" pattern:="" maintain="" count:="" 137="" shifts:="" 2988194="" execution="" time="14" ms="" in="" searching="" a="" pattern,="" the="" counts="" of="" different="" algorithms="" must="" be="" the="" same.="" the="" numbers="" of="" shifts="" of="" different="" implementations="" of="" the="" same="" algorithm="" could="" differ="" slightly.="" 2="" 18534="" 37057="" 35350="" 35355="" 9853="" 39297="" 14807="" 34713="" 12492="" 24432="" 22176="" 28324="" 17472="" 22547="" 40571="" 41371="" 28691="" 32721="" 8073="" 27922="" 2203="" 12561="" 7656="" 36225="" 6846="" 17478="" 6652="" 7446="" 10824="" 44055="" 22475="" 38101="" 13067="" 27766="" 23089="" 28030="" 22005="" 43697="" 12608="" 34524="" 23605="" 34243="" 18030="" 38875="" 13425="" 15845="" 36068="" 41153="" 3405="" 42783="" 5660="" 22682="" 10268="" 29990="" 15269="" 40196="" 1281="" 4009="" 3948="" 21191="" 12378="" 41780="" 37429="" 40163="" 13148="" 24060="" 16640="" 34210="" 22949="" 29695="" 2084="" 23386="" 20862="" 40155="" 32687="" 41332="" 12507="" 33234="" 15798="" 29077="" 7861="" 31687="" 18905="" 39526="" 15727="" 35865="" 10733="" 38385="" 15472="" 30933="" 26544="" 43051="" 28775="" 37415="" 19235="" 39821="" 19201="" 36650="" 30390="" 39664="" 9690="" 21820="" 39862="" 42003="" 8325="" 39829="" 20404="" 27667="" 12928="" 28128="" 13622="" 34347="" 10322="" 19681="" 8883="" 12100="" 19493="" 25014="" 7475="" 40256="" 5327="" 6850="" 22185="" 33070="" 41005="" 42888="" 18008="" 30677="" 16416="" 32760="" 10730="" 14130="" 11847="" 25688="" 6755="" 31576="" 5859="" 35502="" 8311="" 33101="" 3576="" 42932="" 3991="" 22645="" 9211="" 11681="" 33421="" 34311="" 28907="" 42451="" 27867="" 33119="" 4856="" 5852="" 4551="" 23617="" 3291="" 9487="" 19872="" 37155="" 26769="" 32598="" 2775="" 7230="" 9710="" 43828="" 6906="" 39239="" 3606="" 43903="" 3237="" 38901="" 661="" 40010="" 9583="" 25705="" 7668="" 18114="" 35425="" 40764="" 15483="" 24073="" 21236="" 26247="" 4856="" 31439="" 23934="" 33011="" 13768="" 44671="" 26186="" 39386="" 28769="" 33532="" 3106="" 33627="" 37821="" 41623="" 36610="" 37511="" 33094="" 42868="" 40878="" 43038="" 22411="" 30492="" 7328="" 36090="" 4512="" 39411="" 11063="" 28910="" 10626="" 27611="" 15040="" 30753="" 11167="" 16145="" 4412="" 28344="" 10246="" 29761="" 22041="" 43777="" 13899="" 25308="" 5981="" 32396="" 21326="" 26454="" 19374="" 41543="" 15891="" 37433="" 1546="" 19170="" 16785="" 26932="" 10867="" 37371="" 20963="" 29642="" 14389="" 22594="" 9422="" 31491="" 2625="" 26911="" 18367="" 31471="" 28121="" 29991="" 8331="" 16979="" 26709="" 27691="" 14602="" 32161="" 9753="" 31932="" 31517="" 41260="" 11086="" 29699="" 5192="" 24070="" 13159="" 38831="" 5388="" 30065="" 5853="" 17017="" 25792="" 26229="" 12439="" 29715="" 13158="" 34313="" 10149="" 16130="" 797="" 43933="" 15552="" 35722="" 9855="" 18796="" 41323="" 41797="" 30195="">