Describe the time complexity of your algorithm

Assignment Help Computer Engineering

Reference no: EM131864881

Problem

Suppose we wish to perform exact inference over a chain Markov Random Field given byX1 X2 ... Xn. Assume that each variableXihas|V al(Xi)|=d.

(a) Derive anO(n3d3) algorithm for computing marginalsP(Xi, Xj) over alln2variable pairs Xi,Xj.

(b) Since we are computing marginals for all variable pairs, we can store computations done for the previous pairs and use them to save time for the computations of the remaining pairs. The key recursive relationship that makes thisXwork is the following equation (fori

P(Xi, Xj) =P(Xi, Xj1)P(Xj|Xj1) (1) Xj1

Prove that the equation above holds.

(c) Construct a dynamic programming algorithm that computes marginals over alln2variable pairs based on the recursive relation in (1), and achieves a running time that is asymptotically faster thanO(n3d3). Describe the time complexity of your algorithm in terms ofnandd. Note: Make sure to clearly specify how each of the probabilitiesPyou use are computed.

Reference no: EM131864881

Questions Cloud

Describe the traditionalist generation : Describe the Traditionalist Generation. What social, economic, and political issues affected this generation?

Create flowchart based on algorithm for revised program need : Create a 1- to 2-page flowchart based on the algorithm for the revised program needs. Add the flowchart structure in the existing flowchart for the program.

Describe a time when you had a negative service experience : Describe a time when you had a negative service experience. What could the company have done differently to keep you in the zone of tolerance?

What is the distribution of the mean mpg for the sample : In determining automobile mileage ratings, it was found that the mpg in the city for a certain model is normally distributed, with a mean of 30 mpg.

Describe the time complexity of your algorithm : Describe the time complexity of your algorithm in terms ofnandd. Note: Make sure to clearly specify how each of the probabilitiesPyou use are computed.

Determine the related safety precautions : Determine the related safety precautions that need to be taken and the PPE equipment that need to be utilized in the following scenario.

Discuss dimensions of the global leadership : Determine the skills, strengths, or qualities that you should posses relative to the seven(7) dimensions of the Global Leadership and Organizational Behavior.

Explain the source of the strategic conflict : Explain the source of the strategic conflict between Starbucks & the Ethiopian government?

Explain different instruction format in term of fixed length : Explain the different instruction formats in terms of fixed and variable length. How are these instructions executed in a classical von Neumann machine?

User Account

All Pages