Feb2019

Graph Theory  Introduction:- Graph data structure and traversal Ordering:-  of dependent nodes using topological ordering  Shortest path:- algorithm in weighted and non-weighted graphs Spanning Tree:- algorithms to connect all nodes in a graph  Graphs are excellent tools for modelling complex relationships  Adjacency matrix is most common way of representing Graph Adjacent List and Adjacent Sets are alternative data structures  Traversing of graph 1) Depth-first 2) Breath-first Relationship between entities example :-  Rob drives a Car.      Entities:- {Rob, Car}      Relationship:- {Drives} A graph can be used to represent above relationship where  (V)ertices ->  entities (E)dges -> relationship => G=(V,E) Directed and Undirected Graph Directed (Twitter) :- Rob drives his car => one directional relationship (car cannot drive Rob) => Rob -----> Car Undirected (Facebook):- David and Dave plays fo...

There are two ways to approach a problem in computer science  Bottom-up Top-down Bottom-up :- approach a problem from the simple case to difficult case... for example factorial of N   we start a loop from 1 to till N where product=1 product =product*1 product= product*2 product=product*3 and continue till N    Top-down :- approach a problem then sub-problem and then sub problem of subvproblem until the best case .. for example:- factorial of a number where N!-> N * (N-1)! * (N-2)! *... 1 fact(N){ if(n==1) return 1; return n * fact(n-1) } where n=1 is the best case where algorithm will stop executing further.   Recursion:-   Recursive shines when implementing a top-down approach Recursion executes on call-stack where best case will the on the top Recursion natural fits when we need to delve into multiple layers of a problem without knowing how many layers are there. e.g. find sub directories in a directory where depth is unknown  Problems:-...

 Permutation lock:- A permutation is an ordered combination. ( a lock problem) (multiplication priciple) it can have 2 types:-  1) Repetition Allowed :- When  a thing has 3 different types, we have N choices each times. Hence the permutation will be =N*N*N 2) No Repetition :- N factorial / (N-r) factorial Combination:- is counting of selections that we make for N objects whereas permutation is counting the number of arrangements of N objects  care about selections