Course Code : MCS-021
Course Title : Data and File Structures
Assignment Number : MCA(2)/021/Assign/2010
Maximum Marks : 100
Weightage : 25%
Last Dates for Submission : 15th October, 2010 (for July, 2010 session)
15th April, 2011 (for January, 2011 session)
BCA MCA Bsc B tech CS information technology
final year project
This assignment has three questions, which carry 80 marks. Answer all the questions. Viva-voce carries 20 marks. You may use illustrations and diagrams to enhance the explanations. Please go through the guidelines regarding assignments given in the Programme Guide. Ensure that you don’t copy the program from course material or any other source. All the implementations should be in C language.
Question 1:
An alternative linked representation for sparse matrices uses nodes that have the fields down, right, row, col, and value. Each nonzero entry of the sparse matrix is represented by a node. The zero terms are not explicitly stored. The nodes are linked together to form two circular lists. The first list, the row list, is made up by linking nodes by rows and within rows by columns using the right field. The second list, the column list, is made up by linking nodes via the down field. In this list, nodes are linked by columns and within columns by rows. These two lists share a common header node. In addition, a node is added to contain the dimensions of the matrix.
(a) Write any 5 X 8 matrix that has exactly nine nonzero terms such that at least one nonzero term appears in each row and each column. For this sparse matrix, draw the linked representation. (10 Marks)
(b) Suppose that an m X n matrix with t non-zero terms is represented as above. How small must t be so that the above linked scheme uses less space than an m X n array uses?
(10 Marks)
(c) Design a suitable external (i.e. one that can be used for input and output) representation for a sparse matrix. Your representation should not require explicit input of the zero terms. (10 Marks)
Question 2:
Draw two binary trees whose preorder listing is abcdefgh and whose postorder listing is dcbgfhea. Also, list the nodes of binary trees in inorder and level order. (25 Marks)
Question 3:
Suppose that an undirected Graph is represented with the array adjacency list representation. Write an algorithm to remove the an edge from G. What is the time complexity of the algorithm.
(25 Marks)
Course Title : Data and File Structures
Assignment Number : MCA(2)/021/Assign/2010
Maximum Marks : 100
Weightage : 25%
Last Dates for Submission : 15th October, 2010 (for July, 2010 session)
15th April, 2011 (for January, 2011 session)
BCA MCA Bsc B tech CS information technology
final year project
This assignment has three questions, which carry 80 marks. Answer all the questions. Viva-voce carries 20 marks. You may use illustrations and diagrams to enhance the explanations. Please go through the guidelines regarding assignments given in the Programme Guide. Ensure that you don’t copy the program from course material or any other source. All the implementations should be in C language.
Question 1:
An alternative linked representation for sparse matrices uses nodes that have the fields down, right, row, col, and value. Each nonzero entry of the sparse matrix is represented by a node. The zero terms are not explicitly stored. The nodes are linked together to form two circular lists. The first list, the row list, is made up by linking nodes by rows and within rows by columns using the right field. The second list, the column list, is made up by linking nodes via the down field. In this list, nodes are linked by columns and within columns by rows. These two lists share a common header node. In addition, a node is added to contain the dimensions of the matrix.
(a) Write any 5 X 8 matrix that has exactly nine nonzero terms such that at least one nonzero term appears in each row and each column. For this sparse matrix, draw the linked representation. (10 Marks)
(b) Suppose that an m X n matrix with t non-zero terms is represented as above. How small must t be so that the above linked scheme uses less space than an m X n array uses?
(10 Marks)
(c) Design a suitable external (i.e. one that can be used for input and output) representation for a sparse matrix. Your representation should not require explicit input of the zero terms. (10 Marks)
Question 2:
Draw two binary trees whose preorder listing is abcdefgh and whose postorder listing is dcbgfhea. Also, list the nodes of binary trees in inorder and level order. (25 Marks)
Question 3:
Suppose that an undirected Graph is represented with the array adjacency list representation. Write an algorithm to remove the an edge from G. What is the time complexity of the algorithm.
(25 Marks)
No comments:
Post a Comment