file attached
1. Money change
· O(k)
2. AscII abacdaacac
3. Adjacy list
4. Asymptotic growth (4n cube+15nsquare+11n/n power 6)
· Theta(4ncube+15nsquare+11n/6)
· Theta(4ncube+n square+ n)
· Theta( 1500 n square)
· Theta ( n power 6)
5. Quick sort, don’t control over size of recursive call
6. Quick sort is based on divide and conquer paradigm. In the combine step of divide and conquer process
· Work is needed to combine sub-arrays, the array is already sorted
· No Work is needed to combine sub-arrays, the array is already sorted
· Merging the arrays
· Dividing the arrays
7. Counting sort assumes that the number to be stored are in the range_________
· 1 to k where k is small
· K to n where k is small
· K to n where n is small
· K to n where n is large
8. Catalan for
9. If we encode and compress text using ASCII standard each character is represented by
· Fixed length code word of 4 bits
· Variable length code word up to 4 bits
· Fixed length code word of 8 bits
· Variable length code word up to 8 bits
10. Huffman algorithm finds
· Some time optimal some time non-optimal solution
· Space wise optimal and time wise non optimal solution
· A non-optimal solution
· An optimal solution
11. The Huffman algorithm belongs to
· The class of exponential algorithm
· Class of non-polynomial algorithm
· Space wise to polynomial algorithm but time wise exponential algorithm
· Space and time wise polynomial algorithm
12. Huffman algorithm time complexity
· Can be improved up to O(nlogn)
· Can be improved up to O( underroot n log n)
· Is always O( n square)
· Is always O( n cube)
13. An adjacy matrix for a graph
· Always square in shape
· It is not necessary for it to be square in shape
· Is square in shape for directed graph but not for undirected graphs
· Is always diagonal matric
14. In digraph
· Is in degree attach to the vertex
· Is out degree attach to the vertex
· is a degree attach to the vertex
· both in and out degree attached to the vertex
15. in undirected graphs there
· are no cross edge but forward and back edge
· are only forward edge
· is convention of only back edges
· is convention of forward edges
16. precedence constraint graph is
· non-acyclic directed graph
· non-acyclic undirected graph
· acyclic undirected graph
· acyclic directed graph
17. kurskal’s algorithm
· choose best non-cycle edge
· choose the best tree edge
· choose the vertex that gives the lightest weight
· follow the DP rules for choosing edges
18. in prim’s algorithm, the additional information maintained by the algorithm is
· the length of the shortest path from vertex V to the vertex u
· the length of the shortest edge from vertex v to point already in tree
· the DP rules
· the information about all adjacent vertices
19. Adding any edge to free tree
· Keep it free tree and increase the size of the tree
· Create a unique cycle
· Not allow to add edge to free tree
· Create multiple cycles
20. G power T for graph can be computed in
· Theta(VE)
· Theta(V log E)
· Theta(E log V)
· Theta (V + E)
21. Which of the following not true about dijkstra algorithm
· The length of shortest path to start vertex is always zero
· It can find the shortest path to all other vertices in the same worst case time that it need to find the shortest path to a single vertex
· It will work on any weighted graph with positive weights
· Running time of bell algorithm is greater than dijkstra algorithm
22. Kruskal is used for
· Calculating shortest path problem
· Calculating MST
· Both can be calculated by it
· Single source shortest path problems
23. Shortest path information is propagated sequentially along each shortest path in
· Prims algorithm
· Dijsktra algorithm
· Bell algorithm
· Kruskal algorithm
24. Complexity wise the comparison based merge and quick sort algorithm fall in
· Deterministic polynomial class
· Non-deterministic polynomial class
· Quick in P class and merge in NP class
· Quick in NP class and merge in P class
25.
Tags:
Thanks ... Amna...
© 2021 Created by + M.Tariq Malik. Powered by
Promote Us | Report an Issue | Privacy Policy | Terms of Service
We non-commercial site working hard since 2009 to facilitate learning Read More. We can't keep up without your support. Donate.
We are user-generated contents & non-commercial site. All product, videos, pictures & others contents on site don't seem to be beneath our Copyrights & belong to their respected owners & freely available on public domains. All Contents on site are for personal & non-commercial use.We believe in Our Policy & do according to them. If Any content is offensive in your Copyrights then please email at m.tariqmalik@gmail.com with copyright detail & We will happy to remove it immediately.
Management: Admins ::: Moderators
Awards Badges List | Moderators Group
All Members | Featured Members | Top Reputation Members | Angels Members | Intellectual Members | Criteria for Selection
Become a Team Member | Safety Guidelines for New | Site FAQ & Rules | Safety Matters | Online Safety | Rules For Blog Post