Data Structures Assignment

Data Structures Assignment

Problem 1: Count the number of zeros in 69!.

Problem 2: A magic square is a square matrix of integers such that the sum of every row, the sum of every column and sum of each of the diagonal are equal. Such a magic square is shown below: 8 3 4

1 5 9

6 7 2

Write a program to display a magic square.

Problem 3: Determine a suitable representation for polynomials in a single variable based on arrays. A polynomial p(x) is of the form : 5 x - 10 x + 23. Write a program that given p(x) and a point, say x = 1, finds the value of p(x) at that point. For example, the value of the polynomial 5 x - 10 x + 23 at x = 1 is 18. 3

3

Given two polynomials, write different functions for performing polynomial arithmetic involving operations of +, - and *. In other words, write the complete definitions of the following function prototypes : void add ( float *p, degp, float *q, degq, float *res, degres ); void sub ( float *p, degp, float *q, degq, float *res, degres ); void mult ( float *p, degp, float *q, degq, float *res, degres ); where p, q and polynomials with degrees 'degp' and 'degq' respectively and

res is the resulting polynomial of degree degres which holds after the polynomial arithmetic +, -, *

Problem 4: This assignment deals with creating a data structure for large numbers (nonnegative). You have to read from an input file, say, "input", data of the following kind : 980089673400089200098129823 # 120006734009867453400 # 23457689020# 1000000000000000000209 # 34567892 # Note that every big number is followed by a hash(#) symbol as shown above. Moreover the digits of the big number are consecutive ( you may assume this to be always true in the input if that simplifies the design ). Neither the number of digits in a big number is known apriori nor is the number of such large numbers in the input file. Your program should read such an input file and produce a output file of the following form : /* Output From Program */ Big Number 1 : 27 digits : 980089673400098200098129893 Big Number 2 : ....................................... Note that the representation chosen for a big number is to be a linked list each of whose node should contain certain fragments of the large number. A possible representation is outlined below but you may choose a different one if you so please. A node may be defined as i) a short integer and a ii) link. The data of the first node should hold the no. of digits in the number; the data of remaining nodes would store 4 consecutive digits of the large number. The internal representation for the first input number would be: 27 -> 9800 -> 8967 -> 3400 -> 982 -> 9 -> 8129 -> 893 However, when you generate back the number, you have to account for the missing zeros in the above representation. You may choose to read the input as a character array, convert to numbers as you proceed and assemble the linked list.

Problem 5: This assignment deals with creating a multi-linked list data structure for storing and processing student's academic data. To keep the problem simple, this program would deal with only rollnumbers. The kind of roll-numbers we deal with are also restricted as described below. A roll-no comprises of an 8-digit integer. The first 2 digits indicate the year of joining ( E.g. 1998 would be coded as 98, ignore the y2K problem ).

The 3rd , 4th and 5th digits indicate the department where the program is offered. Sample values are given below. 108 : IT 109 : Electronics 104 : Civil 107 : Computer 105 : Elec 102 : Mech

6th digit indicates male or female student. Male=0 and female=1. 7th digit is for category for admission. The last 2 digits denote the serial number of the student. It should be clear from above that given a roll number of a student, one can find out certain details about the student. (a) A list of roll-numbers would be given to you in a file ( say file, "input"); how many such numbers are there are not known apriori. You have to process the roll-numbers and create a multi-linked data structure as explained below : A node of this structure has 3 fields : i) rollno ii) a link field, say dept_link and iii) another link field, say prog_link. The dept_link links this node to another node that has the same dept code ( 4th and 5th digits ). Similarly the prog_link links this node to another node that has the same program code ( 3rd digit ). The last node in the chain for a department or program would have a NULL value respectively. This multi-linked structure would be accessed using 2 arrays, dept array and prog array. Each element of these arrays is of type pointer to node. Note that every rollno exists on two lists, one linked via the dept code and the other linked via the program code. For the following roll-numbers, the data structure to be constructed is shown on a separate page. Input : 041051122 (b) Given a dept code, your program should list all roll nos belonging to that department. Similarly given a program code, your program should list all students registered for the program.

Problem 6: Given a list of integers, construct a binary search tree from the list. You may use any algorithm for constructing the tree. Use a linked list representation for the tree where each node has two pointers, one for the left subtree and the other for the right subtree and an integer field. The binary tree is to be accessed by a pointer to the root of the tree.

a. Use a header file say "btree.h" to place the class definition of a binary tree. Incorporate appropriate function and data members for using a binary tree. A separate main() is to be used for solving the programming problem. b. After constructing the search tree, read in a few values (some which exist in the tree and some which don't ) and search the tree for these values. In case of the value being found, output a string of the form, LLRLR. This string would indicate the path followed from root in the tree leading to the value. For example, the string LRLL for a value say 20 would indicate that 20 was found by proceeding from the root as follows : Left (L); Right(R); Left(L); Left(L). Note that such a string is a unique signature for any element present in the tree. c. Write three non-member functions for inorder, preorder and postorder traversals of a binary search tree. For the tree constructed in part(b)above, show the result of all the three traversals.

Problem 7: This problem deals with polynomials - their representation and simple operations on them. A polynomial would be given as input as described below : o number of terms in the polynomial, say n o n pairs of (coefficient, exponent) values in an arbitrary order For example, the following polynomial : p(x) = 10 x

15

+ 23.8 x

3

+ 1.6 x

-

2.5 may be supplied as :

Number of terms : 4 terms (coeff, exp ) : ( in arbitrary order) 10.0 15 1.6 1 -2.5 0 3.3 3 Given such sparse polynomials, choose a linked list based representation for creating the same. Write functions for the following :  

function that returns the degree of a polynomial functions, addpoly and diffpoly, which implement addition and difference of two input sparse polynomials.

Write a main() and test out your implementation.

Problem 8: An input file, named as, "input", contains data of the following kind : 04980001 q 5 05980005 a 6 04980001 a 3 04980003 q 10 .... Each line of the input file gives for a roll no (9 digit integer) his/her marks (out of 10) in quiz (indicated by q) or in assignment (indicated by a). The roll no’s are not in any order. Each line gives one mark only, either in quiz or assignment. The number of lines of input is not known. Assume that the input file is free of errors. Write a program that creates (a) a linked list of the roll no and quiz marks, call it the quiz list (b) a linked list of the roll no and assignment marks, call it the assignment list (c) merges the two lists to create a new linked list which has both quiz and assignment marks along with the roll no. (d) creates an absentee list for those roll numbers who have scores in one but not the other. An element of this list would have the roll no and a single character, q or a, indicating where the concerned person was absent. The program should display the lists after creating each of the linked lists mentioned above. Also the lists should be organized in the ascending order of roll numbers. Try your program with a sample input file as given below : 980010 a 10 980009 q 2 980005 q 6 980009 a 9 980004 q 6 980025 a 10 980013 q 8 980007 a 6 980004 a 8 980025 q 9 /* Expected Output from the Program - Summary of Marks */ QUIZ LIST Roll No Quiz-marks -----------------------980004 6 980005 6

980009 980013 980025

2 8 9

ASSGN LIST Roll No Assign-marks -----------------------980004 8 980007 6 980009 9 980010 10 980025 10 MARKS LIST Roll No Quiz-marks Assign-marks -----------------------------------980004 6 8 980009 2 9 980025 9 10 ABSENTEE LIST Roll No Absent in -----------------------980005 assgn 980007 quiz .....................

Problem 9:

Companies and people often buy and sells stocks. Often they buy the same stock for different prices at different times. Say a person owns 1000 shares a certain stock (such as Checkpoint); she may have bought the stock in amounts of 100 shares over 10 different times with 10 different prices.

We will analyze two different methods of accounting -- FIFO and LIFO accounting used for determining the "cost" of a stock. This information is typically calculated when a stock is sold to determined if a profit / loss was made. In our version of FIFO accounting, the price of a commodity is averaged starting with the first purchase of that item. Say we sell 250 shares of a stock, according to this method;

the purchase price is determined by averaging the prices on the first 250 shares bought. In our version of LIFO accounting, the price of a commodity is averaged starting with the last purchase of that item. Say we sell 250 shares of a stock, according to this method; the purchase price is determined by averaging the prices on the last 250 shares bought.

In this assignment, you will be using a queue for storing data for Fifo accounting, and a stack for Lifo accounting. You should use an array based implementation for your stack based implementation and a linked list for implementing your queue.

Both your stack and queue should have records with the following fields: The name of the stock (a string or int) The number of shares of a stock (an int) The purchase price (can be a decimal) You can assume that the first element of the structure is the security bought first, the second was bought second, etc.

Your program should have the user able to enter information about various stocks, the amount of shares, and the price. The user can then enter a query about a certain stock and the cost according to the Lifo and Fifo accounting methods for a certain number of shares.

The following could be your menu: Press 1 to enter a new stock Press 2 to find the LIFO and FIFO price for a stock. If 1 is pressed, the user needs to enter the stock symbol, and the number of shares, and the price. If 2 is pressed, the user needs to enter the stock symbol being queried and the number of shares in question.