Algorithms in C++,
The duke
fwdalgorithmsinc.zipUser_42751212015Module1and2pagestocompetework.pdf
User_42751212015Module1and2pagestocompetework_1.pdf
User_42751212015Module2Homework(CIS330).docx
[INSERT TITLE HERE] 1
Running head: [INSERT TITLE HERE]
[INSERT TITLE HERE]
Student Name
Allied American University
Author Note
This paper was prepared for [INSERT COURSE NAME], [INSERT COURSE ASSIGNMENT] taught by [INSERT INSTRUCTOR’S NAME].
Directions: Please complete each of the following exercises. Please read the instructions carefully.
For all “short programming assignments,” include source code files in your submission.
1. Short programming assignment. Combine the malloc2D function of program 3.16 with the adjacency matrix code of program 3.18 to write a program that allows the user to first enter the count of vertices, and then enter the graph edges. The program should then output the graph with lines of the form:
There is an edge between 0 and 3.
2. Short programming assignment. Modify your program for question 2.1 so that after the adjacency matrix is created, it is then converted to an adjacency list, and the output is generated from the list.
3. Short programming assignment. Modify program 4.7 from the text, overloading the == operator to work for this ADT using a friend function.
4. Is the ADT given in program 4.7 a first-class ADT? Explain your answer.
5. Suppose you are given the source code for a C++ class, and asked if the class shown is an ADT. On what factors would your decision be based?
6. How does using strings instead of simple types like integers alter the O-notation of operations?
User_42751212015Module1Homework(CIS330)Corrected (1).docx
[INSERT TITLE HERE] 1
Running head: [INSERT TITLE HERE]
[INSERT TITLE HERE]
Student Name
Allied American University
Author Note
This paper was prepared for [INSERT COURSE NAME], [INSERT COURSE ASSIGNMENT] taught by [INSERT INSTRUCTOR’S NAME].
Directions: Please refer to your textbook to complete the following exercises.
1. Refer to page 12 of your text to respond to the following:
Show the contents of the id array after each union operation when you use the quick find algorithm (Program I.I) to solve the connectivity problem for the sequence 0-2, 1-4, 2-5, 3-6, 0-4, 6-0, and 1-3. Also give the number of times the program accesses the id array for each input pair.
2. Refer to page 12 of your text to respond to the following:
Show the contents of the id array after each union operation when you use the quick union algorithm (Program I.I) to solve the connectivity problem for the sequence 0-2, 1-4, 2-5, 3-6, 0-4, 6-0, and 1-3. Also give the number of times the program accesses the id array for each input pair.
3. Refer to figures 1.7 and 1.8 on pages 16 and 17 of the text. Give the contents of the id array after each union operation for the weighted quick union algorithm running on the examples corresponding to figures 1.7 and 1.8
4. For what value is N is 10N lg N>2N2?
5. Prove that O(1) is the same as O(2)
6. You are given the information that the time complexity of one problem is N log N and that the time complexity of another problem is N3. What does this statement imply about the relative performance of specific algorithms that solve the problems?
