Many problems in Computer Vision are formulated in form of a random filed of discrete variables. Examples range from low-level vision such as image segmentation, optical flow and stereo reconstruction, to high-level vision such as object recognition. The goal is typically to infer the most probable values of the random variables, known as Maximum a Posteriori (MAP) estimation. This has been widely studied in several areas of Computer Science (e.g. Computer Vision, Machine Learning, Theory), and the resulting algorithms have greatly helped in obtaining accurate and reliable solutions to many problems. These algorithms are extremely efficient and can find the globally (or strong locally) optimal solutions for an important class of models in polynomial time. Hence, they have led to a significant increase in the use of random field models in computer vision and information engineering in general. This tutorial is aimed at researchers who wish to use and understand these algorithms for solving new problems in computer vision and information engineering. No prior knowledge of probabilistic models or discrete optimization will be assumed. The tutorial will answer the following questions: (a) How to formalize and solve some known vision problems using MAP inference of a random field? (b) What are the different genres of MAP inference algorithms? (c) How do they work? (d) What are the recent developments and open questions in this field?