Fall XXXXXXXXXXAlgorithm Development and Data Structures Assignment 3 Special Instructions: · All assignment shall be submitted by the deadline. Late submissions will be penalized with 10% per day for...

in file(attached)


Fall 2021- 20025 Algorithm Development and Data Structures Assignment 3 Special Instructions: · All assignment shall be submitted by the deadline. Late submissions will be penalized with 10% per day for up to 3 calendar days after which the assignment cannot be submitted anymore. An email must be sent should you choose to submit a late assignment. · This assignment is a Group and an Individual work. · Even partially copied code will be subject to regulations against academic integrity. Do NOT discuss or share your solution with anybody. Posting this assignment or solution on the Internet is a violation of the Student Code of Conduct. See the Academic Honesty at Sheridan. · Deductions will be applied if partial functionality is provided. · You’ll get zero grade if your code doesn’t compile. · Compilation warnings are considered to be major mistakes. · Two submission please · · A document file named PROG20025_AS__ that includes answers for part 1 . Each student has to answer and submit this question individually. This is to be submitted to Assignment 3-individual Dropbox on Slate. · one.zip folder named appropriately as PROG20025_ASG__.zip., containing: · A document file that includes discussion for part 2: · A well-documented program file for second question. Make sure your program has no compilation error and is correct. Copy your program to text file named [q2.txt] containing your code and include a program header (I.e., a block comment at the top with your name, date, description of program). · Submission is done in electronic format using SLATE DropBox. DO NOT email your submission. Due date for the submission is week . · This assignment has 2 questions on 5 pages. The assignment is out of 100. Part 1 – INDIVIDUAL WORK : BST, BBST and Sorting Understanding and Applying-[50 Marks] a.[15 Marks] - Show in the style given in the class, how the last 5 digits of your student number (e.g. 123456789) will be inserted in the following ADT-Please make sure to change these digits to be unique digits: · Binary Search Tree-[5 Marks]. · Red-Black Tree-[10 Marks]. Show your Tree after you insert a number to the tree. b. Show in the style given in the class, how the last 5 digits of your student number (e.g. 123456789) will be sorted using the following sorting algorithms- Please make sure to change these digits to be unique digits: a. Selection sort-[5 Marks]. b. Quick sort-[5 Marks]. c. Merge sort-[5 Marks]. c. You need to design TWO algorithms in Pseudo code that takes N numbers (size of input) in array A and counts the number of distinct values in A. a. First algorithm will do the count without using any sorting algorithms -[5 Marks]. b. Second algorithm counts the number of distinct values in the array with using any sorting algorithms- [5 Marks]. c. What is the complexity of the designed algorithm? Explain your answer-[10 Marks]. Part 2- GROUP WORK : Binary Search Tree Empirical and Theoretical Results Part 1: You need to define a binary search tree data structure . Also, you need to implement the following functions: 1. Insert Sorted · BSTREE insert(BSTREE root, int num): root points to a node in a binary search tree; num is a number to be inserted in the tree rooted at “root”. This function returns the root of the modified tree. 2. Print Elements · void inorderTraversal(BSTREE root, FILE *fp): root points to a node in a binary search tree. This function does not return anything, but prints out, to the file specified, the nodes in the tree rooted at “root” by performing an inorder traversal. Part 2: Test the performance of the designed data structure using theoretical and experimental approaches as follows: 1. Dataset 1-Dataset is sorted- Add code to insert the numbers 1...n in that order in an initially empty doubly linked list and a binary search tree. a. Run it on different values of n where : i. n = 20,000 ii. n = 50,000 iii. n = 100,000 b. Do an in-order traversal of the tree, printing out the contents to a file (named “sorted”) to verify that you indeed built the data structure correctly. c. Note the time for each program executions to just build the data structure (i.e., don’t include printing in the time) and include the timings in your report. For each n, you must run it 3 times and then take the average time. Don’t forget to submit all your data though. d. Report the results of the analyzed algorithms for each data structure using the Big-O and the timings. 2. Dataset 2-Dataset is random - Add code to read in values from “dataToBuildDS.txt” and properly insert them in an initially empty doubly linked list and binary search tree. 1. Run your program on different values of n by doing the following: · Read in the first 20,000 entries only found in “dataToBuildDS.txt” · Read in the first 50,000 entries only found in “dataToBuildDS.txt” · Read in the first 100,000 entries only found in “dataToBuildDS.txt” 2. Do an in-order traversal of the tree, printing out the contents to a file (named “unsorted”) to verify that you indeed built the data structure correctly. 3. Note the time to build the data structure. For each n, you must run it at least 3 times and then take the average. Include all timings as well as the average in your report. 4. Report the results of the analyzed algorithms for each data structure using the Big-O and the timings. Your Answer should include the following parts : · [25 marks] Implementation of the data structures that shows the experimental study in timings for the datasets for insertion and print algorithms for each data set. · [25 marks] Report: · Describe the data structure [BST] and algorithms [insert, find and print] in pseudocode. · Comparison in terms of: · Big-O and datasets for insert and print · Timings and datasets for insert and print Assignment 3 Grading Page Group Number Please add your group number Students Please add student names Max Mark Mark Part 1-[50 marks] Binary Search Tree 5 5 Red-Black Tree 10 10 Sorting algorithms 15 15 Design algorithms 20 20 Part 2- Experimental Study[25 marks] Documentation including a Program header with names 5 5 Implementation of the Binary Search Tree 5 5 Perform Insert elements correctly 5 5 Perform print the elements correctly in files 5 5 Record 3 runs for Dataset 1+ Dataset2 and calculate timings for 2 datasets. 5 5 Part 2- Discussion and Comparisons[25 marks] Pseudocode algorithms for insert and print for binary search tree. 5 5 Discuss and compare between 2 datasets in terms of Big O for insert and print 10 10 Discuss and compare between the 2 datasets in terms of Timings for insert and print 10 10 Fail to follow submission guidelines(-10%) 0 0 Poor communication and presentation document organization (-10%), layout (-10%) spelling (-10%), title page (-10%) 0 0 Late submission -10% per day 0 0 Total 100 100 Comments 1