Musings

A random collection

Archive for July 2010

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. GraphG = (V,E)
    • Vertex setV = V(G)
    • Edge setE = 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
    • IsomorphicG \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 unionG \cup G'
    • Graph intersectionG \cap G'
    • Disjoint graphsG \cap G' = \emptyset
    • SubgraphG' \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

  1. NIEHS Brain Teasers
  2. Discovery Education
  3. Hogies
  4. David Bau
  5. Math Fair
  6. Book: Moscow Puzzles
  7. MENSA Brain Teasers Archive
  8. British MENSA another one

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

TECH: Head First DP

Design Toolbox

OO Basics
  1. Abstraction
  2. Encapsulation
  3. Polymorphism
  4. Inheritance
OO Principles
  1. Encapsulate what varies
  2. Favor composition over inheritance
  3. Program to interfaces, not implementations
OO Patterns
  1. 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
  7. Being Adaptive – the Adapter and Facade Patterns
  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

  1. Vince Huston on Design Patterns

Wrappers: Adapter, Facade, Proxy

Adapters

  1. Adapter: different interface
  2. Adapter: Provides a different interface to its “subject” object. It makes 2 existing interfaces work together.
  3. Adapter: Intent
    • 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

Facade

  1. Facade: simplified interface
  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
  8. Polymorphism – derived classes/inheritance – virtual functions, overloading
  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);
};

Reference: Anatomy article, with follow up article after comments.
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++