Data Structures

National University of Computer & Emerging Sciences (NUCES), Islamabad Department of Computer Science 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

1 5 8 9

Now inserting number 6 in an array Updated Array 1 5 6 8 9 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

2 4 4 5 6 7 7 7 2 4 5 6 7

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} National University of Computer and Emerging Sciences Islamabad

National University of Computer & Emerging Sciences (NUCES), Islamabad Department of Computer Science 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

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

Input index 2 and 11 Resultant Array

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

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

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

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

National University of Computer and Emerging Sciences Islamabad

National University of Computer & Emerging Sciences (NUCES), Islamabad Department of Computer Science 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

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

Resultant Array

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

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

National University of Computer and Emerging Sciences Islamabad