Data Structure assignment

National University of Computer & Emerging Sciences (NUCES),

Islamabad Department of Computer Science

National University of Computer and Emerging Sciences Islamabad

CS201: Data Structures (Fall 2015)

Assignment # 1

Submission: You are required to submit single .cpp file for all the problems.

Name_roll#_Section .cpp file as (i.e. XYZ_i14000_A.cpp). Submit .cpp file on slate with given

deadline.

Deadline: Deadline to submit assignment is 04 September 11:55 PM. Late submission without

any deduction will be accepted till 05th September 10:00 AM. No submission will be considered

for grading outside slate or after 05th September 10:00 AM. Correct and timely submission of

assignment is responsibility of every student; hence no relaxation will be given to anyone.

Plagiarism: -50% marks in the assignment if any part of assignment is found plagiarized

Note: Write a “main” function to run all the problems given below. Your program shall display

menu that asks uses to run any specific problem. Design of menu should display your aesthetic

sense. Take any size of array what you want but you should generalize your code.

1. Sorted Insert Write a SortedInsert() function which insert the number into an array at correct sorted

position such that array is sorted in increasing order.

Example:

Original Array

Now inserting number 6 in an array

Updated Array

2. Removing duplicates Write a removeDuplicates() function which takes input a sorted list and deletes any

duplicate nodes from the list.

Example:

Original Array

Updated Array

3. Product array Given an array arr[] of n integers, construct a Product Array prod[] (of same size) such

that prod[i] is equal to the product of all the elements of arr[] except arr[i]. Solve it

without division operator and in O (n).

Example: arr[] = {10, 3, 5, 6, 2}

prod[] = {180, 600, 360, 300, 900}

1 5 8 9

1 5 6 8 9

2 4 4 5 6 7 7 7

2 4 5 6 7

National University of Computer & Emerging Sciences (NUCES),

Islamabad Department of Computer Science

National University of Computer and Emerging Sciences Islamabad

4. Reversing Write reverse function which reverses an array between two indexes. Remember if the

function discovers that indexes provided not in the range, it must return 0 otherwise 1.

Example:

Original Array

Input index 2 and 11

Resultant Array

5. Rotating clockwise Write a rotate function which takes input n and shifts elements of an array to the right n

times. Array under consideration is circular.

Example:

1 2 3 11 10 9 8 7 6 5 4 12

Input rotate value: 5

7 6 5 4 12 1 2 3 11 10 9 8

6. Addition In this problem, you have to take two strings of numbers (e.g. 1203 and 201453) from the

user and store each string (number) in a separate array. While storing a number in a array

you have to keep in mind that each digit of that number should be stored in a separate

index. You have to add these two numbers and store answer in a third array digit by

digit.

Example:

0 0 0 0 0 0 0 0 6 5 4 2

0 0 0 0 0 0 0 9 5 0 9 8

+

Note: All the three arrays should be of size 20.

1 2 3 4 5 6 7 8 9 10 11 12

1 2 3 11 10 9 8 7 6 5 4 12

0 0 0 0 0 0 1 0 1 6 4 0

National University of Computer & Emerging Sciences (NUCES),

Islamabad Department of Computer Science

National University of Computer and Emerging Sciences Islamabad

7. Shuffle Merge Write a function named "Shuffle Merge" that copies the elements of both arrays into a

larger array, such that elements of both arrays appear alternatively. If the function

discovers that the number of cells in the large array is not enough to hold all the numbers

that to be copied into it, then the function should return 0 to indicate failure. Otherwise it

should return 1.

Example:

Array 1

Array 2

Resultant Array

8. Print The title is pretty much self-explanatory. You have to Display the array.

1 11 16 7 3 8

9 10 6 5 4 2

1 9 11 10 16 6 7 5 3 4 8 2