Sorting algorithm | My Assignment Tutor

Reflective Questions (30 points) Limit your answers to one paragraph or less.  You may do research but your writing must be your own; your answers may be checked for plagiarism. Explain the difference between a statically allocated array, a dynamically allocated array, and a linked list. Linked lists have terrible performance for random access or searching of internal entries. Why? Explain the advantages of adding a tail pointer to a linked list, and of doubly-linked over singly-linked lists. Introductory Performance Analysis (20 points) A simple sorting algorithm has quadratic   It takes three minutes to sort a list of 10,000 entries.  How long do you expect it to take to sort a list of 100 entries?  How did you arrive at your answer? A binary searching algorithm has logarithmic   It takes a second to find an item in a list of 10,000 entries.  How long do you expect it to take to find an item in a list of 10,000,000 entries?  How did you arrive at your answer? A naïve searching algorithm took a second to find an item in a list of 500 entries and two seconds to find an item in a list of 1,000 entries. Estimate its runtime in terms of entries, in milliseconds. How did you arrive at your answer? An unknown searching algorithm took a second to find an item in a list of 500 entries, two seconds to find an item in a list of 5,000 entries, and three seconds to find an item in a list of 50,000 entries. Estimate its runtime in big-   How did you arrive at your answer? Dynamic Memory Management (25 points) With the following structures allocated: typedef struct { char *name; int commonality; int weight; } monster; typedef struct { char *name; char *description; double area; int nmonsters; monster *monsters; } region; typedef struct { char *name; double diameter; int nregions; region *regions; } planet; Write functions to free all memory allocated for a planet, its child regions, and their child monsters.The functions should call each other as appropriate – use functions to free enclosed structures.Don’t free any memory that wouldn’t have been allocated.Don’t free anything more than once.Don’t worry about headers.Your function prototypes should be: void dispose_monster(monster *monster); void dispose_region(region *region); void dispose_planet(planet *planet); Linked Lists (25 points) Coding: 15 points With the following structures defined: struct monster_struct { char *name; int commonality; int weight; struct monster_struct *next; }; typedef struct monster_struct monster; typedef struct monster_list { monster *head; } Write functions to return the second-most-common monster and the third-lightest monster in the list.Don’t worry about headers.Don’t worry about which way to resolve ties.The list will always have three monsters in it.Your function prototypes should be: monster *second_most_common(monster_list *ml); monster *third_lightest(monster_list *ml); Analysis: 10 points In big-terms what is the performance of each function?  Why?Would either adding a tail pointer to the list, or making it a doubly-linked list, increase performance? Why or why not?

QUALITY: 100% ORIGINAL PAPER – NO PLAGIARISM – CUSTOM PAPER

Leave a Reply

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