Scribd Logo
Upload

Welcome to Scribd!

  • 60 views

    Tutorial 8: FIT 1029 - Algorithmic Problem Solving

    Uploaded by

    Ali Alabid
    The objectives of this tutorial are to get familiar with recursive sorts, tracing recursive algorithms, writing backtracking algorithms, and understanding Heaps and Heap sort. It includes tasks on applying merge sort, quick sort, and heap sort to alphabetically sort a list of letters. It also discusses backtracking approaches for generating bitstrings and solving problems like the torch problem and knapsack problem.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Tutorial 8: FIT 1029 - Algorithmic Problem Solving

    Uploaded by

    Ali Alabid
    60 views2 pages
    The objectives of this tutorial are to get familiar with recursive sorts, tracing recursive algorithms, writing backtracking algorithms, and understanding Heaps and Heap sort. It includes tasks on applying merge sort, quick sort, and heap sort to alphabetically sort a list of letters. It also discusses backtracking approaches for generating bitstrings and solving problems like the torch problem and knapsack problem.

    Original Description:

    FIT1029

    Original Title

    Tutorial 8

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The objectives of this tutorial are to get familiar with recursive sorts, tracing recursive algorithms, writing backtracking algorithms, and understanding Heaps and Heap sort. It includes tasks on applying merge sort, quick sort, and heap sort to alphabetically sort a list of letters. It also discusses backtracking approaches for generating bitstrings and solving problems like the torch problem and knapsack problem.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    60 views2 pages

    Tutorial 8: FIT 1029 - Algorithmic Problem Solving

    Uploaded by

    Ali Alabid
    The objectives of this tutorial are to get familiar with recursive sorts, tracing recursive algorithms, writing backtracking algorithms, and understanding Heaps and Heap sort. It includes tasks on applying merge sort, quick sort, and heap sort to alphabetically sort a list of letters. It also discusses backtracking approaches for generating bitstrings and solving problems like the torch problem and knapsack problem.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    Tutorial 8

    FIT 1029 Algorithmic Problem Solving


    23 April 2014 Prepared by Julian Garca
    The objectives of this tutorial are:
    To get familiar with recursive sorts.
    To be able to trace recursive algorithms.
    To be able to write backtracking algorithms
    To understand Heaps and Heap sort.
    Task 1
    For the list of letters [A, L, G, O, R, I, T, H, M]...
    Algorithm MergeSort(L[0..n-1])
    Input: A list of length n
    Output: A list sorted into ascending order
    Sorts a list using Merge Sort
    if (n > 1)
    {
    q ! n/2-1
    MergeSort(L[0 .. q])
    MergeSort(L[q+1.. n-1])
    L ! Merge(L[0 .. q], L[q+1.. n-1])
    }
    Apply merge sort to sort the list alphabetically
    Apply quick sort to sort the list alphabetically. Use the two parti-
    tion methods discussed in Lecture 13.
    Discuss advantages and disadvantages of the two different parti-
    tion methods.
    Algorithm QuickSort(L[0..n-1])
    Input: A list of length n
    Output: A list sorted into ascending order
    Sorts a list using Quick Sort
    if (n > 1)
    {
    index ! Partition(L[0, n-1])
    if (index > 0) {
    QuickSort(L[0 .. index-1])
    }
    if (index < n-1) {
    QuickSort(L[index+1.. n-1])
    }
    }
    Algorithm Partition(L[0..n-1])
    Input: A list of length n Output: Position of the pivot
    Partition the list, so you rst have the items less than the pivot,
    then the pivot, then items greater or equal to pivot.
    pivot ! L[0]
    index ! 0
    k ! 1
    while (k < n) do
    {
    if (L[k] < pivot)
    {
    index ! index + 1
    //swap L[k] and L[index]
    tmp ! L[k]
    L[k] ! L[index]
    L[index] ! tmp
    }
    k ! k+1
    }
    //swap pivot and L[index]
    tmp ! L[0]
    L[0] ! L[index]
    L[index] ! tmp
    return index
    Task 2
    Consider the backtracking approach to generating bitstrings. For
    N = 3, describe the order that the bit strings will be printed if
    possibleItems [1, 0]; instead of possibleItems [0, 1].
    Task 3
    Modify the module backtrack, given in lectures, so that possibleItems
    is a Stack.
    Task 4
    Describe a representation of partial solutions to solve the torch prob-
    lem
    1
    using backtracking. Discuss how different representations may
    1
    4 people wish to cross a bridge at
    night. They need a torch to cross and
    only have one torch. They can only
    cross at most two at a time, and can
    only travel at the speed of the slowest.
    The four people can cross in 1 minute,
    2 minutes, 5 minutes and 10 minutes,
    respectively. Find a way for them to
    cross in the minimum amount of time.
    affect the design of modules.
    tutorial 8. fit 1029 algorithmic problem solving 2
    Task 5
    For the backtracking approach to solve the knapsack problem (mod-
    ule knapSack in the lecture)...
    Write an algorithm for the module getPossibleItems.
    Write an algorithm for the module processSolution.
    Task 6
    Draw the binary search tree that results from inserting the letters in
    the list [A, L, G, O, R, I, T, H, M], considering their alphabetical order.
    Task 7
    Apply Heap Sort to sort the list of letters [A, L, G, O, R, I, T, H, M] in
    alphabetical order. Show the state of the tree at every step.

    You might also like