sid99
November 5th, 2006, 05:09 PM
Hi there i have a problem with these two questions i received as homework. I have limited experience in this field and believe my university is teaching us very poorly on this module as though expecting us to already understand this module considering most people have no prior knowledge in data structures and algorithms nor programming. Most people who do understand this are students who already have atleast 3 or more years experience in programming or fields such as this. Please someone help me out i really want to be able to understand as what i have to do and even a brief solution would help! I am even willing to pay someone for tuition if it comes down to it!! OK enough me rambling the reasons, now here are the questions:
--------------------------------------------------------------------------------------------
(1) Assume the following situation: you have a
program managing a sets of records and records are often imported unsorted from files and need to be sorted. The following algorithms have been tested to work on your system with the following running times (in ms):
(ALGORITHM) Insertion Sort (AVERAGE CASE) 5 + n2 (WORST CASE) 5 + 2n2
(ALGORITHM) Merge Sort (AVERAGE CASE) 80 + 40n log10n (WORST CASE) 100 + 50nlog10n
(ALGORITHM) Quick Sort (AVERAGE CASE) 50 + 30n log10n (WORST CASE) 50 + 50n2
Work out optimal strategies for choosing an algorithm minimising the
• average running time
• maximal running time
depending on the number of records to be sorted. Each strategy uses two
sorts and has one switching point.
You can use a program like gnuplot (http://www.gnuplot.info/) to plot
the functions, explore the ranges and find the intersection. Alternatively do
manual binary search with your calculator, or write a program in Java that
does it for you. Describe the way you achieved your results and document
it by either giving 2 screenshots of your plots, a table of your search steps
and results, or the source of the program you wrote.
Give the choice of sorts and the ranges where they are fastest. Verify
the switching point arithmetically by giving the running times for the next
greater and smaller n.
Each optimal strategy uses two sorts and has one switching point.
FOR QUESTION 1 THE FURTHER INSTRUCTIONS WE WERE GIVEN WERE:
What you are looking for is the minimum of three functions. Using a plotting program can help to see the overall shapes.
Looking at the difference between the functions allows you to locate the intersections with binary search (you are looking for a change of sign).
When doing the verification and other calculations, pay attention to the base of the log. It is chosen to be 10 to facilitate the use of calculators, if you use binary or natural logs,
---------------------------------------------------------------------------------------------
(2)
•Write the following algorithm in pseudocode using the the queue ADT:
Take an array of n sorted queues containing integer numbers. Insert
these queues into a queue (of queues). Then repeatedly merge the first
two sorted queues into a new sorted queue and reinsert the merged
queue at the end. Repeat until the queue of queues contains only one
queue.
•Give the time complexity of the algorithm in terms of n and the average
length of the initial queues k. Justify your answer.
•What is the memory complexity of the algorithm, if the queues are
implemented using linked lists; what is it if they are implemented
using arrays of fixed size. Justify your answer.
FOR QUESTION 2 THE FURTHER INSTRUCTIONS WE WERE GIVEN WERE:
Be aware that it is only allowed to use the method specified in he ADT. Thus you do not have direct access to the number of elements in a queue.
You can write calls to ADT functions like in Java. E.g. queue1.enqueue(something).
Use the names from the ADT definition.
Take into account, that queues may be empty when you merge them (check with isEmpty where necessary).
Note that this question is about queues, not about priority queues.
--------------------------------------------------------------------------------------------
(1) Assume the following situation: you have a
program managing a sets of records and records are often imported unsorted from files and need to be sorted. The following algorithms have been tested to work on your system with the following running times (in ms):
(ALGORITHM) Insertion Sort (AVERAGE CASE) 5 + n2 (WORST CASE) 5 + 2n2
(ALGORITHM) Merge Sort (AVERAGE CASE) 80 + 40n log10n (WORST CASE) 100 + 50nlog10n
(ALGORITHM) Quick Sort (AVERAGE CASE) 50 + 30n log10n (WORST CASE) 50 + 50n2
Work out optimal strategies for choosing an algorithm minimising the
• average running time
• maximal running time
depending on the number of records to be sorted. Each strategy uses two
sorts and has one switching point.
You can use a program like gnuplot (http://www.gnuplot.info/) to plot
the functions, explore the ranges and find the intersection. Alternatively do
manual binary search with your calculator, or write a program in Java that
does it for you. Describe the way you achieved your results and document
it by either giving 2 screenshots of your plots, a table of your search steps
and results, or the source of the program you wrote.
Give the choice of sorts and the ranges where they are fastest. Verify
the switching point arithmetically by giving the running times for the next
greater and smaller n.
Each optimal strategy uses two sorts and has one switching point.
FOR QUESTION 1 THE FURTHER INSTRUCTIONS WE WERE GIVEN WERE:
What you are looking for is the minimum of three functions. Using a plotting program can help to see the overall shapes.
Looking at the difference between the functions allows you to locate the intersections with binary search (you are looking for a change of sign).
When doing the verification and other calculations, pay attention to the base of the log. It is chosen to be 10 to facilitate the use of calculators, if you use binary or natural logs,
---------------------------------------------------------------------------------------------
(2)
•Write the following algorithm in pseudocode using the the queue ADT:
Take an array of n sorted queues containing integer numbers. Insert
these queues into a queue (of queues). Then repeatedly merge the first
two sorted queues into a new sorted queue and reinsert the merged
queue at the end. Repeat until the queue of queues contains only one
queue.
•Give the time complexity of the algorithm in terms of n and the average
length of the initial queues k. Justify your answer.
•What is the memory complexity of the algorithm, if the queues are
implemented using linked lists; what is it if they are implemented
using arrays of fixed size. Justify your answer.
FOR QUESTION 2 THE FURTHER INSTRUCTIONS WE WERE GIVEN WERE:
Be aware that it is only allowed to use the method specified in he ADT. Thus you do not have direct access to the number of elements in a queue.
You can write calls to ADT functions like in Java. E.g. queue1.enqueue(something).
Use the names from the ADT definition.
Take into account, that queues may be empty when you merge them (check with isEmpty where necessary).
Note that this question is about queues, not about priority queues.