Introduction-to-algorithms — dynamic programmimng

Dynamic programming typically applies to optimization problems in which we make a set of choices in order to arrive at an optimal solution. As we make each choice, subproblems of the same form often arise. Dynamic programming is effective when a given subproblem may arise form more than one partial set of choices.

  • The key technique is to store the solution to each such subproblem in case it should reappear.

Divide-and-conquer algorithms portion the problem into disjoint subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem — that is, when subproblems share subsubproblems.

  • In this context, a divide-and-conquer algorithm does more work than necessary, repeatedly, solving the common subsubproblems.

A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subsubproblem.

We typically apply dynamic programming to optimization problems. Such problems can have many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution to the problem, as opposed to the optimal solution, since there may be several solutions that achieve the optimal value.

When developing a dynamic-programming algorithm, we follow a sequence of four steps:

  1. Characterize the structure of an optimal solution.
  2. Recursively define the value of an optimal solution.
  3. Compute the value of an optimal solution, typically in a bottom-up fashion.
  4. Construct an optimal solution from computed information.

Step 1-3 from the basis of a dynamic-programming solution to a problem.

  • If we need only the value of an optimal solution, and not the solution itself, the we can omit step 4.
  • When we do perform step 4, we sometimes maintain additional information during step 3 so that we can easily construct an optimal solution.

Read More »

Performance of Python Data Structures

It is important for you to understand the efficiency of these Python data structures because they are the building blocks we will use as we implement other data structure in the remainder of the book.

Lists

The designers of Python had many choices to make when they implemented the list data structure. Each of these choices could have an impact of how fast on how fast list operations perform. To help them make the right choices they looked at the ways that people would most commonly use the list data structure and they optimized their implementation of a list so that the most common operations were very fast. Of course they also tried to make the less common operations fast, but when a tradeoff and to be made the performance of a less common operation was often sacrificed in favor of the more common operation.

Two common operations are indexing and assigning to an index position. Bothe of these operations take the same amount of time no matter how large the list becomes. When an operation like this is independent of the size of the list they are O(1) .

Read More »

Mathematics for 3D Game Programming and Computer Graphics – Vectors

Vectors are of fundamental importance in any 3D game engine. They are used to represent points in space, such as the locations of objects in a game or the vertices of a triangle mesh. They are also used to represent spatial directions, such as the orientation of the camera or the surface normals of a triangle mesh. Understanding how to manipulate vectors is an essential skill of the successful 3D programmer.

Throughout this book, we encounter vectors of various types, usually representing two-dimensional, three-dimensional, or four-dimensional quantities. For now, we make no distinction between vectors representing options and vectors representing directions, nor do we concern ourselves with how vectors are transformed from one coordinate system to another.

Vector Properties

The Dot Product

The dot product of two vectors, also known as the scalar product or inner product, is one of the most heavily used operations in 3D graphics because it supplies a measure of the difference between the directions in which the two vectors point.

\mathbf{P} \cdot \mathbf{Q} = \sum_{i=1}^{m} P_i Q_i.

This definition states that the dot product of two vectors is given by the sum of the products of each component. In three dimensions, we have

\mathbf{P} \cdot \mathbf{Q} = P_x Q_x + P_y Q_y + P_z Q_z.

The dot product P \cdot Q may also be expressed as the matrix product:

\mathbf{P}^T \mathbf{Q} = \begin{bmatrix}P_1 & P_2 & \cdots & P_n\end{bmatrix} \begin{bmatrix} Q_1 \\ Q_2 \\ \vdots \\ Q_n \end{bmatrix},

Now for an important theorem that reveals the ubiquitous utility of the dot product.

Given two n -dimensional vectors \mathbf{P} and \mathbf{Q} , the dot product \mathbf{P} \cdot \mathbf{Q} satisfies the equation

\mathbf{P} \cdot \mathbf{Q} = \lVert P \rVert \lVert Q \rVert \cos \alpha

where \alpha is the planar angle between the lines connecting the origin to the points represented by \mathbf{P} and \mathbf{Q} .

The Cross Product

The cross product of two three-dimensional vectors, also known as the vector product, returns a new vector that is perpendicular to both of the vectors being multiplied together. This property has many uses in computer graphics, one of which is a method for calculating a surface normal at a particular point given two distinct tangent vectors.

The cross product of two 3D vectors P and Q , written as P \times Q , is a vector quantity given by the formula:

P \times Q = < P_yQ_z - P_zQ_y, P_zQ_x - P_xQ_z, P_xQ_y - P_yQ_x >

A commonly used tool for remembering this formula is to calculate cross products by evaluating the pseudodeterminant

P \times Q = \begin{vmatrix} i & j & k \\ P_x & P_y & P_z \\ Q_x & Q_y & Q_z \end{vmatrix}

Theorem 2.8

\lVert P \times Q \rVert = \lVert P \rVert \lVert Q \rVert \sin \alpha

where \alpha is the planar angle between the lines connecting the origin to the points represented by P and Q .

We know that any nonzero result of the cross product must be perpendicular to the two vectors being multiplied together, but there are two possible directions that satisfy this requirement. It turns out that the cross product follows a pattern called the right hand rule.

Mathematics for 3D Game Programming and Computer Graphics – The render pipeline

This chapter provides a preliminary review of the rendering pipeline. It covers general functions, such as vertex transformation and primitive rasterization, which are performed by modern 3D graphics hardware. Readers who are familiar with these concepts may safely skip ahead. We intentionally avoid mathematical discussions in this chapter and instead provide pointers to other parts of the book where each particular portion of the rendering pipeline is examined in greater detail.

Graphics Processors

A typical scene that is to be rendered as 3D graphics is composed of many separate objects. The geometrical forms of these objects are each represented by a set of vertices and a particular type of graphics primitive that indicates how the vertices are connected to produce a shape. Figure 1.1 illustrates the ten types of graphics primitive defined by the OpenGL library. Graphics hardware is capable of rendering a set of individual points, a series of line segments, or a group of filled polygons. Most of the time, the surface of a 3D model is represented by a list of triangles, each of which references three points in a list of vertices.

f0002-01

Read More »

Getting MEAN – Designing a MEAN stack architecture

A common MEAN stack architecture

A common way to architect a MEAN stack application is to have a representational state transfer (REST) API feeding a single-page application (SPA). The API is typically built with MongoDB, Express, and Node.js, with the SPA being built in Angular. The approach is particularly popular with those who come to the MEAN stack from an Angular background and are looking for a stack that gives a fast, responsive API. Figure 2.1 illustrates the basic setup and data flow.

fig_2-1

What is a REST API?

REST stands for REpresentational State Transfer, which is an architectural style rather than a strict protocol. REST is stateless – it has no idea of any current user state or history.

API is an abbreviation for application program interface, which enables applications to take to each other.

So a REST API is a stateless interface to your application. In the case of the MEAN stack, the REST API is used to create a stateless interface to your database, enabling a way for other applications to work with the data.

Figure 2.1 is a great setup, ideal if you have or intend to build an SPA as your user-facing side.

  • Angular is designed with a focus on building SPAs, pulling in data from a REST API, as well as pushing it back.
  • MongoDB, Express, and Node.js are also extremely capable when it comes to building an API, using JSON all the way through the stack, including the database itself.

This is where many people start with the MEAN stack, looking for an answer to the question, "I've built an application in Angular; now where do I get the data?"

Read More »

Getting MEAN – Introducing full-stack development

The MEAN stack is a pure JavaScript stack comprised of four main technologies, with a cast of supporting technologies:

  • MongoDB — the database
  • Express — the web framework
  • Angular — the front-end framework
  • Node.js — the web server

Why the MEAN stack specifically?

The MEAN stack pulls together some of the "best-of-breed" modern web technologies into a very powerful and flexible stack. One of the great things about the MEAN stack is that it not only uses JavaScript in the browser, it uses JavaScript throughout. Using the MEAN stack, you can code both the front end and back end in the same language.

The principle technology allowing the this to happen is Node.js, bringing JavaScript to the back end.

Read More »

TypeScript as a language for Angular applications

The reason is that developing in JavaScript isn’t overly productive. Say a function expects a string value as an argument, but the developer mistakenly invokes it by passing a numeric value. With JavaScript, this error can be caught only at run- time. Java or C# compilers won’t even compile code that has mismatching types, but JavaScript is forgiving because it’s a dynamically typed language.

On larger projects, good IDE context-sensitive help and support for refactoring are important. Renaming all occurrences of a variable of function name in spatially typed languages is done by IDEs in a split second, even in projects that have thousands oaf lines of code; but this isn’t the case in JavaScript, which doesn’t support types. IDEs can help with refactoring much better when the types of the variables are known.

To be more productive, you may consider developing in a statically typed language and then convert the code to Javascript for deployment. Currently there are dozens of languages that compile to JavaScript. The most popular are TypeScript, CoffeeScript, and Dart.

Why not use the Dart language?

  • Interoperability with third-party Javascript libraries isn’t that great.
  • Development in Dart can be done only in a specialized version of the Chrome browser (Dartium) that comes with the Dart VM.
  • The generated JavaScript isn’t easily readable by a human.
  • The community of Dart developers is rather small.

Read More »

JavaScript definite guide – Arrays

An array is an ordered collection of values. Each value is called an element, and each element has a numeric position in the array, known as its index.

  • JavaScript arrays are untyped: an array element may be of any type, and different elements of the same array may be of different types. Array elements may even by objects o other arrays, which allows you to create complex data structures, such as arrays of objects and arrays of arrays.
  • JavaScript arrays are zero-based and use 32-bit indexes: the index of the first element is 0, and the highest possible index is 4294967294 (2^32−2 ), for a maximum as needed and there is no need to declare a fixed size for the array when you create it or to reallocate it when the size changes.
  • JavaScript arrays may be sparse: the elements need not have contiguous indexes and there may be gaps.
  • Every JavaScript array has a length property.
    • For non sparse arrays, this property specifies the number of elements in the array.
    • For sparse arrays, length is larger than the index of all elements.

JavaScript arrays are specialized form of JavaScript object, and array indexes are really little more than property names that happen to be integers. Implementations typically optimize arrays so that access to numerically indexed array elements is generally significantly faster than access to regular object properties.


Inner link

iOS development with Swift 3 – Your first iOS app

What is Swift?

Swift is the modern language created by Apple which got the Apple developer world buzzing. While loved by iOS developers, Objective-C was at the same time seen by many others as an outmoded language – a verbose and peculiar syntax, and with an unsafe type system. Built as a modern alternative to Objective-C, Swift was designed with specific enhancements in mind, specifically safety, performance, and expressiveness.

  • _Safety_ — Swift introduced several programming concepts to reduce some common programmer mistakes. These include strong typing, optionals and error handling.
  • _Performance_ — Apple has introduced internal optimizations to ensure that Swift runs fast. Xcode also provides warnings to encourage you to write code that ensures your app is running optimally.
  • _Expressiveness_ — Expressive code has the right balance between containing a clear meaning and being succinct.

Read More »

日语谓语的各种形态 – “基本形”

动词的“基本形“

语法解释

“基本形”是动词的基本形式。词典中的词条都使用这一形式。各类动词“ます形”去掉“ます”的形式和“基本形”的关系对应如下:

  • 一类动词:“基本形”最后的发音为“う”段,“ます形”去掉“ます”后的发音为“い”段。
  • 二类动词:“基本形”为“ます形”去掉“ます”后加“る”。
  • 三类动词:“基本形”分别为“来る”和“する”,“ます形”去掉“ます”后则为“来”和“し”。

fig_20-1-1

Read More »