Lab 05

Containers

• store any kind of data

Sorted - implies defined relation between positions of each elt

• maintains pre-defined order, non-arbitrary
• DON'T insert into PQ
• intentional, can't just push_back everything

Ordered -

• maintains current order

Sorted vs. Ordered leads to different complexities

Sorted is faster than ordered usually due to arbitrary order

Set Theory

Set - collection of objects

Union, Intersection, Set Difference (subtraction)

Symmetric Difference (XOR)

• (union) - (intersection) ?

Cartesian Product - generate list of products

Power Set

$$|P(A)|$$ = $$2^{|A|} = 2^{3}$$

Union-Find - NOT on midterm

Connected Nodes are sets, can use DS that use sets to graph the connected nodes

• Take union of 2 sets, find which set a n element is in

Find using Linked Lists - Idea 1 bad

Union Find -> $$O(n^{2})$$

• Amortized doesn't apply here, having more unions requires doing the same thing every time

Amortized -> easy in a lot of cases, some cases are more work?

Idea 3 - give a hierarchy of leaders

Elementary Sorts

• Bubble
• Selection
• Insertion

Bubble Sort - biggest elements gets bubbled to the top $$O(n^{2})$$

• BAD

Selection Sort - find small elements, move them to the index where they need to be, then use subset of original items

Insertion Sort

• fast for small lists and for almost sorted lists

Binary Heap Implementation

Tree implementation

Given a node at position i in the array

What is the index of i's parent?

(i-1)/2

Index of children?

Left: 2i + 1, Right: 2i + 2

If you use a dummy element for 0, and do 1-indexing: Left; 2i, Right: 2i + 1

Set Theory

Symmetric Difference

Set of all objects in either A or B, but NOT both

Cartesian Product

Set whose...

Power Set

Set whose members are al possible subsets of A. X is a subset of Y if all elements of X are in Y

Size of P(A) = $$2^{size(A)}$$

Union Find - NOT on midterm

You want a way of determining that A and B are part of the same group

Union: Merge 2 disjoint sets

Find: Determine which sets

Union of Linked Lists: Join 2 Linked-Lists and update root

Union Find: Idea 1

Vector of vectors for each node with each vector containing all the elements in current set

Union() O(n^2)

Find O(1)

Comparing 2 sets O(n)

Amortized Union() O(n^3) -> same as the complexity of doing n union() operations

Union Find: Idea 2

Give each set a "leader." We will choose the smallest member to be the leader of each set

Union Find: Idea 3

Give a hierarchy of leaders, where a couple of elements are leaders of themselves

Union() O(n), average O(log n)

Find() O(n), average O(log n)

Compare() ~~~

Amortized Union() O(n^2), average O(n log n)

Lab 5 Coding Problem

//vector of non-negative ints, arrange them to form the largest possible number, as a string
//{50,2,19} -> "95201"
//{90,9} -> "990"
// Hint: use a custom comparator
// My hint: if there seems to be too many cases, there's probably a simpler way to check

Use this:
std::to_string(int); // convert the numbers to strings in before returning true or false in comparator
---------------------------------------------------------------------------------------------
struct Comp{
public:
    bool operator()(int l, int r) const
        string sl = to_string(l);
        string sr = to_string(r);
        return sl + sr > sr + sl; // order matters, '<' or '>' depends on order as well
};

string findLargestNumber(vector<int> &numbers) {
    std::sort(numbers.begin(), numbers.end(), Comp{});   //Comp{} does default ctor
    ostringstream oss;
    for (int i = 0; i < numbers.size(); ++i) {
        oss << i;
    }
    return oss.str();
}