Savitribai Phule Pune University, Pune
Second Year of Computer Engineering (2015 Course)
210247: Data Structures Lab
 Teaching Scheme
 Credit
 Examination Scheme
 PR: 04 Hours/Week
 02
 TW: 25 Marks
PR: 50 Mark
 Guidelines for Instructor's Manual The instructor‘s manual is to be developed as a handson resource and reference. The instructor's manual need to include prologue (about University/program/ institute/ department/foreword/ preface etc), University syllabus, conduction & Assessment guidelines, topics under considerationconcept, objectives, outcomes, set of typical
applications/assignments/ guidelines, and references.
 Guidelines for Student Journal The laboratory assignments are to be submitted by student in the form of journal. Journal consists of prologue, Certificate, table of contents, and handwritten writeup of each assignment (Title, Objectives, Problem Statement, Outcomes, software & Hardware requirements, Date of Completion, Assessment grade/marks and assessor's sign, Theory Concept in brief, algorithm, flowchart, test cases, conclusion/analysis. Program codes with sample output of all performed assignments are to be submitted as softcopy.
 As a conscious effort and little contribution towards Green IT and environment awareness, attaching printed papers as part of writeups and program listing to journal may be avoided. Use of DVD containing students programs maintained by lab Incharge is highly encouraged.

 For reference one or two journals may be maintained with program prints at Laboratory.


 Guidelines for Assessment Continuous assessment of laboratory work is to be done based on overall performance and lab assignments performance of student. Each lab assignment assessment will assign grade/marks based on parameters with appropriate weightage. Suggested parameters for overall assessment as well as each lab assignment assessment include timely completion, performance, innovation, efficient codes, punctuality and neatness.

Guidelines for Laboratory Conduction The instructor is expected to frame the assignments by understanding the prerequisites, technological aspects, utility and recent trends related to the topic. The assignment framing policy need to address the average students and inclusive of an element to attract and promote the intelligent students. The instructor may set multiple sets of assignments and distribute among batches of students. It is appreciated if the assignments are based on real world problems/applications. Encourage students for appropriate use of Hungarian notation, Indentation and comments. Use of open source software is to be encouraged. For all lab assignments instruct students to minimize the number of operations, test against all test cases. In addition to these, instructor may assign one real life application in the form of a mini project based on the concepts learned. Instructor may also set one assignment or miniproject that is suitable to respective branch beyond the scope of syllabus. Set of suggested assignment list is provided in groups A, B, C, D, and E. Each student must perform at least 13 assignments as at least 3 from group A, 3 from group B, 2 from group C,
2 from group D and 3 from group E. Operating System recommended : 64bit Open source Linux or its derivative
Programming tools recommended:  Open Source C++ Programming tool like G++/GCC
 Suggested List of Laboratory Assignments
 Group A
 1.
 Second year Computer Engineering class, set A of students play cricket and set B of
students play badminton. Write C/C++ program to find and display
i. Set of students who play either cricket or badminton or both ii. Set of students who play both cricket and badminton
iii. Set of students who play only cricket
iv. Set of students who play only badminton
v. Set of students who play neither cricket nor badminton
(Note While realizing the set duplicate entries are to avoided)
 2.
 Write C/C++ program to store marks scored for first test of subject 'Data Structures
and Algorithms' for N students. Compute
I. The average score of class
ii. Highest score and lowest score of class iii. Marks scored by most of the students
iv. list of students who were absent for the test
 3.
 Department library has N books. Write C/C++ program to store the cost of books in
array in ascending order. Books are to be arranged in descending order of their cost. Write function for
a) Reverse the contents of array without using temporary array.
b) Copy costs of books those with cost less than 500 in new array c) Delete the duplicate entries using temporary array
d) Delete duplicate entries without using temporary array e) Count number of books with cost more than 500.
 4.
 It is decided that weekly greetings are to be furnished to wish the students having their
birthdays in that week. The consolidated sorted list with desired categorical information is to provide to authority. Write C++ program for array of structures to

 store students PRNs with date and month of birth. Let Array_A and Array_B be the
two arrays for two SE Computer divisions. Arrays are sorted on date and month. Merge these two arrays into third array Array_SE_Comp_DOB resulting in sorted information about Date of Birth of SE Computer students.
 5.
 A magic square is an n * n matrix of the integers 1 to n^{2}^{ }such that the sum of each row,
column, and diagonal is the same. The figure given below is an example of magic square for case n=5. In this example, the common sum is 65. Write C/C++ Program for magic square.

 15
 8
 1
 24
 17

 16
 14
 7
 5
 23
 22
 20
 13
 6
 4
 3
 21
 19
 12
 10
 9
 2
 25
 18
 11
 6.
 An m x n matrix is said to have a saddle point if some entry a[i][j] is the smallest
value in row i and the largest value in j. Write C/ C++ function that determines the location of a saddle point if one exists.
 7.
 Write C/C++ program for storing matrix. Write functions for
a) Check whether given matrix is upper triangular or not b) Compute summation of diagonal elements
c) Compute transpose of matrix
d) Add, subtract and multiply two matrices
 8.
 Write C++ program with class for String. Write a function
frequencythat determines the frequency of occurrence of particular character in the string.
deletethat accepts two integers, start and length. The function computes a new string that is equivalent to the original string, except that length characters being at start have been removed.
chardeletethat accepts a character c. The function returns the string with all occurrences of c removed.
replace to make an inplace replacement of a substring w of a string by the string x. note that w may not be of same size of x
_{}_{ }_{pal}_{i}_{ndrome}_{ }_{to ch}_{ec}_{k w}_{h}_{e}_{ther}_{ }_{g}_{i}_{v}_{e}_{n string}_{ }_{is }_{p}_{a}_{l}_{i}_{ndrome}_{ }_{or n}_{o}_{t}
 9.
 Write C++ program for sparse matrix realization and operations on it Transpose, Fast
Transpose and addition of two matrices
 10.
 Write a C++ program to realize polynomial equation and perform operations. Write
_{fun}_{c}_{t}_{i}_{on}
^{a}^{) }^{T}^{o input}^{ }^{a}^{nd output}^{ }^{po}^{l}^{y}^{nom}^{i}^{a}^{ls r}^{e}^{p}^{r}^{e}^{s}^{e}^{nted}^{ }^{a}^{s }^{b}m^{x}^{e}^{m}^{+}^{ }^{b}m1^{x}^{e}^{m}^{}^{1}^{ }^{+}^{…..}^{ }^{+}^{b}0^{x}^{e}^{0}^{.}
^{Your}^{ f}^{un}^{c}^{t}^{i}^{ons sho}^{u}^{ld ove}^{r}^{load the}^{ }^{<}^{<}^{ a}^{nd }^{>}^{>}^{ }^{op}^{e}^{r}^{a}^{t}^{o}^{rs.}
b) Evaluates a polynomial at given value of x c) Add two polynomials
d) Multiplies two polynomials
 Group B
 11.
 Department of Computer Engineering has student's club named 'Pinnacle Club'.
Students of Second, third and final year students of department can be granted membership on request. Similarly one may cancel the membership of club. The list is sorted on PRN of student. First node is reserved for president of club and last node is reserved for secretary of club. Write C++ program to maintain club member‘s

 information using singly linked list. Store student PRN and Name. Write functions to
a) Add and delete the members as well as president or even secretary. b) Compute total number of members of club
c) Display members
d) Display list in reverse order using recursion
e) Two linked lists exists for two divisions. Concatenate two lists.
 12.
 The ticket booking system of Cinemax theater has to be implemented using C++
program. There are 10 rows and 7 seats in each row. Doubly circular linked list has to be maintained to keep track of free seats at rows. Assume some random booking to start with. Use array to store pointers (Head pointer) to each row. On demand
a) The list of available seats is to be displayed b) The seats are to be booked
c) The booking can be cancelled.
 13.
 Write C++ program for storing appointment schedule for day booked randomly. Set
start and end time and min and max duration for visit slot such as 20 minutes or 1 hour
. Write functions for a) Display free slots b) Book appointment
c) Cancel appointment
( check validity, time bounds, availability etc)
d) Sort list based on time
e) Sort list based on time using pointer manipulation
 14.
 Second year Computer Engineering class, set A of students like Vanilla Icecream and
set B of students like butterscotch icecream. Write C/C++ program to store two sets using linked list. compute and display
vi. Set of students who like either vanilla or butterscotch or both vii. Set of students who like both vanilla and butterscotch
viii. Set of students who like only vanilla not butterscotch ix. Set of students who like only butterscotch not vanilla
x. Set of students who like neither vanilla nor butterscotch
 15.
 Write C++ program to store set of negative and positive numbers using linked list.
Write functions
a) Insert numbers
b) Delete nodes with negative numbers
c) To create two more linked lists using this list, one containing all positive numbers and other containing negative numbers
d) For two lists that are sorted; Merge these two lists into third resultant list that is sorted
 16.
 Write C++ program for storing binary number using doubly linked lists. Write
functions
a) to compute 1‘s and 2‘s complement
b) add two binary numbers
 17.
 Let x = (x1,x2, … , xn) and y = (y 1, y2,…. , ym) be two doubly linked lists. Assume that
in each linked list, the nodes are in nondecreasing order of their datafield values.
Write an algorithm to merge the two lists to obtain a new linked list z in which the nodes are also in this order. Following the merge, x and y should represent empty lists because each node initially in x or y is now in z. No additional nodes may be used.
 18.
 Design a linked allocation system to represent and manipulate univariate polynomials
with integer coefficients (use circular linked lists with head nodes). Each term of the

 polynomial will be represented as a node Thus. a node in this system will have three
data members as below:
Exponent Link
Coefficient To erase polynomials efficiently, we need to use an availablespace list and associated functions. The external (i.e.. for input or output) representation of a univariate polynomial will be assumed to be a sequence of integers of the form: n, c1, e1 ,c2. e2. c3. e 3 . . , cn en where ei represents an exponent and ci a coefficient; n gives the number of
terms in the polynomial. The exponents are in decreasing order — i.e., e1> e2> …. >en.
Write and test the following functions:
1. istream&operator >>(istream& is, Polynomial& x): Read in an input polynomial and convert it to its circular list representation using a head node.
2. ostream&operator<< (ostream&os, Polynomial& x): Convert x from its linked list representation to its external representation and output it.
3. Polynomial:: Polynomial(const Polynomial& a) [Copy Constructor]: Initialize the polynomial *this to the polynomial a.
4. const Polynomial& Polynomial :: operator=(const Polynomial& a) [Assignment Operator]: Assign polynomial a to*this.
5. Polynomial:: Polynomial ( ) [Destructor]: Return all nodes of the polynomial
*this to the availablespace list.
6. Polynomial operator+ (const Polynomial& a, const Polynomial& b) [Addition]: Create and return the polynomial a + b. a and b are to be left unaltered.
7. Polynomial operator (const Polynomial& a, const Polynomial& b) [Subtraction] : Create and return the polynomial a  b. a and b are to be leftunaltered.
8. Polynomial operator* (constPolynomial& a, constPolynomial& b) [Multiplication]: Create and return the polynomial a * b. a and b are to be left unaltered.
9. floatPolynomial ::Evaluate(float x): Evaluate the polynomial *this at x and return the result.
 19.
 Write C++ program to realize Set using Generalized Liked List (GLL) e.g A ={ a, b,
{c, d,e, {}, {f,g}, h, I, {j,k}, l, m}. Store and print as set notation.
 Group C
 20.
 A palindrome is a string of character that‘s the same forward and backward. Typically, punctuation, capitalization, and spaces are ignored. For example, ‖Poor Dan is in a droop‖ is a palindrome, as can be seen by examining the characters ―poor danisina droop‖ and observing that they are the same forward and backward. One way to check for a palindrome is to reverse the characters in the string and then
compare with them the originalin a palindrome, the sequence will be identical. Write
C++ program with functions
1. to check whether given string is palindrome or not that uses a stack to determine whether a string is a palindrome.
2. to remove spaces and punctuation in string, convert all the Characters to lowercase, and then call above Palindrome checking function to check for a palindrome
3. to print string in reverse order using stack
 21.
 In any language program mostly syntax error occurs due to unbalancing delimiter such

 as (),{},[]. In a given expression while (m<(n[8]+0)), the first opening parenthesis
matched with the last closing parenthesis, but this is done after the second opening parenthesis is matched with the next to last closing parenthesis, this, in turn, is done after the opening square bracket is matched with the closing bracket. Here, identify the data structure needed to implement delimiter matching program to display the given statement is balanced/ well parenthesis or not. Write C++ program using stack to check whether given expression is well parenthesized or not.
 22.
 Implement C++ program for expression conversion as infix to postfix and its
evaluation using stack based on given conditions
i. Operands and operator, both must be single character. ii. Input Postfix expression must be in a desired format. iii. Only '+', '', '*' and '/ ' operators are expected.
 23.
 Implement C++ program for expression conversion as infix to prefix, prefix to postfix,
prefix to infix, postfix to infix and postfix to prefix.
 24.
 A classic problem that can be solved by backtracking is called the Eight Queens
problem, which comes from the game of chess. The chess board consist of 64 square arranged in an 8 by 8 grid. The board normally alternates between black and white square, but this is not relevant for the present problem. The queen can move as far as she wants in any direction, as long as she follows a straight line, Vertically, horizontally, or diagonally. Write C++ program with recursive function for generating all possible configurations for 4queen's problem.
 Group D
 25.
 Queues are frequently used in computer programming, and a typical example is the
creation of a job queue by an operating system. If the operating system does not use priorities, then the jobs are processed in the order they enter the system. Write C++ program for simulating job queue. Write functions to add job and delete job from queue.

 b) Write C++ program to store roll numbers of student array who attended training
program in sorted order. Write function for searching whether particular student attended training program or not using binary search.
 30.
 Write C++ program to store names and mobile numbers of your friends in sorted order
on names. Search your friend from list using binary search (recursive and non recursive). Insert friend if not present in phonebook.
 31.
 Write C++ program to store names and mobile numbers of your friends in sorted order
on names. Search your friend from list using Fibonacci search. Insert friend if not present in phonebook.
 32.
 Write C++ program to maintain club members, store roll numbers in ascending order. Write function ‗Ternary_Search‘ to search whether particular student is member of club or not. Ternary search is modified binary search that divides array into 3 halves instead of two.
 33.
 Write C++ program to store first year percentage of students in array. Write function
for sorting array of floating point numbers in ascending order using a) Selection Sort
b) Bubble sort and
 34.
 Write C++ program to store first year percentage of students in array. Write function
for sorting array of floating point numbers in ascending order using a) Insertion sort
b) Shell Sort
 35.
 Write C++ program to store first year percentage of students in array. Write function
for sorting array of floating point numbers in ascending order using quick sort
 36.
 Write C++ program to store first year percentage of students in array. Write function
for sorting array of floating point numbers in ascending order using bucket sort
 37.
 Write C++ program to store first year percentage of students in array. Write function
for sorting array of floating point numbers in ascending order using radix sort
 26.
 In a priority queue, items are added in queue along with a priority, and serves (deletes
from queue) the item with the highest priority. If two items have the same priority then they can be deleted from queue in either order. Priority queues are heavily used in computer system software for example when keeping track of jobs waiting to print on a printer.
Implement a priority queue in C++ using an inorder List to store the items in the queue. Create a class that includes the data items(which should be template) and the priority (which should be int)The inorder list should contain these objects ,with operator <= overloaded so that the items with highest priority appear at the beginning of the list (which will make it relatively easy to retrieve the highest item.)
 27.
 A doubleended queue(deque) is a linear list in which additions and deletions may be
made at either end. Obtain a data representation mapping a deque into a one dimensional array. Write C++ program to simulate deque with functions to add and delete elements from either end of the deque.
 28.
 Pizza parlor accepting maximum M orders. Orders are served in first come first served
basis. Order once placed can not be cancelled. Write C++ program to simulate the system using circular queue using array.
 Group E
 29.
 a) Write C++ program to store roll numbers of student in array who attended
training program in random order. Write function for searching whether particular student attended training program or not using linear search and sentinel search.
 