关于c++:CSCI-2132-Software-Development
Assignment 7CSCI 2132: Software DevelopmentDue April 8, 2019Assignments are due on the due date before 23:59. All assignments must be submitted electronically via the course SVNserver. Plagiarism in assignment answers will not be tolerated. By submitting your answers to this assignment, you declarethat your answers are your original work and that you did not use any sources for its preparation other than the class notes,the textbook, and ones explicitly acknowledged in your answers. Any suspected act of plagiarism will be reported to theFaculty’s Academic Integrity Officer and possibly to the Senate Discipline Committee. The penalty for academic dishonestymay range from failing the course to expulsion from the university, in accordance with Dalhousie University’s regulationsregarding academic integrity.General Instructions: How to Submit Your WorkYou must submit your assignment answers electronically: Change into your subversion directory on bluenose: cd ~/csci2132/svn/CSID . Create a directory a7 for the current assignment. Change into your assignment directory: cd a7 . Create files inside the a7 directory as instructed in the questions below and put them underSubversion control using svn add <filename> . Only add the files you are asked to add! Once you are done answering all questions in the assignment (or the ones that you are able toanswer—hopefully all), the contents of your a7 directory should look like this:a7permutations.clinked_list.clinked_list.hnode_pool.cnode_pool.hstringset.c(You will also have executable programs and potentially some data files in this directory, but youshould not add them to SVN.) Submit your work using svn commit -m"Submit Assignment 7" .1(Q1) RecursionConsider the sequence of the first n positive integers, ?1,2, . . . , n?. A permutation of this sequence isany sequence that contains each of the numbers 1, 2, . . . , n exactly once. So, ?3, 4, 2,is a permutation of 1, 2, 3, 4 but 1, 3, 2, 3 and 1, 5, 3, 2 are not.A permutation x1 is lexicographically less than another permutation y1 yn if andonly if there exists an index 1 ≤ k ≤ n such that xi = yifor all 1 ≤ i < k and xk < yk.So,2, 1, 3, 4 is lexicographically less than 2, 3, 1, 4 because x1 = y1 = 2 and x2 = 1 < y2 = 3. If theelements in the sequence were letters rather than integers, you could interpret the sequence of lettersas a word and the ordering defined here would simply be the one in which the words would occur in adictionary.Your task is to write a C program permutations that takes a command line argument n and outputsall permutations of the sequence ?1,2, . . . , n? in lexicographic order. The output should consist ofn! lines, each containing one permutation. The numbers in each permutation must be printed inorder, separated by exactly one space between each pair of consecutive numbers. Thus, when runningpermutations 3, you should see the following output on your screen:$ ./permutations 31 2 31 3 22 1 32 3 13 1 23 2 1permutations 4 should produce$ ./permutations 41 2 3 41 2 4 31 3 2 41 3 4 21 4 2 31 4 3 22 1 3 42 1 4 32 3 1 42 3 4 12 4 1 32 4 3 13 1 2 43 1 4 223 2 1 43 2 4 13 4 1 23 4 2 14 1 2 34 1 3 24 2 1 34 2 3 14 3 1 24 3 2 1As the title of the question suggests, recursion is a natural strategy to implement this program. Youshould not have to generate the permutations and then sort them. Your code should be able to generatethe permutations in the desired order.The basic strategy is fairly simple: Your top-level invocation of the function that generates the permutationshould iterate over all possible choices of the first element in the permutation, from smallestto largest. For each such choice, you make a recursive call that generates all permutations of theremaining n 1 elements. How do you do this? You iterate over all possible choices for the secondelement, from smallest to largest and, for each such choice, make a recursive call that generates allpermutations of the remaining n?2 elements, and so on. The deepest recursive call is asked to generatea permutation of 0 elements, that is, you have already chosen all n elements in the permutation. Thisis the point at which you print the current permutation.One issue you will have to deal with is how to keep track of the elements that can still be chosen asthe second, third, fourth, . . . element in the permutationu after choosing the first one, two, three, . . .elements in the permutation. One easy way to do this is to initialize an array of size n that containsall the numbers from 1 to n. Whenever you choose an element from this array, you set its entry to 0and, in subsequent recursive calls, you skip elements that are 0 because they were already chosen.Don’t forget to restore each number x in this array of candidates when it is no longer part of the set ofelements currently chosen as part of the permutation. This is not the most efficient way to do this, butefficiency is not your main concern in this question.Implement your program in a single source file permutations.c. Do not submit the executable fileobtained by compiling it. However, you should obviously compile and test your code.3(Q2) Structs, unions, and dynamic memory managementThe ability to allocate and deallocate memory on the heap at arbitrary times is key to writing flexibleprograms, but every allocation or deallocation has an associated cost because the runtime system oroperating system needs to perform a certain amount of bookkeeping to keep track of which memorylocations on the heap are currently occupied and which ones are available for future allocation requests.As a result, in programs that create and destroy many small objects on the heap, the cost of heapmanagement may become the main performance bottleneck. This is the case in object-oriented programsthat manipulate complex collections of small objects and in the implementation of pointer-based datastructures such as linked lists and binary search trees, where a na?ve implementation represents eachlist or tree node as a separately allocated block on the heap.A common technique to improve the performance of such programs substantially is to allocate largerchunks of memory at a time, large enough to hold hundreds or thousands of the manipulated objects(e.g., a chunk that is big enough to hold 1000 list nodes in a linked list implementation). Your codethen has to manually track which of the slots in this large memory chunk are occupied or not, but thisis a much simpler problem that can be solved much more efficiently than general heap management.The data structure that manages the allocation of individual list nodes from this array of list nodes isoften referred to as a “node pool”.Here, your task is to implement a linked list that uses a node pool to efficiently manage the memoryoccupied by its nodes. As an application, you will use the same test program as in Lab 8, which needsa data structure to store a collection of strings. In Lab 8, you implement this collection as a splay treein order to guarantee fast searches. Here, you do not worry about the speed of searching the datastructure, only about the cost of heap management, so a linked list suffices as the data structure tostore the collection of strings.1Develop your code for this question in four steps: ...