# Musings

A random collection

## TECH: Graph Theory

1. Partition of set A – represented as $\mathcal{A}$ – a set of disjoint subsets $\{A_1,A_2, ..., A_n\}$, such that $\cup A_i = A$ and $A_i \neq \emptyset$
• Partition $\mathcal{A}'$ Refines a partition $\mathcal{A}$ of set A – $\mathcal{A}' = \{A_1', \cdots, A_m'\}$ and $A_i' \subset A_j \in \mathcal{A}$
• k-element subsets of A – $[A]^k$
2. Graph$G = (V,E)$
• Vertex set$V = V(G)$
• Edge set$E = E(G) \subset V \times V$
3. Order of a graph – $\vert G \vert$ – number of vertices
• Empty graph – no vertices $G = (V=\emptyset, E=\emptyset)$
• Trivial graph – a graph with 0 or 1 vertices
4. vertex v is Incident with an edge e – means $v \in e$ – e is an edge at v
5. End vertices of an edge – ends – edge joins its ends
6. Adjacent edges – if they have a common end vertex
7. Adjacent vertices/Neighbors – there is an edge joining them
• Complete graph – there is an edge from each vertex to every other vertex in the graph – $K^n$ = a complete graph of n-vertices
• Independent vertices – no edge between them – if they are not adjacent
• Stable setsIndependent set of vertices – no 2 elements of the set are adjacent
8. Bijection – there is one-to-one correspondence between 2 sets – bijective = injective/one-to-one + surjective/onto
• Isomorphic$G \simeq G'$ – let G = (V,E) and G’ = (V’, E’) be 2 graphs, and there exists a bijection $\psi \colon V \to V'$ with $(x,y) \in E$ will always imply $(\psi(x), \psi(y)) \in E'$ for all $x, y \in V$
• Isomorphism
• Automorphism – G = G’
• Graph property – a property that is “closed” under isomorphism – if the property holds for a graph, it also holds for all graphs isomorphic to this one graph.
• Graph invariant – a function taking graphs as arguments, and assigns equal values to all isomorphic graphs – example: number of vertices, number of edges, greatest number of pairwise adjacent vertices
9. Graph Set Operations
• Graph union$G \cup G'$
• Graph intersection$G \cap G'$
• Disjoint graphs$G \cap G' = \emptyset$
• Subgraph$G' \subset G$ – G contains G’
• Proper subgraph – similar to proper subset
• G[U] – graph on vertices U whose edges are all edges of G involving U
• Minus = G[V\U] = G-U – delete all the vertices in $U \cap V$ and their edges
• Complement graph – $\bar{G}$
• G*G’ – obtained by joining all vertices of G to all vertices of G’
10. Induced subgraph – if $G' \subset G$ and G’ contains all edges of G with vertices of G’ as end points, $a,b \in V' \subset V \text{ and } (a,b) \in E \implies (a,b) \in E'$ – consists of some of the vertices of the original graph and all of the edges that connect them in the original
• Edge Induced subgraph – consists of some of the edges of the original graph and the vertices that are at their endpoints
• Spanning subgraph – G’ a subgraph (not necessarily induced subgraph) of G such that V’ = V, i.e., G’ contains all the vertices of G.
11. G is Edge-Maximal with a given graph property – if G itself has the graph property but no graph G+G’=(V={a,b},E’={e=(a,b)}) has the property – you add an edge to G, it does not satisfy the graph property anymore
• minimal graphs
• maximal graphs
12. Degree/valency of a vertex – the number of edges at the vertex – the number of neighbors of v – d(v)
• Maximum $\Delta(G)$, Minimum $\delta(G)$ degree of graph G – $max/min\{d(v)|v \in V\}$
• Average degree of graph G, d(G) – measures number of edges of G per vertex
$d(G) = \frac{1}{\vert V \vert} \sum_{v \in V} d(v) = 2 \times \frac{\vert E\vert}{\vert V \vert}$

$\vert E \vert = \frac{1}{2} \sum d(v)$

$\text{min-degree}(G) \leq \text{avg-degree}(G) \leq \text{max-degree}(G)$

• Regular graph – degree of all vertices is same
• THM: The number of vertices of odd degrees in a graph is always even
• THM: Every graph G (with at least one edge) has a subgraph H with
$2\delta(H) > d(H) \geq d(G)$

Every graph G has a subgraph H whose avg degree is not less than than avg degree of G, and minimum degree of subgraph H is more than half of its average degree
Vertices of large degree can not be scattered completely among vertices of small degree

13. Path – a non-empty graph P = (V,E) such that V = {a,b,c,..j,k} and E = {(a,b),(b,c),…,(j,k)}
• A path may also be written as; P = abc…jk
• Length of path – number of edges of the path
• Independent paths – 2 paths with no common inner vertices – they do not cross – only possible common vertices are end-vertices
14. Cycle – first and last vertex is same – let P=abcd…jk, then C = P.a
• Length of Cycle – number of edges = number of vertices
• Girth of a graph – minimum length of a cycle contained in the graph
• Circumference of a graph – maximum length of a cycle contained in the graph
• Chord of a cycle – an edge joining 2 vertices of a cycle, but this edge is not already a part of the cycle
• THM: Every graph G contains a path of length at least $\delta(G) = \text{min-degree}(G)$. Also a cycle of length at least $\delta(G)+1$
• Distance of 2 vertices a, b in graph G – length of a shortest a-b path in G
• Diameter of a graph G – greatest distance between any 2 vertices in G
• THM: Every graph G contains a cycle such that girth(G) ≤ 2 diam(G)+1
• Center Vertex, Radius of Graph
• THM: If $\delta(G) \geq 3$, then girth(G) > 2 log(order(G))
15. CONTINUE HERE, pg 10
16. Walk – path with same vertex occurring more than once
• Closed walk – ends where it started
• Path – a walk with all distinct vertices
17. Connected graph – for any 2 vertices in G there is a path linking them
• Component
• Separator
• Cutvertex
• Bridge
• Separation
• k-connected
• connectivity $\kappa(G)$
• edge-connectivity, $\lambda(G)$
18. Acyclic graph – containing no cycles – forest
• Tree – a connected acyclic graph
• Leaves of a tree – vertices of degree 1
• Every non-trivial tree has a leaf; if we remove a leaf from a tree, what remains is also a tree
• Any 2 vertices of a tree T are li nked by a unique path in T
• A Tree T is minimally connected – T is connected; but T-e is disconnected for each edge $e \in T$
• A Tree T is maximally acyclic – T contains no cycle; but T+ab contains a cycle where a,b are non-adjacent vertices in T
• Every connected graph contains a spanning tree
• A connected graph with n vertices is a tree if and only if it has n-1 edges
• Root
• Tree-order – up/above, down/below
• Up-closure, Down-closure
• Chain
• Height/level of tree T
• Normal tree
• Normal spanning tree – depth first search trees
19. Bipartite graphs – partition graph in 2 sets such that 2 vertices in the same set do not have an edge connecting them
20. r-partite – r partitions of graph such that vertices in same set are not adjacent
21. Complete graph – partition with each vertex in a set by itself
22. A graph is bipartite if and only if it contains no cycle of odd length
23. star, center
24. Euler tours – a closed walk (you finish where you started) in a graph that traverses every edge of the graph exactly once
25. Eulerian graph – a graph that allows a Eulerian tour
26. A connected graph is Eulerian if and only if every vertex has even degree

Written by curious

July 28, 2010 at 12:41 pm

Posted in algorithms

## GEN: Misc

Warmers

A Small Collection

1. Given 5 chains with 3 links in each. You need to join them to create 1 single long chain from them by breaking links and joining them. What is the smallest number of links that you will break and join to make the long chain? (Source: Moscow Puzzles Ch 1, Puzzle #13, pg 5)
2. Given a box with 8 RED socks and 6 BLUE socks. What is the minimum number of socks you must pick without looking at them so that you will have at least 2 socks of the same color?

Written by curious

July 22, 2010 at 1:13 pm

Posted in kiddie

Design Toolbox

 OO Basics Abstraction Encapsulation Polymorphism Inheritance OO Principles Encapsulate what varies Favor composition over inheritance Program to interfaces, not implementations OO Patterns Strategy – defines a family of algorithms, encapsulates each one, and makes them interchangeable. It lets the algorithm vary independently from clients that use it

Good Design

 Reusable Extensible Maintainable Encapsulate to Handle Change Independent parts Flexibility Loose coupling Information Hiding Design by Contract Open/Closed Principle (OCP) – open for extension, but closed for modification SOLID principles: (SRP, OCP, LSP, ISP, DIP) Single Responsibility Principle (SRP) Liskov substitution principle (LSP) Interface segregation principle (ISP) Dependency inversion principle (DIP)
1. Intro to Design Patterns (Strategy Pattern)
• Starts with designing a Duck class hierarchy with
• Need to add a “fly” feature to some ducks. Puts it in base class, Duck, but that leads to all Duck subtypes getting the behavior.

Lesson: A localized update to the code caused a non-local side effect (flying rubber ducks)
• Take out “Flyable” and “Quackable” into separate interfaces, subtypes implement these interfaces. Since these are interfaces, each subclass implementing these interface need to provide implementation of “fly()”, “quack()” methods – no reuse of code. There may be different types of “fly(), quack()” behaviors, causing us to create a separate subclass that implements the behavior differently (will need many combinations of subclasses)

Lesson: Inheritance is not solving the problem. No reuse with interface approach – Will need to implement the interface functions in all the subclasses that implement it.

• Design Principle: Identify the aspects of your application that vary and separate them from what stays the same.

Take what varies/changes and “encapsulate” it so it won’t affect the rest of the code when you later alter/extend the varying parts. Fewer unintended consequences from code changes, more flexibility in the systems.

• “fly()”, “quack()” are the varying parts of the Duck class that vary across ducks. Separate these behaviors into a new set of base classes – FlyingBehavior, QuackingBehavior
• Design Principle: Program to an interface (supertype), not an implementation
• Design Principle: Favor Composition over Inheritance

Composition gives you more flexibility. It lets you encapsulate a family of algorithms into their own set of classes, but it also lets change behavior at run time (example by setting/changing the flyBehavior object).

• Add 2 instance variables “flyBehavior, quackBehavior” to Duck and delegate its “performFly(), performQuack()”. Set the “flyBehavior, quackBehavior” variables to concrete objects in the constructors of Duck subclasses to get desired behavior for the subclass, and add setter methods for setting them.

Lesson: Now it is a lot easier to add new Duck subclasses (example ModelDuck) and new Fly behavior (say RocketPoweredFly)

• Strategy Pattern defines a family of algorithms, encapsulates each one, and makes them interchangeable. Strategy lets the algorithm vary independently from clients that use it.
• I created this broadcast class. It keeps track of all the objects listening to it and anytime a new piece of data comes along it sends a message to each listener. The listeners can join the broadcast at any time or they can even remove themselves. It is really dynamic and loosely coupled. Sounds like Observer Pattern
2. Keeping your objects in the know (Observer Pattern)
• Design Principle: Strive for loosely coupled designs between objects that interact
• Observer defines a one-to-many dependency between objects so that when one object changes state, all its dependents are notified and updated automatically.
3. Decorating Objects
• Design Principle: Classes should be open for extension but closed for modification – Open-Closed principle
• Decorator – attach additional responsibilities to an object dynamically. Decorators provide a flexible alternative to subclassing for extending functionality
4. Baking with OO Goodness – Abstract Factory, Factory Methods
5. One of a Kind Objects – Singleton
6. Encapsulating Invocation – Command Pattern
8. Encapsulating Algorithms – the Template Method
9. Well Managed Collections – Iterator, Composite Patterns
10. State of Things – State Pattern
11. Controlling Object Access – Proxy Pattern
12. Pattern of patterns – Compound Patterns
13. Patterns in real world
14. Leftover patterns – Bridge, Builder, Chain of Responsibility, Flyweight, Interpreter, Mediator, Memento, Prototype, Visitor

Written by curious

July 22, 2010 at 11:13 am

Posted in design-patterns

## TECH: Design Patterns Analyzed

Bookmarks

2. Adapter: Provides a different interface to its “subject” object. It makes 2 existing interfaces work together.
• Convert the interface of a class into another interface clients expect. Adapter lets classes work together that couldn’t otherwise because of incompatible interfaces
• Wrap an existing class with a new interface
• match an old component to a new system

2. Facade: Wrap a complicated system with an object that provides a simple interface

Proxy

1. Proxy: same interface
2. Proxy: Provides the same interface to its “subject” object.
3. Proxy: Intent
• Provide a surrogate or placeholder for another object to control access to it
• Use an extra level of indirection to support distributed, controlled, or intelligent access
• Add a wrapper and delegation to protect the real component from undue complexity
4. Proxy: Benefits –
1. Placeholder for an expensive to create object – only create real object on first access/request
2. Local representative of a remote object – stub code for CORBA etc
3. Protective proxy – check caller has access permissions before forwarding request
4. Smart proxy – additional actions like reference counting, delayed load from persistent store, ensure real object locked before access

http://www.dofactory.com/Patterns/Patterns.aspx

Written by curious

July 22, 2010 at 10:47 am

Posted in design-patterns

## C++: Standard Library

STL provides:

1. Containers:
• vector, list, deque
• stack, queue, priority_queue
• map, set, bitset, multimap, multiset
2. Iterators – copied (iter1 = iter2, , copy-constructed (Iterator iter1(iter2)), incremented (iter++, ++iter, *iter++)
• input iterator – equality/inequality comparison (iter == end(), iter != end()), dereference as rvalue (i = *iter, iter->ival) – istream_iterator, istream_buf_iterator
• output iterator – dereference as lvalue (*iter = x) – ostream_iterator, ostreambuf_iterator
• forward iterator – default constructor (ForwardIterator iter, ForwardIterator())
• bidirectional iterator – decrement (iter--, --iter, *iter--)
• random access iterator – ptr arithmetic (iter + 10, iter-10, n = iter2-iter1), inequality comparison (iter1 < iter2, iter1 > iter2), compound assignment (+=, -=), offset dereference (iter[n])
• Inserter iteratorsback_insert_iterator, front_insert_iterator, insert_iterator
• Inserter iterator constructorsback_inserter, front_inserter, inserter
• reverse_iterator
• raw_storage_iterator
3. Algorithms:
• 12 non-modifying sequence operationsfor_each, find, find_if, find_end, find_first_of, adjacent_find, count, count_if, mismatch, equal, search, search_n
• 27 modifying sequence operationscopy, copy_backward, swap, swap_ranges, iter_swap, transform, replace, replace_if, replace_copy, replace_copy_if, fill, fill_n, generate, generate_n, remove, remove_if, remove_copy, remove_copy_if, unique, unique_copy, reverse, reverse_copy, rotate, rotate_copy, random_shuffle, partition, stable_partition
• 5 sortingsort, stable_sort, partial_sort, partial_sort_copy, nth_element
• 4 binary search on sorted rangeslower_bound, upper_bound, equal_range, binary_search
• 7 merge operationsmerge, inplace_merge, includes, set_union, set_intersection, set_difference, set_symmetric_difference
• 4 heap operationspush_heap, pop_heap, make_heap, sort_heap
• 7 min/max operationsmin, max, min_element, max_element, lexicographical_compare, next_permutation, prev_permutation
• 4 numericaccumulate, adjacent_difference, inner_product, partial_sum
• raw memoryuninitialized_copy, uninitialized_fill, uninitialized_fill_n
4. Function Objects:
• base classesunary_function, binary_function
• arithmeticplus, minus, multiplies, divides, modulus, negate
• comparisonequal_to, not_equal_to, greater, less, greater_equal, less_equal
• logicallogical_and, logical_or, logical_not
• negatorsnot1, not2
• 2 parameter bindersbind1st, bind2nd
• 3 convertorsptr_fun, mem_fun, mem_fun_ref
• 14 instrumental typesunary_negate, binary_negate, binder1st, binder2nd, pointer_to_unary_function, pointer_to_binary_function, mem_fun_t, mem_fun1_t, const_mem_fun_t, const_mem_fun1_t, mem_fun_ref_t, mem_fun1_ref_t, const_mem_fun_ref_t, const_mem_fun1_ref_t
5. valarray
6. exceptionslogical (logic_error, domain_error, invalid_argument, length_error, out_of_range), runtime (runtime_error, range_error, overflow_error, underflow_error)
7. memory – auto_ptr, auto_ptr_ref
8. string
9. RTTItypeid, type_info
10. I/O Streamistream, ostream, iostream, streambuf, filebuf, stringbuf, ifstream, ofstream, fstream, istringstream, ostringstream, stringstream, getline – cin, cout, cerr, clog
11. Locale

Written by curious

July 15, 2010 at 9:00 am

Posted in STL

## OO: Basics

1. Abstract Data Type
2. Abstraction
3. Information Hiding
4. Composition/Aggregation/Containment
5. Association
6. Inheritance
7. Encapsulation – private, protected, public
9. Open-Closed Principle – Open for Extension, but Closed for Modification
Single Choice Principle – Whenever a software system must support a set of alternatives, ideally only one class in the system knows the entire set of alternatives
10. Liskov Substitution Principle (LSP) – Callers of base class method should be able to use any subclass/derived class without knowing it
Design-by-contract – a) A sub class should Honor the contracts made by it parent classes; b) Pre-conditions can only get weaker; c) Post-conditions can only get stronger
11. Coupling – degree of interdependence – low coupling is better
12. Cohesion
13. Reuse – higher re-usability is better
14. Accessor/Mutator – Use Accessors, Mutators instead of accessing member variables directly – easier to change internal detail, easier to execute additional side-effect of mutator
15. Relations – “IS-A” “IS-A-KIND-OF”, “HAS-A”, “IMPLEMENTED-IN-TERMS-OF”, “USES”
16. Interface – a set of methods that can be invoked on an object
17. Program to an interface not an implementation – GoF(Ch1,p18)
Benefits:

• clients remain unaware of the specific types of objects they use, as long as the object adheres to the interface
• clients remain unaware of the classes that implement these objects; clients only know about the abstract class(es) defining the interface
18. Composition vs Inheritance – Favor Composition over Inheritance (GoF,Ch1,p20)
• In Inheritance, internals of parent classes are often visible to subclasses – breaks encapsulation
• But with composition, no internal details of composed objects need be visible in the code using them
• Using inheritance is recommended mainly when adding to the functionality of existing components, reusing most of the old code and adding relatively small amounts of new code.
19. Implementation Inheritance – class inheritance – describes one object’s implementation in terms of another
20. Interface Inheritance – subtyping – one object can be used in place of another
21. Bad – Rigid, Fragile, Immobile, High Coupling
22. Dependency Inversion Principle – a) high level modules should not depend upon low level modules, both should depend upon abstractions; b) abstractions should not depend upon details, details should depend upon abstractions
23. Dependency Injection – a class does not instantiate (create object of a class) any other classes. Instead, it depends on the classes that are “somehow” injected (using setter method or passing as argument in the constructor) into it.
24. Inversion of Control – an object that wants some functionality from another “provider” object, gets called by the provider; rather than the usual flow of logic where the object calls the provider when it needs it.
25. Law of Demeter – Only talk to your immediate friends
26. Interface Segregation Principle – Many client specific interfaces are better than one general purpose interface; Clients should not be forced to depend upon interfaces they don’t use
27. Single Responsibility Principle

Written by curious

July 14, 2010 at 9:21 am

Posted in design-patterns

## C++: How to implement an assignment operator for the following class?

class TFoo : public TSuperFoo
{
private:
TBar* fBar1;
TBar* fBar2;

public:
TFoo& operator=(const TFoo& that);
};


Issues:

1. Do we really need an assignment operator? Yes, definitely. Otherwise compiler will define one for us.
2. Can Copy Constructor be same as Assignment operator? No, assignment operator must be aware of existing state of the object. Copy ctor gets raw memory with no prior state to worry about.
3. Function definition: parameter must be const reference to TFoo, return must be reference to “*this” (to preserve semantics “a=b=c=d”), should not be virtual (for virtual function overridden in derived class must take exactly the same parameters -Err!!! Isn’t this relaxed a bit in newer C++. Ponder on it).
4. Ownership and aliasing of pointers – 2 pointers pointing to the same object (this->fBar1, that.fBar1), who is responsible for deleting it?
5. Instead of trying to do a memcpy(), better to just use copy constructor (fBar1 = new TBar(*that.fBar1))
6. Remember to free memory already pointed by fBar1,fBar2 before you assign a new object to them
7. Guard against accidentally assigning yourself (if (this != &that))
8. Do not forget the ancestors, TSuperFoo. Call (TSuperFoo::operator=(that))
9. Exception Safety: Remember to clean up in case there is an exception. Also in case of an exception leave the object unchanged, in a consistent state.
10. Consider delegating work to auto_ptr
11. Leverage auto_ptr completely, it can free up the memory for old pointer when you reset it with a new pointer
12. What if other classes derive from TBar and fBar1, fBar2 happen to point to instances of derived classes?
13. What if there are classes deriving from TFoo?

Written by curious

July 9, 2010 at 11:10 am

Posted in C++