Programming in C
A4.dvi School of Computer Science University of Guelph CIS*3490 The Analysis and Design of Algorithms Winter 2023 Instructor: Fangju Wang Assignment 4 (100%) Question 1: BST Creation (70%) File data A4 Q1.txt contains 2045 word instances. Develop two programs to read the file, create optimal binary search trees (BSTs) for the words, and search the trees. In a tree, create a node for a word, even the word may appear multiple times in the file, i.e. the word may have multiple instances. For example, undergraduate appears nine times in the file, but there should be only one node for it. It is assumed that the probability to search a word is proportional to the word’s frequency in the text. 1.1 BST by dynamic programming (40%) Develop a program to create an optimal BST by using the technique of dynamic programming (described in section 8.3 in the textbook). You are required to calculate the “average number table” and “root table”. After creating the tree, the program prompts the user to enter a word (key) and searches the tree for the word. Whenever the program compares user input K with word W at node V , it displays word W , the minimum average number of comparisons of the subtree rooted at V (three digits after the decimal point), and the subtree to go (left or right). If the program fails to find the K in the tree, it displays “not found” after comparisons. Please see the guide for suggested output format. 1.2 BST by greedy technique (30%) Develop a program to create an optimal BST by using the greedy technique. After creating the tree, the program prompts the user to enter a word (key) and searches the tree for the word. Whenever the program compares user input K with word W at node V , it displays word W , the probability of W (three digits after the decimal point), and the subtree to go (left or right). If the program fails to find the K in the tree, it displays “not found” after comparisons. Please see the guide for suggested output format. Question 2: Stable Marriage Problem (30%) Develop a program to implement the Gale-Shapley stable marriage algorithm. The program reads in a file storing preference lists, and outputs the solution. File data A4 Q2 1.txt and data A4 Q2 2.txt can be used to develop and test your program. In a data file, the first value is the n, followed by two sets of preference lists. When your program is executed, it prompts a file name, reads in the file, and displays the result as an n × n matrix. The data file used to grade your program will have the same format, and the n value may be 3 or 4. Please see the guide for the formats of input file and suggested output. 1 Note: Write your own code for this assignment. NO code from any source is allowed. Due time: 08:00am, Monday, March 27, 2023. Submit your work as a tar file to Moodle. 2 A4_guide.dvi School of Computer Science University of Guelph CIS*3490 The Analysis and Design of Algorithms Winter 2023 Instructor: Fangju Wang Assignment 4 Guide Hints and suggestions for individual questions: • For Q1.1, you can follow the algorithm on page 302 in the textbook. The algorithm is also on slide 33 in “08 Dynamic Programming”. Slides 22 – 35 provide more details and examples. • For Q1.1, your program output can be something like: Enter a key: undergraduate Compared with of (6.147), go right subtree. Compared with the (1.972), go right subtree. Compared with university (0.412), go left subtree. Compared with to (0.156), go right subtree. Compared with undergraduate (0.053), found. • For Q1.2, you can sort the words into a sequence in alphabetic order, find the word with the largest probability and place it in the root of tree. Then split the sorted word sequence into two sub-sequences and create two trees from the two sub-sequences as the subtrees of the root mentioned above, by using the same method. Do this recursively. • For Q1.2, your program output can be something like: Enter a key: wine Compared with the (0.061), go right subtree. Compared with to (0.031), go right subtree. Compared with university (0.018), go right subtree. Compared with with (0.005), go left subtree. Compared with which (0.004), go right subtree. Compared with winter (0.002), go left subtree. Compared with will (0.001), go right subtree. Not found. • In Q1.1 and Q1.2, a difference of 0.05 in average number or probability is acceptable. 1 • For Q2, you can follow the algorithm on page 381 in the textbook. The algorithm is also on slide 39 in “10 Iterative Improvement”. Slides 36 – 43 provide more details and examples. • The following is the content of file data A4 Q2 1.txt. The first 3 is the n. The two matrices are (a) and (b) in Figure 10.11 on page 380. Please see the figure for the meaning of the matrices. 3 2 1 3 2 3 1 3 2 1 2 3 1 3 1 2 2 3 1 Program output can be something like 1 0 0 0 0 1 0 1 0 with the 1 at row i and column j representing pairing i and j. • File data A4 Q2 2.txt contains the data of Q4 in Exercises 10.4 in the textbook. Solution to this exercise has been posted on Moodle. Note: You can develop your programs using any C system, as long as your programs can be correctly compiled and executed on the Linux system in SoCS. You are allowed to use standard library functions. Your programs should be submitted as a tar file containing your program files and readme and makefile. The readme file should contain a brief description of how to compile and run each program. Any compilation error or 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 name. 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. Your programs are not required to report running time. 2 coding information published in this undergraduate calendar outlines the rules curricula programs and fees for the academic year including the semester the fall semester and the winter semester for your the undergraduate calendar is available in format if you wish to link to undergraduate calendar please refer to the link guidelines the university a full member of the association of universities and college of canada university of guelph the information published in this undergraduate outlines the rules regulations curricula programs and fees for the academic year including the summer semester the fall semester and winter semester the university reserves the right to change without any information contained in this calendar including fees any rule or pertaining to the standards for admission to the requirements for the of study in and the requirements for the granting of degree or diplomas in or all of its programs the publications of information in this calendar each bind the university to the provision of courses programs schedule of or facilities as list herein the university will not be liable for any in or cancellation of any academic activities as set forth in this calendar related information where such interruption is cause by fire strike inability to process material or trades restrictive laws or governmental act taken by faculty staff or students of the university or by other unrest or disobedience public health emergencies or any other cause of any beyond the reasonable control of the university in the event of a discrepancy a print version downloaded and the web version the web version will apply by enrolment service introduction collection use and disclosure of personal personal information is collected under the authority of the university of act and in accordance with ontario is freedom of information and of privacy act laws on index html this information used by university officials in order to carry out their authority academic administrative responsibilities and also to establish a relationship for alumni development purposes certain personal information is disclosure to external including the ontario universities application centre the ministry of college and universities and statistics canada for statistical and planning and is disclosure to other individual or organization in accordance with the of registrarial services department policy on the release of student for detail on the use and disclosure of this information call the office of services at the university at or see disclosure of personal information to the ontario ministry of training and universities the university of guelph is required to disclosure personal such as characteristics and education outcomes to the minister of training and universities under of the ministry of training college and act chapter as amendments the ministry collect this data purposes including but not limited to planning allocating and administering funding to college universities and other post secondary education and institution amendments made to the act authorizing the collection and of personal information from college and universities by the minister of college and universities which were set out in schedule of the childcare act campus into force on march the amendments strengthen the of the minister to directly or indirectly collect and use personal information students as required to conduct research and analysis including longitudinal and statistical activities conducted by or on behalf of the ministry for that relate to post secondary education and training including information the university is required to provide includes but is not limited to first and last name ontario education number citizenship date of birth gender digits of a student is postal code mother tongue degree program and major students which the student is enrolled year of study and whether the student has from another institution further information on the collection and use of enrolment related data can be obtained from the ministry of training college universities website english or french or by writing to the director post secondary finance and information branch post secondary education division the floor block bay toronto on an update on institutional and notice of disclosure is posted at on publications notice of frequently asked questions related to the ministry school enrolment and data are also posted at publications to disclosure personal information to statistics canada the ministry of college and universities disclosure student level enrolment related data it from the college and universities as required by statistics canada with section of the federal statistics act this gives authority to personal information in accordance with of notification of of personal information to statistics canada for further information please the statistics canada school web site at and section canada address for university communication depending on the nature and of the communication the university may use one of these address to with students students are therefore responsible for checking all of the on a regular basis email address the university issued email address is an official means of communication with the student and will be used for from the university students are responsible for monitoring their email account regular see section i statement of students academic for more information home address students are responsible for maintaining a mailing address with the university address change can be made in writing enrolment services name change the university of guelph is committed to the of its student record therefore each student is required to provide either application for admission or on personal data form required for registration complete legal name any requests to change a name by means of alteration substitution or addition must be accompanied by appropriate support student confidentiality and release of student information policy excerpt the undertakes to protect the privacy of each student and the confidentiality of or her record to this end the university shall refuse to disclosure personal any personal other than the individual to whom the information relates where would constitute an unjustified invasion of the personal privacy of that or of any other individual all member of the university community must the confidential nature of the student information which they acquire in the of their work complete policy at learning outcomes