University Study Materials 4 U

Define general NLPP Let z be a real value functions of n variables designed by, (i)z=f(x1, x2 …xn) (ii)Let b1, b2 …bn be a set of constraints     s.t. g1(x1, x2. . . xn) (<=, =,or ,>=) b1     s.t. g2(x1, x2. . . xn) (<=, =,or ,>=) b2                                   .                                   .           gm (x1, x2. . . xn) (<=, =,or ,>=) bm As in linear programming, f(x1, x2 …xn) is the NLP’s objective function, and               g 1(x1, x2. . . xn) (<=, =,or ,>=) b1 , . . . ,      gm (x1, x2. . . xn) (<=, =,or ,>=) bm are the NLP’s constraints. An NLP with no constraints is an unconstrained NLP. (iii)Let Xj>=0, j=1, 2…n If either f or some g^i’s are non-linear. Then the problem of determining the type which makes z=0 is a maximum or minimum satisfies eqn (ii) & (iii). This is called general NLPP. for more  click here

SOLVED QUESTION BANK

What do you mean by general LPP? Linear Programming is a mathematical technique for choosing the best alternative from a set of feasible alternatives, in situations where the objective function as well as the restrictions or constraints can be expressed as linear mathematical function. Define Slack, Surplus variables Slack Variable: If the constraints of a given LPP be S a ij x j £ bi    then the non-negative variable Si which are introduced to convert the inequalities to equalities                            S a ij x j  + Si  =   b i        are called slack variables. Surplus variable: If the constraints of a given LPP be S a ij x j ³ b i      then the nonnegative variable Si which are introduced to convert the inequality                              constraints to the equations S a ij x j  -  Si   =   b i   are called surplus variables. for more  click here

click here  for two marks Q & A

QUEUEING THEORY SIMULATION INTRODUCTION TO LINEAR PROGRAMMING NON-LINEAR PROGRAMMING PROBLEM

Simulation is the imitation of the operation of a real world process or system over time. It is a numerical technique for conducting experiments that involve certain types of mathematical and system over extended period of time. Applications of simulation Manufacturing systems Public and transportation systems Restaurant and entertainment systems Computer system performance   system and system environment in simulation A system is defined as the collection of objects / ideas which permits identification as a whole coherent logical functional unit. A system is often affected by changes occurring outside the system. Such changes are said to occur in the system environment. Types of simulation models Based on the representation                     Physical model                     Schematic model                     Symbolic model Based on timing nature                     Static                     Dynamic for more  click here

Basic characteristics of a queuing system The input or arrival pattern   The service mechanism The queue discipline The customer’s behavior Define transient and steady state A queuing system is said to be in transient state when its operating characteristics are dependent of time otherwise it is steady state. for more   click here

COMPLEXITY ANALYSIS & ELEMENTARY DATA STRUCTURES HEAP STRUCTURES RED BLACK TREE & TRIES DIVIDE AND CONQUER DYNAMIC PROGRAMMING AND BACKTRACKING

SEARCH STRUCTURES Red Black Tree  click here Red Black Tree Algorithm  click here Tries click here Red-Black Properties Every node is either red or black. Every leaf (NULL pointer) is black. ■ Note: this means every “real” node has 2 children If a node is red, both children are black ■ Note: can’t have 2 consecutive reds on a path Every path from node to descendent leaf contains the same number of black nodes. The root is always black RB Trees: Worst-Case Time So we’ve proved that a red-black t ree has  O(lg  n ) height Corollary: These operations take O(lg  n ) time:                         ■Minimum(), Maximum()                         ■Successor(), Predecessor()                         ■Search() Insert() and Delete():                         ■Will also take O(lg  n ) time                         ■But will need special care since they modify tree

A P J Abdul Kalam Technological University      

 JOB SEQUENCING WITH DEADLINES   Link 1

Strassen’s Matrix Multiplication Traveling Salesperson Problem Knapsack Problem The 8-Queens Problem Graph Coloring Branch & Bound Click here

click here

Min-Max Heaps, Deaps, Leftist Trees, Binomial Heaps & Fibonacci Heaps are available from the following links            Link 1   &   Link 2 Min Max Heap & Leftist Heap Click Here Heap sort, Binomial Heap & Leftist Heap  Click Here Binomial Heap  link 1   &  link 2 Binomial Heap Algorithm  click here   Fibonacci heap Algorithm  click here Binomial  Heap  vs Lazy  Heap  ( Complexity)

Linked Lists ppt click here Asymptotic Notations Step count is to compare time complexity of two programs that compute same function and also to predict the growth in run time as instance characteristics changes. Determining exact step count is difficult and not necessary also. Because the values are not exact quantities. We need only comparative statements like c1n2 ≤ tp(n) ≤ c2n2. For example, consider two programs with complexities c1n2 + c2n and c3n respectively. For small values of n, complexity depend upon values of c1, c2 and c3. But there will also be an n beyond which complexity of c3n is better than that of c1n2 + c2n.This value of n is called break-even point. If this point is zero, c3n is always faster (or at least as fast). Common asymptotic functions are given below. a)  Big ‘Oh’ Notation (O) O(g(n)) = { f(n) : there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 } It is the upper bound of any function. Hence it denotes the