CS代考 COMP90038 Algorithms and Complexity – cscodehelp代写

COMP90038 Algorithms and Complexity
Transform-and-Conquer
Olya Ohrimenko
(Slides from Harald Søndergaard)
Lecture 14
Semester 2, 2021
…………… . …. …………….. …
Algorithms and Complexity
(Sem 2, 2021) Transform-and-Conquer © University of Melbourne 1 / 18

Last Lecture
Priority queues, heaps, heap operations, heapsort.
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Transform-and-Conquer © University of Melbourne 2 / 18

Transform and Conquer
Instance simplification Representational change Problem reduction
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Transform-and-Conquer © University of Melbourne 3 / 18

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
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Transform-and-Conquer © University of Melbourne 4 / 18

Uniqueness Checking, Brute-Force
The problem:
Given an unsorted array A[0] . . . A[n − 1], is A[i] ̸= A[j] whenever i ̸= j?
The obvious approach is brute-force:
for i ← 0 to n − 2 do
for j ← i + 1 to n − 1 do
if A[i] = A[j] then return False
return True
What is the complexity of this?

…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Transform-and-Conquer
© University of Melbourne 5 / 18

Uniqueness Checking, with Presorting
Sorting makes the problem easier:
Sort(A, n)
for i ← 0 to n − 2 do
if A[i] = A[i + 1] then return False
return True
What is the complexity of this?

…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Transform-and-Conquer
© University of Melbourne 6 / 18

Exercise: Computing a Mode
A mode is a list or array element which occurs most frequently in the list/array. For example, in
42, 78, 13, 13, 57, 42, 57, 78, 13, 98, 42, 33 the elements 13 and 42 are modes.
The problem:
Given array A, find a mode.
Discuss a brute-force approach vs a pre-sorting approach.
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Transform-and-Conquer © University of Melbourne 7 / 18

Mode Finding, with Presorting
Sort(A, n) i←0
maxfreq ← 0 while i < n do runlength ← 1 while i + runlength < n and A[i + runlength] = A[i] do runlength ← runlength + 1 if runlength > maxfreq then maxfreq ← runlength mode ← A[i]
i ← i + runlength return mode
Again, after sorting, the rest takes linear time..
. .
…………….. …
. . . .
. . . .
. . . . .
. .
. .
Algorithms and Complexity (Sem 2, 2021) Transform-and-Conquer © University of Melbourne 8 / 18

Searching, with Presorting
The problem:
Given unsorted array A, find item x (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? 
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Transform-and-Conquer © University of Melbourne 9 / 18

Searching, with Presorting
What if we need to search for m items?
Let us do a back-of-the envelope calculation (consider worst-cases for
simplicity):
Take n = 1024 and m = 32.
Sequential search: m × n = 32, 768.
Sorting + binsearch: nlog2 n+m×log2 n = 10,240+320 = 10,560.
Average-case analysis will look somewhat better for sequential search, but pre-sorting will still win.
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Transform-and-Conquer © University of Melbourne 10 / 18

Exercise: Finding Anagrams
An anagram of a word w is a word which uses the same letters as w 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.
Devise an algorithm to find all anagrams in the list. 
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Transform-and-Conquer © University of Melbourne 11 / 18

Left blank
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Transform-and-Conquer © University of Melbourne 12 / 18

Binary Search Trees
A binary search tree, or BST, is a binary tree that stores elements in all internal nodes, with each sub-tree satisfying the BST property:
Let the root be r; then each element in the left subtree is smaller than r and each element in the right sub-tree is larger than r. (For simplicity we will assume that all keys are different.)
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Transform-and-Conquer © University of Melbourne 13 / 18

Binary Search Trees
BSTs are useful for search applications. To search for k in a BST, compare against its root r. If r = k, we are done; otherwise search in the left or right sub-tree, according as k < r or k > r.
If a BST with n elements is “reasonably” balanced, search involves, in the worst case, Θ(log n) comparisons.
15
8 20
5 91725 2 6 12 29
10
…………… . …. …………….. …
Algorithms and Complexity
(Sem 2, 2021)
Transform-and-Conquer
© University of Melbourne 14 / 18

Binary Search Trees
If the BST is not well balanced, search performance degrades, and may be as bad as linear search:
325 18
21
212
157 105
…………… . …. …………….. …
Algorithms and Complexity
(Sem 2, 2021)
Transform-and-Conquer
© University of Melbourne 15 / 18

Insertion in Binary Search Trees
To insert a new element k into a BST, we pretend to search for k. When the search has taken us to the fringe of the BST (we find an
empty sub-tree), we insert k where we would expect to find it. Inserting 24:
15 15
8 20 ⇒ 8 20
5 2 6
9 17 25
5 2 6
9 17 25 12 24 29
10
…………… . …. …………….. …
12 10
29
Algorithms and Complexity (Sem 2, 2021)
Transform-and-Conquer
© University of Melbourne 16 / 18

BST Traversal Quiz
Performing ………… traversal of a BST will produce its elements in sorted order.

…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Transform-and-Conquer © University of Melbourne 17 / 18

Summary & Next Lecture
Transform and conquer:
Pre-sort
Binary Search Trees
Balancing Binary Search Trees:
To optimise the performance of BST search, it is important to keep trees (reasonably) balanced.
Next we shall look at AVL trees and 2–3 trees.
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Transform-and-Conquer © University of Melbourne 18 / 18