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