FIT2004 ALGORITHMS AND DATA STRUCTURES
COMPLETE STUDY GUIDE WITH SOLVED
QUESTIONS
◉ Divide and Conquer.
Answer: works by recursively breaking down a problem into two or
more sub problems until the problems become simple enough to be
solved directly. An example would be mergesort.
◉ Recursive Algorithms.
Answer: solve a problem by solving smaller internal instances of a
problem -- work towards a base case.
◉ Dynamic Programming.
Answer: Break down a problem into smaller and smaller
subproblems. At their lowest levels, the subproblems are solved and
their answers stored in memory. These saved answers are used
again with other larger (sub)problems which may call for a
recomputation of the same information for their own answer.
Reusing the stored answers allows for optimization by combining
the answers of previously solved subproblems.
◉ Selection Sort.
,Answer: Non-stable, in place sort. Has an N-squared order of growth,
needs only one spot of extra space. Works by searching the entire
array for the smallest item, then exchanging it with the first item in
the array. Repeats this process down the entire array until it is
sorted.
◉ Insertion Sort.
Answer: Stable, in place sort with an order of growth which is
between N and N-squared, needs only one spot of extra space and is
dependent on the order of the items. Works by scanning over the
list, then inserting the current item to the front of the list where it
would fit sequentially. All the items to the left of the list will be
sorted, but may not be in their final place as the larger items are
continuously pushed back to make room for smaller items if
necessary.
◉ ShellSort.
Answer: Non-stable, in place sort with an order of growth which is
undetermined, though usually given at being N-to-the 6/5. Needs
only one spot of extra space. Works as an extension of insertion sort.
It gains speed by allowing exchanges of entries which are far apart,
producing partially sorted arrays which are eventually sorted
quickly at the end with an insertion sort. The idea is to rearrange the
array so that every h-th entry yields a sorted sequence. The array is
h-sorted.
◉ Quick Sort.
,Answer: Non-stable, in place sort with an order of growth of NlogN.
Needs lgN of extra space. It has a probabilistic guarantee. Works by
making use of a divide and conquer method. The array is divided
into two parts, and then the parts are sorted independently. An
arbitrary value is chosen as the partition. Afterwards, all items
which are larger than this value go to the right of it, and all items
which are less than this value go to the left of it.
We arbitrarily choose a[lo] as a partitioning item. Then we scan from
the left end of the array one by one until we find an entry that is
greater than a[lo]. At the same time, we are scanning from a[lo] to
the right to find an entry that is less than or equal to a[lo]. Once we
find these two values, we swap them.
◉ 3-Way Quick Sort.
Answer: Non-stable, in place sort with an order of growth between
N and NlogN. Needs lgN of extra space. Is probabilistic and
dependent on the distribution of input keys.
◉ Mergesort.
Answer: Stable sort which is not in place. It has an order of growth
of NlogN and requires N amount of extra space. Works by dividing an
array in half continuously into smaller and smaller arrays. At the
lowest level, these arrays are sorted and then merged together after
sorting in the reverse order they were divided apart in.
, ◉ Heap Sort.
Answer: Non-stable, in place sort which has an order of growth of
NlogN. Requires only one spot of extra space. Works like an
improved version of selection sort. It divides its input into a sorted
and unsorted region, and iteratively shrinks the unsorted region by
extracting the smallest element and moving it into the sorted region.
It will make use of a heap structure instead of a linear time search to
find the minimum.
◉ Counting Sort (Key Indexed sort).
Answer: An integer sorting algorithm which counts the number of
objects that have a distinct key value, and then used arithmetic on
those countes to determine the positions of each key value in the
output array.
It cannot handle large keys efficiently, and is often used as a
subroutine for other sorting algorithms such as radix sort.
Has a time complexity of N.
◉ Unordered Linked List.
Answer: Data structure with non-efficently supported operations. Is
unordered. Has a worst case cost of search and insertion at N, an
average case cost of insertion at N, and an average case cost of
searching at N/2.
COMPLETE STUDY GUIDE WITH SOLVED
QUESTIONS
◉ Divide and Conquer.
Answer: works by recursively breaking down a problem into two or
more sub problems until the problems become simple enough to be
solved directly. An example would be mergesort.
◉ Recursive Algorithms.
Answer: solve a problem by solving smaller internal instances of a
problem -- work towards a base case.
◉ Dynamic Programming.
Answer: Break down a problem into smaller and smaller
subproblems. At their lowest levels, the subproblems are solved and
their answers stored in memory. These saved answers are used
again with other larger (sub)problems which may call for a
recomputation of the same information for their own answer.
Reusing the stored answers allows for optimization by combining
the answers of previously solved subproblems.
◉ Selection Sort.
,Answer: Non-stable, in place sort. Has an N-squared order of growth,
needs only one spot of extra space. Works by searching the entire
array for the smallest item, then exchanging it with the first item in
the array. Repeats this process down the entire array until it is
sorted.
◉ Insertion Sort.
Answer: Stable, in place sort with an order of growth which is
between N and N-squared, needs only one spot of extra space and is
dependent on the order of the items. Works by scanning over the
list, then inserting the current item to the front of the list where it
would fit sequentially. All the items to the left of the list will be
sorted, but may not be in their final place as the larger items are
continuously pushed back to make room for smaller items if
necessary.
◉ ShellSort.
Answer: Non-stable, in place sort with an order of growth which is
undetermined, though usually given at being N-to-the 6/5. Needs
only one spot of extra space. Works as an extension of insertion sort.
It gains speed by allowing exchanges of entries which are far apart,
producing partially sorted arrays which are eventually sorted
quickly at the end with an insertion sort. The idea is to rearrange the
array so that every h-th entry yields a sorted sequence. The array is
h-sorted.
◉ Quick Sort.
,Answer: Non-stable, in place sort with an order of growth of NlogN.
Needs lgN of extra space. It has a probabilistic guarantee. Works by
making use of a divide and conquer method. The array is divided
into two parts, and then the parts are sorted independently. An
arbitrary value is chosen as the partition. Afterwards, all items
which are larger than this value go to the right of it, and all items
which are less than this value go to the left of it.
We arbitrarily choose a[lo] as a partitioning item. Then we scan from
the left end of the array one by one until we find an entry that is
greater than a[lo]. At the same time, we are scanning from a[lo] to
the right to find an entry that is less than or equal to a[lo]. Once we
find these two values, we swap them.
◉ 3-Way Quick Sort.
Answer: Non-stable, in place sort with an order of growth between
N and NlogN. Needs lgN of extra space. Is probabilistic and
dependent on the distribution of input keys.
◉ Mergesort.
Answer: Stable sort which is not in place. It has an order of growth
of NlogN and requires N amount of extra space. Works by dividing an
array in half continuously into smaller and smaller arrays. At the
lowest level, these arrays are sorted and then merged together after
sorting in the reverse order they were divided apart in.
, ◉ Heap Sort.
Answer: Non-stable, in place sort which has an order of growth of
NlogN. Requires only one spot of extra space. Works like an
improved version of selection sort. It divides its input into a sorted
and unsorted region, and iteratively shrinks the unsorted region by
extracting the smallest element and moving it into the sorted region.
It will make use of a heap structure instead of a linear time search to
find the minimum.
◉ Counting Sort (Key Indexed sort).
Answer: An integer sorting algorithm which counts the number of
objects that have a distinct key value, and then used arithmetic on
those countes to determine the positions of each key value in the
output array.
It cannot handle large keys efficiently, and is often used as a
subroutine for other sorting algorithms such as radix sort.
Has a time complexity of N.
◉ Unordered Linked List.
Answer: Data structure with non-efficently supported operations. Is
unordered. Has a worst case cost of search and insertion at N, an
average case cost of insertion at N, and an average case cost of
searching at N/2.