Scribd
Upload
14 views

Lecture#5 - Advanced Data Structure

Uploaded by

Pritom Das
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views

Lecture#5 - Advanced Data Structure

Uploaded by

Pritom Das
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 15

ADVANCED DATA

STRUCTURE
CSE-237 : ALGORITHM DESIGN AND
A N A LY S I S
BINOMIAL HEAP

Advanced Data Structure


INTRODUCTION - NORMAL HEAP

• Binary heap is a data structure that allows


• insert in O(log n)
• delete (minimum) in O(log n)
• find (minimum) in O(1)
• How about merging two heaps
• complexity is O(n)
• But, Binomial Heap allows merge in O(log n)

Advanced Data Structure


APPLICATION OF HEAPS

• Binary Heaps
• efficient findMin, deleteMin
• many applications
• Binomial Heaps
• Efficient merge of two heaps
• Merging two heap based data structures
• Binomial Heap is build using a structure called Binomial Trees

Advanced Data Structure


HEAP RUNTIME

• Visit the reference : https://en.wikipedia.org/wiki/Binomial_heap

Advanced Data Structure


RED BLACK TREE

Advanced Data Structure


BASICS OF RED-BLACK TREE

• Trees offer many many advantages – especially for quick inserting and
reasonably quick deleting.
• Binary tree searches provide outstanding performance in almost all instances

• Big Problem: unbalanced trees


• This will significantly reduce search times and more…
• Unbalanced trees may easily arise if incoming data is sorted or nearly
sorted
• The solution is Red-Black Tree which is a balanced or nearly-balanced
BST

Advanced Data Structure


PROPERTIES OF RED-BLACK TREE

• Red-black trees are a variation of binary search trees to ensure that the tree is
balanced.
• Height is O(lg n), where n is the number of nodes.
• Red Black Trees is an approach to restructure unbalanced BST.
• All nodes will either be ‘red’ or ‘black’ with constraints!
• Always maintain balanced trees after the insert and/or delete opeartions

• Published by my PhD supervisor, Leo Guibas, and Bob Sedgewick.


• Easiest of the balanced search trees, so they are used in STL map operations…

Advanced Data Structure


REFERENCE

• Visit the reference : https://en.wikipedia.org/wiki/Red–black_tree

Advanced Data Structure


STASSEN'S ALGORITHM

Advanced Data Structure


PRODUCT OF TWO MATRICES

• Strassen observed [1969] that the product of two matrices can be


computed as follows:

Advanced Data Structure


PRODUCT OF TWO MATRICES

• The seven factors can be computed as

Advanced Data Structure


PRODUCT OF TWO MATRICES

• Op Count:
- Each of M1, …, M7 rrequires 1 mult and 1 or 2 add/sub
- Total = 7 mul and 18 add/sub,
- Compared with brute force which requires 8 mults and 4 add/sub
• n/2 n/2 submatrices are computed recursively by the same method

Advanced Data Structure


EFFICIENCY OF STRASSEN’S ALGORITHM

• If n is not a power of 2, matrices can be padded with zeros


• Number of multiplications:
- M(n) = 7 M(n/2) for n > 1, M(1) = 1
- Set n = 2k, apply backward substitution
- M(2k) = 7M(2k-1) = 7 [7 M(2k-2)] = 72 M(2k-2) = … = 7k
- M(n) = 7log n = nlog 7 ≈ n2.807
• Number of additions: A(n)  (nlog 7)
• Other algorithms closer to the lower limit of n2 multiplications, but are even more
complicated

Advanced Data Structure


BRANCH-AND-BOUND
Explore it o NEXT DAY

Advanced Data Structure

You might also like