Comp1927 Assignment

COMP1927 17S1 SORT DETECTIVE LAB Carlos Liang z5059355 - Thursday 1 to 4pm Aim To deduce which sorting algorithm is used by each sort program based on their behavior. Hypothesis At first look, Sort A takes quite long to sort, taking around 2 minutes to sort 250,000 elements which indicates it’s time complexity to be O(n2). As it took less time for ascending than the rest, it is possible that it may be a bubble sort with early exit. At first look, Sort B has performed extremely quickly and thus must be sorts with time complexity O(n*log(n)) or less. Theory The properties of the possible sorting algorithms given: Algorithm Oblivious Bubble Sort Bubble Sort with Early Exit Vanilla Insertion Sort Insertion Sort with Binary Search Vanilla Selection Sort Quadratic Selection Sort Merge Sort Vanilla Quick Sort Quick Sort Median of Three Randomised Quick Sort Shell Sort Powers of Two Shell Sedgewick Bogo Sort Ascending O(n2) O(n) O(n) O(n) Descending O(n2) O(n2) O(n2) O(n2) Random O(n2) O(n2) O(n2) O(n*log(n)) O(n2) O(n*n1/2) O(n*log(n)) O(n*log(n)) O(n*log(n)) O(n*log(n)) O(n) O(n) O(n) O(n2) O(n*n1/2) O(n*log(n)) O(n*log(n)) O(n*log(n)) O(n*log(n)) O((n*log(n))2) O((n*log(n))2) O(n*n!) O(n2) O(n*n1/2) O(n*log(n)) O(n2) O(n2) O(n2) O((n*log(n))2) O((n*log(n))2) O(n*n!) Adaptive No Yes Yes Yes Stable Yes Yes Yes Yes No No No Yes Yes Yes Yes Yes No No No Yes No No No No No No Method Part 1: Time Complexity in Ascending Order 1. After receiving the two sorting programs A and B and created a copy of the data generating program, type the following command into CSE server: ./gen Data Size A | /usr/bin/time --format="%U seconds" ./sort > /dev/null ‘Data Size’ is replaced by the number of integers sorting and ‘sort’ is replaced by the sorting program 2. Repeat step 1, 3 times and write down the average time taken for the sorting program in a table. - This is done to reduce error and increase accuracy in the result as there could be fluctuations in the computer’s sorting performance. pg. 1 3. Repeat steps 1 and 2 but with different data sizes like 100, 1000, 10000, 25000, 75000, 100,000, 250,000, 500,000, 750,000, 1,000,000. - Values chosen should be distinctly apart to easily identify whether the algorithm has time complexity O(n2) or O(n*log(n)). 4. Plot results in a scatter graph with time taken vs data size. 5. Repeat entire process but with Sort B. Part 2: Time Complexity in Descending Order 1. Type the following command into CSE server: ./gen Data Size D | /usr/bin/time --format="%U seconds" ./sort > /dev/null ‘Data Size’ is replaced by the number of integers sorting and ‘sort’ is replaced by the sorting program 2. Repeat step 1, 3 times and write down the average time taken for the sorting program in a table. 3. Repeat steps 1 and 2 but with different data sizes like 100, 1000, 10000, 25000, 75000, 100,000, 250,000, 500,000, 750,000, 1,000,000. 4. Plot results in a line graph with time taken vs number of elements. 5. Repeat entire process but with Sort B. Part 3: Time Complexity in Descending Order 1. Type the following command into CSE server: ./gen Data Size R | /usr/bin/time --format="%U seconds" ./sort > /dev/null ‘Data Size’ is replaced by the number of integers sorting and ‘sort’ is replaced by the sorting program 2. Repeat step 1, 3 times and write down the average time taken for the sorting program in a table. 3. Repeat steps 1 and 2 but with different data sizes like 100, 1000, 10000, 25000, 75000, 100,000, 250,000, 500,000, 750,000, 1,000,000. 4. Plot results in a line graph with time taken vs number of elements. 5. Repeat entire process but with Sort B. Part 4: Stability Test 1. Create a simple txt file where there are duplicate numbers but a different letter assigned to each duplicate number like the following program: pg. 2 2. On the CSE server run the following command: ./sortA < Text File > sortedtxt ‘Text File’ is replaced by name of txt file and ‘sortedtxt’ is replaced by the name you want to call your new text file. 3. Step 1 and 2 are repeated 10 times to check for stability in the sorting program. If the output for a test remained identical it is stable. 4. Entire process is repeated for Sort B Results Sort A: Time Complexity Ascending Order (Sort A) Data Size 100 1000 10,000 25,000 75,000 100,000 Test 1(s) 0 0 0.18 1.13 10.22 18.12 Test 2(s) 0 0 0.18 1.13 10.28 18.84 Test 3(s) 0 0 0.18 1.13 10.17 18.35 Average Time(s) 0 0 0.18 1.13 10.22 18.44 Time (s) Sort A: Ascending List 20 18 16 14 12 10 8 6 4 2 0 0 20000 40000 60000 Data Size pg. 3 80000 100000 120000 Descending Order (Sort A) Data Size 100 1000 10,000 25,000 75,000 100,000 Test 1(s) 0 0 0.43 2.72 24.49 43.82 Test 2(s) 0 0 0.43 2.75 24.56 43.47 Test 3(s) 0 0 0.43 2.72 24.52 43.55 Average Time(s) 0 0 0.43 2.73 24.52 43.61 Time (s) Sort A: Descending List 50 45 40 35 30 25 20 15 10 5 0 0 20000 40000 60000 80000 100000 120000 Data Size Random Order (Sort A) Data Size 100 1000 10,000 25,000 75,000 100,000 pg. 4 Test 1(s) 0 0 0.48 2.68 24.21 43.39 Test 2(s) 0 0 0.42 2.69 24.27 43.55 Test 3(s) 0 0 0.42 2.69 24.22 42.98 Average Time(s) 0 0 0.44 2.69 24.23 43.31 Sort A: Random List 50 45 40 Time (s) 35 30 25 20 15 10 5 0 0 20000 40000 60000 80000 100000 120000 Data Size Sort B: Time Complexity Ascending Order (Sort B) Data Size 100 1000 10,000 25,000 75,000 100,000 250,000 500,000 999,999 Test 1(s) 0 0 0 0.01 0.06 0.04 0.13 0.26 0.53 Test 2(s) 0 0 0 0.01 0.03 0.05 0.13 0.26 0.63 Test 3(s) 0 0 0 0.01 0.04 0.04 0.13 0.27 0.55 Average Time(s) 0 0 0 0.01 0.04 0.04 0.13 0.26 0.57 Sort B: Ascending List 0.6 Time (s) 0.5 0.4 0.3 0.2 0.1 0 0 200000 400000 600000 Data Size pg. 5 800000 1000000 1200000 Descending Order (Sort B) Data Size 100 1000 10,000 25,000 75,000 100,000 250,000 500,000 999,999 Test 1(s) 0 0 0 0.01 0.03 0.04 0.15 0.27 0.54 Test 2(s) 0 0 0 0.01 0.03 0.04 0.12 0.27 0.53 Test 3(s) 0 0 0 0.01 0.03 0.04 0.12 0.26 0.54 Average Time(s) 0 0 0 0.01 0.03 0.04 0.13 0.27 0.54 Sort B: Descending List 0.6 0.5 Time (s) 0.4 0.3 0.2 0.1 0 0 200000 400000 600000 800000 1000000 1200000 Data Size Random (Sort B) Data Size 100 1000 10,000 25,000 75,000 100,000 250,000 500,000 999,999 pg. 6 Test 1(s) 0 0 0 0.01 0.04 0.06 0.16 0.34 0.72 Test 2(s) 0 0 0 0.01 0.04 0.06 0.16 0.34 0.74 Test 3(s) 0 0 0 0.01 0.04 0.06 0.17 0.34 0.75 Average Time(s) 0 0 0 0.01 0.04 0.06 0.16 0.34 0.74 Sort B: Random 0.8 0.7 Time (s) 0.6 0.5 0.4 0.3 0.2 0.1 0 0 200000 400000 600000 800000 1000000 1200000 Data Size Discussion Sort A With the collected data, we have created a scatter graph which indicates that it takes roughly n2 operations to complete for ascending, descending and random sets. This is shown with the 20 times increase in time taken from an increase from 25000 to 100,000 elements. The ascending data operates in a favorable manner over descending and random sets which may indicate that the sorting algorithm could be bubble sort with early exit. However, the time complexity for ascending is still O(n2) and the reduction in time could be explained by the decrease number of swaps while the number of comparisons remaining unchanged. Thus, this leaves us with sort A being either oblivious bubble sort or vanilla selection sort as these are the only two sorts with time complexity O(n2) and are non-adaptive. This sort is however stable and thus we can conclude it is an Oblivious Bubble Sort. Sort B Sort B is a faster sorting program than A, and by observing the graph we can see the time complexity of B for ascending, descending or random sets is O(n*log(n)). For example, it takes average of 43 seconds for sort A to sort 100,000 elements in a random order whereas Sort B only takes 0.06 seconds. However, this sort cannot be randomised quick sort otherwise time taken to sort ascending, descending and random sets should be the same, since the initial randomisation of all three cases would turn them into randomised structured arrays. Although it may seem like a vanilla quick sort, our sorting for a random set is not of time complexity O(n2), rending sort B to be not adaptive. This sort operates faster for ascending and descending than random possibly due to the decreased number of swaps to be done. Were it a vanilla sort the difference would be less noticeable as the optimisation gains on ascending and descending lists would not be as prevelant. Finally, Sort B is stable as the and thus sort B is a Merge Sort. pg. 7 Conclusion Sort A has time complexity of O(n2), non-adaptive and stable. Thus, it is an Oblivious Bubble Sort. Sort B has time complexity of O(n*log(n)), non-adaptive and stable. Thus, it is a Merge Sort. pg. 8

Help

Presentation on theme: "COMP1927 Course Introduction 16x1"— Presentation transcript:

1 COMP1927 Course Introduction 16x1
COMP x1 Computing 2Lecturer: Angela Finlayson,angf at cse.unsw.edu.auWebsite:COMP1927 Course Introduction 16x1

2 Course Goalsget you thinking like a computer scientist not just a programmerknow a set of fundamental techniques/structuresable to reason about their applicability/effectiveness

3 Assumed Knowledge At the start of this course you should be able to:
produce a correct C program from a specificationunderstand the state-based model of computation (variables, assignment, addresses, parameters, scope)use fundamental C data structures (char, int, float, array, struct, pointers)use fundamental control structures (sequence, selection (if), iteration (while))use abstraction via function declarationsuse linked links

4 Learning Outcomes By the end of the course you should be able to:
analyse performance characteristics of algorithmsmeasure performance behaviour of programschoose/develop effective data structureschoose/develop algorithms on these data structuresreason about effectiveness of data structures + algorithmscreate a set of DS+A as an abstract data type

5 Syllabus Overview Abstract data types
computational complexity, performance analysisSolving problems such assorting,searchingGraphs and graph algorithms

6 Textbook Algorithms in C, Parts 1-4, Robert Sedgewick
Problems – bad style – complex ways of doing things.Algorithms in C, Parts 1-4, Robert SedgewickAlgorithms in C, Part 5, Robert Sedgewick

7 Lectures present a brief overview of theory
demonstrate problem-solving methodsgive practical demonstrationsLectures are based heavily on text-book.Slides are available in PDF formats.Feel free to ask questions, but No Idle Chatting.

8 Tutorials clarify any problems with lecture material
work through problems related to lecture topicsgive practice with design skills (think before coding)Tutorial exercises available on web the week before. Please read and attempt them before your class.Marks for attendance/participation

9 Labs Lab exercises aim to build skills that will help you to
complete the assignment workpass the final examLab classes give you experience applying tools/techniques. Each lab exercise is a small implementation/analysis task.Some tasks will be done in pairsDon’t copy, don't fall behind and start them before your lab class if you need to.Due by tuesday midnight the next week

10 Assignmentsgive you experience applying tools/techniques to larger problems than the lab exercisesBoth assignments are individual assignmentsLate penalties apply to the maximum mark:10% for each day late.They always take longer than you expect.Organise your time and don't leave them to the last minute.

11 Plagiarism You attempt Labs and Assignments unsupervised ...
Plagiarism= submitting someone else's work as your own.Plagiarism will be checked for and punished. We run a plagiarism detection program against submissions this session, any previous sessions etcYou will struggle in the final exam if you do not practice on your own.Try to get help before you reach the stage where you are too far behind to complete the work.

12 Extra Help Consultations
Weekly consultations for extra help with labs and lecture materialMore time slots will be scheduled near assignment due datesme for additional consultations if needed.Forum on website

13 Assessment Tutorial Mark 5% of total Attendance and participation
Lab Mark 10% of totalLab marks out of 3 for each labSome weeks opportunities for a bonus mark to make up for any missed labsClass Prac Exam 10% of total5% for eachAssignmentsassn 1 10%assn 2 10%Final examWorth 55%of overall assessment

14 Supplementary ExamsSupplementary exams are only available to students whodo not attend the exam ANDhave a serious documented reason for not attendingIf you attend an examyou are making a statement that you are "fit and healthy enough"it is your only chance to pass (i.e. no second chances)

15 AdviceDo the Lab exercises and Assignments yourself (or with your pair partner when appropriate)Programming is a skill that improves with practice. The more you practice the easier labs/assignments/exams will be.Don't restrict practice to lab times and two days before assignments due.Make use of tutorials by attempting questions before the class and participating.Go to consults if you need help or fall behind.We want you to do the best you can 

0 thoughts on “Comp1927 Assignment

Leave a Reply

Your email address will not be published. Required fields are marked *