Archive for July 2010
TECH: Graph Theory
 Partition of set A – represented as – a set of disjoint subsets , such that and
 Partition Refines a partition of set A – and
 kelement subsets of A –
 Graph –
 Vertex set –
 Edge set –
 Order of a graph – – number of vertices
 Empty graph – no vertices
 Trivial graph – a graph with 0 or 1 vertices
 vertex v is Incident with an edge e – means – e is an edge at v
 End vertices of an edge – ends – edge joins its ends
 Adjacent edges – if they have a common end vertex
 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 – = a complete graph of nvertices
 Independent vertices – no edge between them – if they are not adjacent
 Stable sets – Independent set of vertices – no 2 elements of the set are adjacent
 Bijection – there is onetoone correspondence between 2 sets – bijective = injective/onetoone + surjective/onto
 Isomorphic – – let G = (V,E) and G’ = (V’, E’) be 2 graphs, and there exists a bijection with will always imply for all
 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
 Graph Set Operations
 Graph union –
 Graph intersection –
 Disjoint graphs –
 Subgraph – – 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] = GU – delete all the vertices in and their edges
 Complement graph –
 G*G’ – obtained by joining all vertices of G to all vertices of G’
 Induced subgraph – if and G’ contains all edges of G with vertices of G’ as end points, – 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.
 G is EdgeMaximal 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
 Degree/valency of a vertex – the number of edges at the vertex – the number of neighbors of v – d(v)
 Maximum , Minimum degree of graph G –
 Average degree of graph G, d(G) – measures number of edges of G per vertex
 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
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  Path – a nonempty 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 endvertices
 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 . Also a cycle of length at least
 Distance of 2 vertices a, b in graph G – length of a shortest ab 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 , then girth(G) > 2 log(order(G))
 CONTINUE HERE, pg 10
 Walk – path with same vertex occurring more than once
 Closed walk – ends where it started
 Path – a walk with all distinct vertices
 Connected graph – for any 2 vertices in G there is a path linking them
 Component
 Separator
 Cutvertex
 Bridge
 Separation
 kconnected
 connectivity
 edgeconnectivity,
 Acyclic graph – containing no cycles – forest
 Tree – a connected acyclic graph
 Leaves of a tree – vertices of degree 1
 Every nontrivial 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 Te is disconnected for each edge
 A Tree T is maximally acyclic – T contains no cycle; but T+ab contains a cycle where a,b are nonadjacent 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 n1 edges
 Root
 Treeorder – up/above, down/below
 Upclosure, Downclosure
 Chain
 Height/level of tree T
 Normal tree
 Normal spanning tree – depth first search trees
 Bipartite graphs – partition graph in 2 sets such that 2 vertices in the same set do not have an edge connecting them
 rpartite – r partitions of graph such that vertices in same set are not adjacent
 Complete graph – partition with each vertex in a set by itself
 A graph is bipartite if and only if it contains no cycle of odd length
 star, center
 Euler tours – a closed walk (you finish where you started) in a graph that traverses every edge of the graph exactly once
 Eulerian graph – a graph that allows a Eulerian tour
 A connected graph is Eulerian if and only if every vertex has even degree
GEN: Misc
Warmers
 NIEHS Brain Teasers
 Discovery Education
 Hogies
 David Bau
 Math Fair
 Book: Moscow Puzzles
 MENSA Brain Teasers Archive
 British MENSA another one
A Small Collection
 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)
 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?
TECH: Head First DP
Design Toolbox
OO Basics 

OO Principles 

OO Patterns 

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) 
 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 nonlocal 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
 Keeping your objects in the know (Observer Pattern)
 Design Principle: Strive for loosely coupled designs between objects that interact
 Observer defines a onetomany dependency between objects so that when one object changes state, all its dependents are notified and updated automatically.
 Decorating Objects
 Design Principle: Classes should be open for extension but closed for modification – OpenClosed principle
 Decorator – attach additional responsibilities to an object dynamically. Decorators provide a flexible alternative to subclassing for extending functionality
 Baking with OO Goodness – Abstract Factory, Factory Methods
 One of a Kind Objects – Singleton
 Encapsulating Invocation – Command Pattern
 Being Adaptive – the Adapter and Facade Patterns
 Encapsulating Algorithms – the Template Method
 Well Managed Collections – Iterator, Composite Patterns
 State of Things – State Pattern
 Controlling Object Access – Proxy Pattern
 Pattern of patterns – Compound Patterns
 Patterns in real world
 Leftover patterns – Bridge, Builder, Chain of Responsibility, Flyweight, Interpreter, Mediator, Memento, Prototype, Visitor
TECH: Design Patterns Analyzed
Bookmarks
Wrappers: Adapter, Facade, Proxy
Adapters
 Adapter: different interface
 Adapter: Provides a different interface to its “subject” object. It makes 2 existing interfaces work together.
 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
 Facade: simplified interface
 Facade: Wrap a complicated system with an object that provides a simple interface
Proxy
 Proxy: same interface
 Proxy: Provides the same interface to its “subject” object.
 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
 Proxy: Benefits –
 Placeholder for an expensive to create object – only create real object on first access/request
 Local representative of a remote object – stub code for CORBA etc
 Protective proxy – check caller has access permissions before forwarding request
 Smart proxy – additional actions like reference counting, delayed load from persistent store, ensure real object locked before access
C++: Standard Library
STL provides:
 Containers:
vector, list, deque
stack, queue, priority_queue
map, set, bitset, multimap, multiset
 Iterators – copied (iter1 = iter2, , copyconstructed (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, iter10, n = iter2iter1
), inequality comparison (iter1 < iter2, iter1 > iter2
), compound assignment (+=, =
), offset dereference (iter[n]
)  Inserter iterators –
back_insert_iterator, front_insert_iterator, insert_iterator
 Inserter iterator constructors –
back_inserter, front_inserter, inserter
 reverse_iterator
 raw_storage_iterator
 input iterator – equality/inequality comparison (
 Algorithms:
 12 nonmodifying sequence operations –
for_each, find, find_if, find_end, find_first_of, adjacent_find, count, count_if, mismatch, equal, search, search_n
 27 modifying sequence operations –
copy, 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 sorting –
sort, stable_sort, partial_sort, partial_sort_copy, nth_element
 4 binary search on sorted ranges –
lower_bound, upper_bound, equal_range, binary_search
 7 merge operations –
merge, inplace_merge, includes, set_union, set_intersection, set_difference, set_symmetric_difference
 4 heap operations –
push_heap, pop_heap, make_heap, sort_heap
 7 min/max operations –
min, max, min_element, max_element, lexicographical_compare, next_permutation, prev_permutation
 4 numeric –
accumulate, adjacent_difference, inner_product, partial_sum
 raw memory –
uninitialized_copy, uninitialized_fill, uninitialized_fill_n
 12 nonmodifying sequence operations –
 Function Objects:
 base classes –
unary_function, binary_function
 arithmetic –
plus, minus, multiplies, divides, modulus, negate
 comparison –
equal_to, not_equal_to, greater, less, greater_equal, less_equal
 logical –
logical_and, logical_or, logical_not
 negators –
not1, not2
 2 parameter binders –
bind1st, bind2nd
 3 convertors –
ptr_fun, mem_fun, mem_fun_ref
 14 instrumental types –
unary_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
 base classes –
 valarray
 exceptions – logical (
logic_error, domain_error, invalid_argument, length_error, out_of_range
), runtime (runtime_error, range_error, overflow_error, underflow_error
)  memory – auto_ptr, auto_ptr_ref
 string
 RTTI –
typeid, type_info
 I/O Stream –
istream, ostream, iostream, streambuf, filebuf, stringbuf, ifstream, ofstream, fstream, istringstream, ostringstream, stringstream, getline
– cin, cout, cerr, clog  Locale
OO: Basics
 Abstract Data Type
 Abstraction
 Information Hiding
 Composition/Aggregation/Containment
 Association
 Inheritance
 Encapsulation – private, protected, public
 Polymorphism – derived classes/inheritance – virtual functions, overloading
 OpenClosed 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  Liskov Substitution Principle (LSP) – Callers of base class method should be able to use any subclass/derived class without knowing it
Designbycontract – a) A sub class should Honor the contracts made by it parent classes; b) Preconditions can only get weaker; c) Postconditions can only get stronger  Coupling – degree of interdependence – low coupling is better
 Cohesion –
 Reuse – higher reusability is better
 Accessor/Mutator – Use Accessors, Mutators instead of accessing member variables directly – easier to change internal detail, easier to execute additional sideeffect of mutator
 Relations – “ISA” “ISAKINDOF”, “HASA”, “IMPLEMENTEDINTERMSOF”, “USES”
 Interface – a set of methods that can be invoked on an object
 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
 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.
 Implementation Inheritance – class inheritance – describes one object’s implementation in terms of another
 Interface Inheritance – subtyping – one object can be used in place of another
 Bad – Rigid, Fragile, Immobile, High Coupling
 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
 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.
 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.
 Law of Demeter – Only talk to your immediate friends
 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
 Single Responsibility Principle
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:
 Do we really need an assignment operator? Yes, definitely. Otherwise compiler will define one for us.
 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.
 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).
 Ownership and aliasing of pointers – 2 pointers pointing to the same object (this>fBar1, that.fBar1), who is responsible for deleting it?
 Instead of trying to do a memcpy(), better to just use copy constructor (fBar1 = new TBar(*that.fBar1))
 Remember to free memory already pointed by fBar1,fBar2 before you assign a new object to them
 Guard against accidentally assigning yourself (if (this != &that))
 Do not forget the ancestors, TSuperFoo. Call (TSuperFoo::operator=(that))
 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.
 Consider delegating work to auto_ptr
 Leverage auto_ptr completely, it can free up the memory for old pointer when you reset it with a new pointer
 What if other classes derive from TBar and fBar1, fBar2 happen to point to instances of derived classes?
 What if there are classes deriving from TFoo?