Cs520 Advanced Analysis of Algorithms and Complexity

Queue

• A queue is a linear structure in which
• all insertions are done at one end, called the rear or back, and
• all deletions are done at the other end, called the front.
• This updating policy is called first in, first out (FIFO)

Priority Queue

• A priority queue is a structure with some aspects of FIFO queue but
• in which element order is related to each element’s priority,
• rather than its chronological arrival time.
• As each element is inserted into a priority queue, conceptually it is inserted in order of its priority
• The one element that can be inspected and removed is the most important element currently in the priority queue.
• a cost viewpoint: the smallest priority
• a profit viewpoint: the largest priority

Union-Find ADT for Disjoint Sets

• Through a Union operation, two (disjoint) sets can be combined.
• (to insure the disjoint property of all existing sets, the original two sets are removed and the new set is added)
• Let the set id of the original two set be, s and t, s != t
• Then, new set has one unique set id that is either s or t.
• Through a Find operation, the current set id of an element can be retrieved.
• Often elements are integers and
• the set id is some particular element in the set, called the leader,

Union-Find ADT e.g.

• UnionFind create(int n)
• // create a set (called sets) of n singleton disjoint sets {{1},{2},{3},…,{n}}
• int find(UnionFind sets, e)
• // return the set id for e
• void makeSet(unionFind sets, int e)
• //union one singleton set {e} (e not already in the sets) into the exiting sets
• void union(UnionFind sets, int s, int t)
• // s and t are set ids, s != t
• // a new set is created by union of set [s] and set [t]
• // the new set id is either s or t, in some case min(s, t)

Dictionary ADT

• A dictionary is a general associative storage structure.
• Items in a dictionary
• have an identifier, and
• associated information that needs to be stored and retrieved.
• no order implied for identifiers in a dictionary ADT

Video Lecture of the topic can be found at

• Video Lecture of the topic can be found at
• Computer Algorithms - Abstract Data Types (ADT)
• https://youtu.be/aHWNxF0c08U
•  
• Basics for Analysing Computer Algorithms
• https://youtu.be/n1ArVTvMJtE