程序代写代做代考 algorithm go AVL graph COMP90038 – Algorithms and Complexity Lecture 14

COMP90038 – Algorithms and Complexity Lecture 14
COMP90038 Algorithms and Complexity
Lecture 14: Transform-and-Conquer
(with thanks to Harald Søndergaard & Michael Kirley)
Casey Myers Casey.Myers@unimelb.edu.au David Caro Building (Physics) 274

COMP90038 – Algorithms and Complexity
Lecture 14
Review from Lecture 13
• We saw priority queues, heaps and heapsort.
• A priority queue is a set of elements, each containing a priority (key) value.
Elements with higher priorities are ejected first.
• A heap is a a complete binary tree that satisfies the condition:
– Each child has a priority (key) which is not greater than its parents.
• Heapsort is a sorting algorithm that repeatedly ejects the higher priority element, then turns the remaining binary tree into a Heap.

COMP90038 – Algorithms and Complexity
Lecture 14
Transform and Conquer
• Transform-and-Conquer is a group of design techniques that:
– Transform: Modify the problem to a more amenable form, and then
– Conquer: Solve it using known efficient algorithms.
• There are three major variations:
– Instance simplification
– Representational change
– Problem reduction

COMP90038 – Algorithms and Complexity
Lecture 14
Transform and Conquer
• Transform-and-Conquer is a group of design techniques that: – Transform: Modify the problem to a more amenable form
– Conquer: Solve it using known efficient algorithms.
• There are three major variations:
– Instance simplification
– Representational change
– Problem reduction

COMP90038 – Algorithms and Complexity Lecture 14
Instance Simplification
• General principle: Try to make the problem easier through some sort of pre- processing typically sorting.
• We can pre-sort input to speed up, for example:
– Finding the median
– Uniqueness checking
– Finding the mode
Selection sort
Θ(𝑛!)
Insertion sort
Ο(𝑛!)
Shellsort
Ο(𝑛 𝑛)
Mergesort
Θ(𝑛 log 𝑛): worst case
Quicksort
Θ(𝑛 log 𝑛): average Θ(𝑛!): worst case
Heapsort
Θ(𝑛 log 𝑛)

COMP90038 – Algorithms and Complexity
Lecture 14
Uniqueness Checking, Brute-Force
• The problem:
Given an unsorted array A 0, ⋯ , 𝑛 − 1 , is A 𝑖 ≠ A 𝑗 whenever 𝑖 ≠ j?
• The obvious approach is brute-force:
A 0, ⋯ , 𝑛 − 1
2,9,8,6,9,5,7,3
𝑛
8
𝑖
0
𝑗
A𝑖
2
A𝑗
A𝑖 =A𝑗

COMP90038 – Algorithms and Complexity
Lecture 14
Uniqueness Checking, with Presorting
• Sorting makes the problem easier:
Selection sort
Insertion sort
Shellsort
Mergesort
Quicksort
Heapsort
Θ(𝑛!)
Ο(𝑛!)
Ο(𝑛 𝑛)
Θ(𝑛 log 𝑛): worst case
Θ(𝑛 log 𝑛): average Θ(𝑛!): worst case
Θ(𝑛 log 𝑛)

COMP90038 – Algorithms and Complexity
Lecture 14
Uniqueness Checking, with Presorting
• Sorting makes the problem easier:
• What is the complexity of this? Ο 𝑛 log 𝑛 + Ο 𝑛 = Ο 𝑛 log 𝑛
Selection sort
Insertion sort
Shellsort
Θ(𝑛!)
Ο(𝑛!)
Ο(𝑛 𝑛)
Mergesort
Quicksort
Heapsort
Θ(𝑛 log 𝑛): worst case
Θ(𝑛 log 𝑛): average Θ(𝑛!): worst case
Θ(𝑛 log 𝑛)

COMP90038 – Algorithms and Complexity
Lecture 14
Uniqueness Checking, with Presorting
• Sorting makes the problem easier:
A 0, ⋯ , 𝑛 − 1
2,9,8,6,9,5,7,3
𝑛
8
𝑖
A𝑖
A𝑖+1
A𝑖 =A𝑖+1

COMP90038 – Algorithms and Complexity
Lecture 14
Uniqueness Checking, with Presorting
• Sorting makes the problem easier:
A 0, ⋯ , 𝑛 − 1
2,3,5,6,7,8,9,9
𝑛
8
𝑖
0
A𝑖
A𝑖+1
A𝑖 =A𝑖+1

COMP90038 – Algorithms and Complexity
Lecture 14
Uniqueness Checking, with Presorting
• Sorting makes the problem easier:
A 0, ⋯ , 𝑛 − 1
2,3,5,6,7,8,9,9
𝑛
8
𝑖
1
A𝑖
3
A𝑖+1
5
A𝑖 =A𝑖+1
𝐹𝐴𝐿𝑆𝐸

COMP90038 – Algorithms and Complexity
Lecture 14
Uniqueness Checking, with Presorting
• Sorting makes the problem easier:
A 0, ⋯ , 𝑛 − 1
2,3,5,6,7,8,9,9
𝑛
8
𝑖
2
A𝑖
5
A𝑖+1
6
A𝑖 =A𝑖+1
𝐹𝐴𝐿𝑆𝐸

COMP90038 – Algorithms and Complexity
Lecture 14
Uniqueness Checking, with Presorting
• Sorting makes the problem easier:
A 0, ⋯ , 𝑛 − 1
2,3,5,6,7,8,9,9
𝑛
8
𝑖
3
A𝑖
6
A𝑖+1
7
A𝑖 =A𝑖+1
𝐹𝐴𝐿𝑆𝐸

COMP90038 – Algorithms and Complexity
Lecture 14
Uniqueness Checking, with Presorting
• Sorting makes the problem easier:
A 0, ⋯ , 𝑛 − 1
2,3,5,6,7,8,9,9
𝑛
8
𝑖
4
A𝑖
7
A𝑖+1
8
A𝑖 =A𝑖+1
𝐹𝐴𝐿𝑆𝐸

COMP90038 – Algorithms and Complexity
Lecture 14
Uniqueness Checking, with Presorting
• Sorting makes the problem easier:
A 0, ⋯ , 𝑛 − 1
2,3,5,6,7,8,9,9
𝑛
8
𝑖
5
A𝑖
8
A𝑖+1
9
A𝑖 =A𝑖+1
𝐹𝐴𝐿𝑆𝐸

COMP90038 – Algorithms and Complexity
Lecture 14
Uniqueness Checking, with Presorting
• Sorting makes the problem easier:
A 0, ⋯ , 𝑛 − 1
2,3,5,6,7,8,9,9
𝑛
8
𝑖
6
A𝑖
9
A𝑖+1
9
A𝑖 =A𝑖+1
𝑇𝑅𝑈𝐸

COMP90038 – Algorithms and Complexity
Lecture 14
Exercise: Computing the Mode
• A mode is a list of array elements which occurs most frequently in the list/array.
• For example, in:
42, 78, 13, 57, 42, 57, 78, 42
the element 42 is the mode.
• The problem:
Given an array 𝐴, find a mode.
• Discuss a brute-force approach vs a pre-sorting approach.

COMP90038 – Algorithms and Complexity
Lecture 14
Mode Finding with Presorting

COMP90038 – Algorithms and Complexity
Lecture 14
Mode Finding with Presorting
A 0,⋯,𝑛−1 = 42,78,13,57,42,57,78,42 Sortthearray: 13,42,42,42,57,57,78,78

COMP90038 – Algorithms and Complexity
Lecture 14
Mode Finding with Presorting
A 0,⋯,𝑛−1 = 42,78,13,57,42,57,78,42
Frequency of the most common element so far

COMP90038 – Algorithms and Complexity
Lecture 14
Mode Finding with Presorting
A 0,⋯,𝑛−1 = 42,78,13,57,42,57,78,42
This counter keeps track of sequences of equal numbers

COMP90038 – Algorithms and Complexity
Lecture 14
Mode Finding with Presorting
A 0,⋯,𝑛−1 = 42,78,13,57,42,57,78,42
While we do not overflow and the sequence continues

COMP90038 – Algorithms and Complexity
Lecture 14
Mode Finding with Presorting
A 0,⋯,𝑛−1 = 42,78,13,57,42,57,78,42
Increase the sequence counter

COMP90038 – Algorithms and Complexity
Lecture 14
Mode Finding with Presorting
A 0,⋯,𝑛−1 = 42,78,13,57,42,57,78,42
If the sequence is the largest so far

COMP90038 – Algorithms and Complexity
Lecture 14
Mode Finding with Presorting
A 0,⋯,𝑛−1 = 42,78,13,57,42,57,78,42
Update both the frequency and mode variables

COMP90038 – Algorithms and Complexity
Lecture 14
Mode Finding with Presorting
A 0,⋯,𝑛−1 = 42,78,13,57,42,57,78,42
Skip the complete sequence of equal numbers

COMP90038 – Algorithms and Complexity
Lecture 14
Mode Finding with Presorting
• Again, after sorting, the rest takes linear time.

COMP90038 – Algorithms and Complexity
Lecture 14
Searching with Presorting
• The problem:
Given unsorted array 𝐴, find item 𝑥 (or determine that it is absent).
• Compare these two approaches: – Perform a sequential search
– Sort, then perform binary search
• What are the complexities of these approaches?

COMP90038 – Algorithms and Complexity
Lecture 14
Searching with Presorting
• What if we need to search for 𝑚 items?
• Let us do a back-of-the envelope calculation (consider worst-cases for simplicity):
– Taken=1024and𝑚=32.
– Sequentialsearch:m×n=32,768
– Sorting + binsearch: 𝑛 𝑙𝑜𝑔!𝑛 + m × 𝑙𝑜𝑔!𝑛 = 10,240 + 320 = 10,560.
– Average-case analysis will look somewhat better for sequential search, but pre- sorting will still win.

COMP90038 – Algorithms and Complexity
Lecture 14
Exercise: Finding Anagrams
• An anagram of a word 𝑤 is a word which uses the same letter as 𝑤 but in a different order.
– – –
Example: ‘ate’, ‘tea’ and ‘eat’ are anagrams.
Example: ‘post’, ‘spot’, ‘pots’ and ‘tops’ are anagrams.
Example: ‘garner’ and ‘ranger’ are anagrams.
• You are given a very long list of words in lexicographic order.
• Device an algorithm to find all anagrams in the list.

COMP90038 – Algorithms and Complexity
Lecture 14
Exercise: Finding Anagrams
• Finding anagrams from a words list:
• Time complexity?
– Sorting words
• Ο𝑛×𝑚log𝑚
• 𝑛 words of length 𝑚. – Test all combinations
• Ο(𝑛!)
– Canwedobetter?
• Yes! Sort words as well!
• Apply “mode idea”

COMP90038 – Algorithms and Complexity Lecture 14
Binary Search Trees
• A binary search tree, or BST, is a binary tree that stores elements in all internal nodes, with each sin-tree satisfying the BST property:
Let the root be 𝑟; then each element in the left subtree is smaller that 𝑟 and each element in the right sub-tree is larger than 𝑟. (For simplicity, we assume that all keys are different.)

COMP90038 – Algorithms and Complexity
Lecture 14
Transform and Conquer

COMP90038 – Algorithms and Complexity
Lecture 14
Review from Lecture 12

COMP90038 – Algorithms and Complexity
Lecture 14
Build a Binary Search Tree Example
• Let’s attempt to build a BST by inserting 15, 8, 20, 5, 9, 17, 25, 29, 2, 6, 12, 10 one at a time.
• Remember: Let the root be 𝑟; then each element in the left subtree is smaller that 𝑟 and each element in the right sub-tree is larger than 𝑟. (For simplicity, we assume that all keys are different.)
• Keep in mind we really mean: 𝑟𝑜𝑜𝑡. 𝑣𝑎𝑙 = 15
𝑟𝑜𝑜𝑡. 𝑙𝑒𝑓𝑡 = 𝑛𝑢𝑙𝑙 𝑟𝑜𝑜𝑡.𝑟𝑖𝑔h𝑡 =𝑛𝑢𝑙𝑙

COMP90038 – Algorithms and Complexity
Lecture 14
Build a Binary Search Tree Example
• Let’s attempt to build a BST by inserting 15, 8, 20, 5, 9, 17, 25, 29, 2, 6, 12, 10 one at a time.
• Remember: Let the root be 𝑟; then each element in the left subtree is smaller that 𝑟 and each element in the right sub-tree is larger than 𝑟. (For simplicity, we assume that all keys are different.)
• Keep in mind we really mean: 𝑟𝑜𝑜𝑡. 𝑣𝑎𝑙 = 8
𝑟𝑜𝑜𝑡. 𝑙𝑒𝑓𝑡 = 𝑛𝑢𝑙𝑙 𝑟𝑜𝑜𝑡.𝑟𝑖𝑔h𝑡 =𝑛𝑢𝑙𝑙

COMP90038 – Algorithms and Complexity Lecture 14
Binary Search Trees
• BSTs are useful for search applications. To search for 𝑘 in a BST, compare against its root r. If r = 𝑘, we are done; otherwise search in the left or right sub-tree, according to k < r or k > r.
• If a BST with n elements is “reasonably” balanced, search involves in the worst case, Θ(log 𝑛) comparisons.

COMP90038 – Algorithms and Complexity Lecture 14
Binary Search Trees
• If the BST is not well balanced, search performance degrades, and may be as bad as linear search:

COMP90038 – Algorithms and Complexity Lecture 14
Binary Search Trees
• If the BST is not well balanced, search performance degrades, and may be as bad as linear search:
• Is this a valid BST? – We’ll come back
to this at the end

COMP90038 – Algorithms and Complexity
Lecture 14
Insertion in Binary Search Trees
• To insert a new element 𝑘 into a BST, we pretend to search for 𝑘.
• When the search has taken us to the fringe of the BST (we find an empty sub-tree),
we insert 𝑘 where we would expect to find it.
• For example, inserting 24:

COMP90038 – Algorithms and Complexity Lecture 14
BST Traversal Quiz
• Performing ………………. traversal of a BST will produce its elements in sorted order.

COMP90038 – Algorithms and Complexity
Lecture 14
Review from Lecture 12
We go as far down the left as possible, visit the left subtree, visit the root, then finally visit the right subtree.

COMP90038 – Algorithms and Complexity Lecture 14
BST Traversal Quiz
• Performing ………………. traversal of a BST will produce its elements in sorted order.
• Example: build a BST by inserting 8, 10, 5, 3, 13, 6 one at a time.

COMP90038 – Algorithms and Complexity Lecture 14
BST Traversal Quiz
•
• •
Performing ………………. traversal of a BST will produce its elements in sorted order.
Example: build a BST by inserting 8, 10, 5, 3, 13, 6 one at a time.
Now look at an Inorder Traversal for this BST
8
5 10
3 6 13
We go as far down the left as possible, visit the left subtree, visit the root, then finally visit the right subtree.
3,5,6,8,10,13

COMP90038 – Algorithms and Complexity Lecture 14
BST Traversal Quiz
•
• •
Performing Inorder traversal of a BST will produce its elements in sorted order.
Example: build a BST by inserting 8, 10, 5, 3, 13, 6 one at a time.
Now look at an Inorder Traversal for this BST
8
5 10
3 6 13
We go as far down the left as possible, visit the left subtree, visit the root, then finally visit the right subtree.
3,5,6,8,10,13

COMP90038 – Algorithms and Complexity Lecture 14
Binary Search Trees
• Try to build a BST by inserting 325, 18, 21, 212, 157, 105 one at a time.

COMP90038 – Algorithms and Complexity Lecture 14
Coming Up Next
• To optimise the performance of BST search, it is important to keep trees (reasonably) balanced.
• Next we will look at AVL trees and 2-3 trees (Levitin Section 6.3).

Related Posts