Change color scheme of your vim

Bored of the color scheme of the vim editor. Changing involves a few steps as follows:

  1. Download the color scheme package.
  2. Extract it in your $Home/.vim folder.
  3. Now you have about 100 color schemes available for selection. Trying each one of them using :colorscheme colorscheme-name sounds time-consuming.
  4. Well, you can install another package Scroll Colors. Extract it in your $Home/.vim/plugins folder.
  5. Open your vim. Type :COLORSCROLL and you will be prompted to continue. Different color schemes will come in sequence when you navigate using arrows. You will get a preview of each color scheme. Look out at the name of the one that seems good to you.
  6. Open your vimrc file in admin mode. You can find it in your system at /etc/vim/vimrc.
  7. Add the line colorscheme greyhouse, say you want to use greyhouse scheme.
  8. Restart vim and enjoy your color scheme.

Cheers!

Application Development in Qt

In Qt, basically 5 types of applications can be developed. Depending on your purpose, you choose the one and all the environment for developing the application is provided by the framework. They are namely:

  • Qt Widgets Application
  • Qt Quick Application
  • Qt Quick UI Application
  • HTML5 Application
  • Qt Console Application

In this post, I will be telling you about the first three.

Qt Widgets Application
Widgets form the basic building up entity of a user interface application. Talking in context to any CAD software’s UI, you see a button, a menubar, anything on the user interface, that is a widget. You are able to access the functionalities, the services provided by the software by means of these. These all are widgets.

When you choose to develop this type of application, whatever you do is in C++. This is what the framework provides by default. The thing would be different if you add some QML files in the resources folder of the app. Will be telling you about QML ahead. In this app, we have a UI file by default which is created in design mode of QtCreator. UI files are centred to widget based approach only.

Huh, now coming to the two modes of QtCreator. They are: edit mode and design mode. In edit mode, you do the coding part while in design mode, you have the actual look of the window. You can select any component say a toolbutton or any other component and place it on the window at the place where you want. The associated functionality of the component added in design mode is implemented by means of slots. Well, that is a different concept. Signal-slot mechanism is the soul behind the working of UI apps in Qt. Will be telling some other time.

Just manipulate the code in edit mode and see the components you added in action.

Qt Quick UI Application
This application is developed using the QML(acronym for Qt Modeling Language). It is Javascript based language and centred mainly for user interfaces’ applications. In this type of application, only QML is in action. QML is part of Qt Quick which is a UI-creation kit. You can work in edit mode or design mode here also. Well, working in design mode makes things so easy. The functioning is added in edit mode just like QtWidgets application.

Qt Quick Application
This application is a combination of the previous two. You can have C++ and QML both working in the same project. The rest things are the same as the previous two types of applications.

Well, this was all for someone entirely dummy in application development in Qt, covering some simple things yet important.

Compiling OGRE app in QtCreator

OGRE applications can be built in various IDEs. I went on with my friend these days- QtCreator. In order to be able to see OGRE working on my system, I made an application with pre-constructed code. You can follow the instructions below:

  1. Just download the file at this link and un-tar it. This download contains a tutorial, a dist directory and a cmake script.
  2. Put the files in a directory, say ogre-demo.
  3. Now open QtCreator and open the CMakeLists.txt file here.
  4. A dialog box will ask you to choose a build directory. By default, a new build directory is created. Just click next.
  5. Now, you will be asked to run cmake. Click the “Run Cmake” button.
  6. After this, open terminal and move to the build directory.
  7. Run make && make install there. If you do not run these, the console below in QtCreator would display an exit message.
  8. Now, you can run the app in QtCreator. You will be having a blank black screen in front of you just like the one below, though the app has compiled and is running decently.

screenshot06282014_175534208

Time to add something to see OGRE in action. ๐Ÿ˜€ I told about tutorial framework in the download done in step 1. Remember? Hm! Counting on the files in it, the entity that would be displayed in the OGRE window on running the app is defined in the file TutorialApplication.cpp. Open the file and you will find the function createScene() is empty.

Make your function look like:

void TutorialApplication::createScene(void)
{
// Set the scene's ambient light
mSceneMgr->setAmbientLight(Ogre::ColourValue(0.5f, 0.5f, 0.5f));

// Create an Entity
Ogre::Entity* ogreHead = mSceneMgr->createEntity(“Head”, “ogrehead.mesh”);

// Create a SceneNode and attach the Entity to it
Ogre::SceneNode* headNode = mSceneMgr->getRootSceneNode()->createChildSceneNode(“HeadNode”);
headNode->attachObject(ogreHead);

// Create a Light and set its position
Ogre::Light* light = mSceneMgr->createLight(“MainLight”);
light->setPosition(20.0f, 80.0f, 50.0f);
}

Scrutinizing the code above, you will find entity Head whose source file is ogrehead.mesh. This file is present in the dist folder we got during the download, more specifically in dist/media/models folder.

Save your file and run the app. And you get this output:

screenshot06282014_181505778

Once the program is working, use the WASD keys to move, and the mouse to look around. The Escape key exits the program.

You got a basic OGRE app working with QtCreator on your system.

Well, I did not go with literal meaning of OGRE this time. ๐Ÿ˜› You know what it is? The word “ogre” is of French origin and is used to depict a large, hideous, manlike monster that eats human beings. Ogres frequently feature in mythology, folklore, and fiction throughout the world. The above output illustrates it well! ๐Ÿ˜€

The Introductory Stride to OGRE

OGRE, acronym for Object-oriented Graphics Rendering Engine, is a scene-oriented 3D engine to make applications that make use of hardware-accelerated 3D graphics. The engine is written using C++. OGRE can be used in games, simulations.

OGRE has an object-oriented design with a plugin architecture that allows easy addition of features, thus making it highly modular. The engine is flexible, in the sense that there are no predefined constraints on those who wish to want to use OGRE, unlike other engines that are designed for a particular type of game or some application. Considering the gaming industry only, the developers can make use of different libraries in integration to OGRE, depending on their requirements.

OGRE provides support for various platforms including Linux, Windows, iOS and Android. It also imparts bracing for materials, shaders, meshes, animations. Special effects supported include compositor systems, particle systems, sprite graphics and much more. It has been used in commercial games like Torchlight and Ankh.

Installing OGRE:

It is a smooth process. So begin with downloading the source and installing dependencies. Follow the steps below:

  1. Download the source from and extract it using:
    tar xjf ogre_src_v1-8-0.tar.bz2
  2. Next, get the configuration tools to build OGRE using:
    sudo apt-get install build-essential automake libtool.
  3. For dependencies, run:
    sudo apt-get install libfreetype6-dev libfreeimage-dev libzzip-dev libxrandr-dev libxaw7-dev freeglut3-dev libgl1-mesa-dev libglu1-mesa-dev
  4. The dependencies in this step are optional. You can install them using:
    sudo apt-get install nvidia-cg-toolkit libois-dev libboost-thread-dev

Now, you are ready for the installation. Follow the steps below:

  1. Move to source directory:
    cd ogre_src_v1-8-1/
  2. Create a new directory:
    mkdir build
  3. Go to build directory:
    cd build
  4. Run cmake, pass the path of source directory:
    cmake ../../ogre_src_v1-8-1
  5. Run make -j4
  6. After the successful compilation, install it:
    sudo make install
  7. By default, it gets installed in /usr/local/include.

The installation worked like a charm for me. And you have OGRE working on your system. In the coming tutorial, I will be illustrating how to use OGRE in QtCreator. Enjoy! ๐Ÿ˜€

Working with Sage

So something new always excites! Isn’t it? Today I will introduce you to the very powerful mathematics software, SAGE. In general, the word “sage” means a person who has profound wisdom. I had heard about it solving mathematical equations. But when I saw it working, I just astounded me. It works so painlessly. It is whip-smart.

Let’s get started.

Installation:
1. Grab the latest binary version from http://www.sagemath.org/download-linux.html.
2. Unpack the binary.
3. Run sage.

And you got sage working on your system.

Usage: You can work with Sage via-

  • command line
  • notebook graphical interface
  • programs and scripts

I have worked yet in command line interface and in the notebook. There’s not much difference in the way you interact. The provisions of saving files, printing etc. are provided in the notebook. In order to be able to work in notebook mode, type notebook in the sage command line.

I tried out a few linear, non-linear equations and then proceeded with differential equations. To me, the fun part came when I began plotting. Every time the code was evaluated and output was there, I was astounded everytime. Felt that spark in eyes just like little kids have when something fascinates them. ๐Ÿ˜€

A few examples of plotting are:

  • The following code plots a hypotrochoid along with text.
    L = [[6*cos(pi*i/100)+5*cos((6/2)*pi*i/100),6*sin(pi*i/100)-5*sin((6/2)*pi*i/100)] for i in range(200)]
    p = polygon(L, rgbcolor=(1/8,1/4,1/2))
    t = text("hypotrochoid", (5,4), rgbcolor=(1,0,0))
    show(p+t)

    sage0

  • This is a 3D-plot.
    x, y = var('x,y')
    plot3d(x^2 + y^2, (x,-2,2), (y,-2,2))

    sage0-size500.jmol

I tried many more. Next section tells about using LaTeX and Sage.

SageTeX
Well, I will be using LaTeX along with Sage to generate the outputs of sage in the form of pdf. For embedding the outputs of sage into LaTeX documents, SageTeX is used. The SageTeX installed along with Sage should be made known to the LaTeX installation on your system.

For this, follow the following steps:

  1. Ensure that you have LaTeX installed on your system. No? Then run this:
    sudo apt-get install texlive-full
  2. Search for texmf directory in which the LaTeX packages are installed by default. Run kpsewhich -var-value=TEXMFHOME. This would show something like /home/omg/texmf as in my case.
  3. Now copy the sage directory from the sage_root/local/share/texmf/ into your home texmf directory with a command like cp -R sage_root/local/share/texmf/tex TEXMFHOME. Here sage_root is the path to the directory of your sage installation.

And you are done.

Time to check. Take the following example.

documentclass{article}
usepackage{sagetex}

begin{document}

Using SageTeX, one can use Sage to compute things and put them into
your LaTeX{} document. For example, there are
$sage{number_of_partitions(1269)}$ integer partitions of $1269$.
You don’t need to compute the number yourself, or even cut and paste
it from somewhere.

Here’s some Sage code:

begin{sageblock}
f(x) = exp(x) * sin(2*x)
end{sageblock}

The second derivative of $f$ is

[
frac{mathrm{d}^{2}}{mathrm{d}x^{2}} sage{f(x)} =
sage{diff(f, x, 2)(x)}.
]

Here’s a plot of $f$ from $-1$ to $1$:

sageplot{plot(f, -1, 1)}

end{document}

Now run the following commands:

  • latex filename.tex
  • sage filename.sagetex.sage
  • latex filename.tex
  • To view the pdf generated, run evince filename.pdf

So many commands. Huh! Make a script as I did and enjoy. ๐Ÿ™‚

A li’l more about SoQt and Coin3D

Getting acquainted with SoQt

SoQt requires the Coin3D library. It does not come with Qt. The Qt’s free license prohibits the building of SoQt along with Qt. So it says SoQt has to be built separately on the system. To be able to use SoQt, you must have Coin3D and Qt working on your systems.

By using the combination of Coin3D, Qt and SoQt for your 3D applications, you have a framework for writing completely portable software across the whole range of UNIX, Linux, Microsoft Windows and Mac OS X operating systems. Coin3D, Qt and SoQt creates minimum of hassle for developers when working on multiplatform software, with the resulting large gains in productivity.

Beginning with the name of SoQt itself, we know it is the binding between Qt and Coin3D library. Considering Coin3D library, it is free and opensource implementation of OpenInventor which is capable of easy construction of 3D scenes, animation and provides user interaction with the scene. SoQt is compatible with Open Inventor. All Inventor classes follow a naming convention.

The basic classes in Inventor are prefixed using letters Sb. A few of them are listed below:

  • SbBool: Boolean value
  • SbColor: RGB color value
  • SbLine: directed 3D line
  • SbCylinder: cylinder
  • SbSphere: sphere, and so on.

In order to be able to use any of the basic types, the corresponding header files are included.

The letters So refer to scene object. All the other classes in Inventor are prefixed by these letters.
eg., SoCone, SoTransform etc.
The names of methods and variables follow camel-casing. eg. setSceneGraph()

SoQt, like Coin and Qt, provides the programmer with a high-level application programmer’s interface (API) in C++. The library primarily includes a class-hierarchy of viewer components of varying functionality and complexity, with various modes for the end-user to control the 3D-scene camera interaction.

Working of Coin3D

The node is the basic building block used to create three dimensional scene databases in Inventor.
Each node holds a piece of information, such as a surface material, shape description, geometric
transformation, light, or camera. All 3D shapes, attributes, cameras, and light sources present in a
scene are represented as nodes.

An ordered collection of nodes is referred to as a scene graph. This scene graph is stored in the Inventor database. Inventor takes care of storing and managing the scene graph in the database. The database can contain more than one scene graph. After you have constructed a scene graph, you can apply a number of operations or actions to it, including rendering, picking, searching, computing a bounding box, and writing to a file.

Classes of database primitives include:

  • Nodes– Shape nodes, Property nodes, Group nodes
  • Engines:Engines are objects that can be connected to other objects in the scene graph and used to animate parts of the scene or constrain certain parts of the scene in relation to other parts.
  • Sensors:A sensor is an object that detects when something in the database changes and calls a function supplied by the application. Sensors can respond to specified timing requirements or to changes in the scene graph data.

Nodes

  • Group nodes: These nodes are used to collect child objects. The class for these nodes is SoGroup. This class has various sub-classes under it having different characteristics.
  • Shape nodes: They are used to represent 3D geometric objects.
  • Property nodes: They are used to represent qualitative features of the objects in the scene.

Example

I am referring to an example in my previous post.
#include <Inventor/Qt/SoQt.h>: The SoQt class takes care of Qt initialisation.
#include <Inventor/Qt/viewers/SoQtExaminerViewer.h>: A number of viewers are available to view the 3D object generated. They are:

  • Constrained Viewer
  • Examiner Viewer
  • Fly Viewer
  • Plane Viewer
  • Full Viewer

I am using Examiner Viewer here. It is the general purpose viewer that has a convenient interface for repositioning and reorientation of the camera, by panning, rotating and zooming its position.

#include <Inventor/nodes/SoBaseColor.h>: SoBaseColor is a class used to define an object’s base color. The color is specified in RGB format. It falls under property nodes.

#include <Inventor/nodes/SoCone.h>: This is the node for cone shape. It comes under the category of shape nodes.

#include <Inventor/nodes/SoSeparator.h>: It is subclass of SoGroup class. It is used to isolate the effects of nodes in the scene.

QWidget * mainwin = SoQt::init(argc, argv, argv[0]);: Here the initilisation to the SoQt library is done.

SoSeparator * root = new SoSeparator;
root->ref();
: The root node of the scene graph is created here.

SoBaseColor * col = new SoBaseColor;
col->rgb = SbColor(2, 3, 0);
root->addChild(col);
: The base color of the object is set.

root->addChild(new SoCone);: A cone is added to the scene as a child to the root node.

SoQtExaminerViewer * eviewer = new SoQtExaminerViewer(mainwin);
eviewer->setSceneGraph(root);
eviewer->show();
: The ExaminerViewer class of the viewer is used for display of objects.

SoQt::show(mainwin);: This pops up the main window.

SoQt::mainLoop();: Cleans up all static data allocated by the SoQt library on initialization.

In this post, I discussed a few more details about SoQt and working of Coin3D. Will be posting something interesting soon. Keep reading!

Qt with Coin3D

Well, I do not know how many of you have heard of Qt and Coin3D. In this post, I will be telling you about these and how these two can be used together.

What is Qt?
Qt is a cross-platform application framework that is widely used for developing application software with a graphical user interface (GUI).

Qt can be implemented using following tools:
1.Qt Creator, a cross-platform IDE for C++ and QML. Qt Designer’s GUI layout/design functionality is integrated into this relatively new IDE, although Qt Designer can still be called as a standalone tool.
2.Qmake, a tool that automates the generation of Makefiles for development project across different platforms.

Installation:
1. Download the source file from http://qt-project.org/downloads according to your system.
2. Next step is to run the .run file.
3. First place it in your home directory.
4. Type in terminal: sudo chmod a+x file-name.run.
5. Execute ./file-name.run in terminal.
In my case, I ran qt-opensource-linux-x64-5.2.1.run file and had qt-5.2.1 working on my system.

What is Coin3D?
Check for its installation in my previous post http://kamalpreetgrewal.wordpress.com/2014/03/13/coin3d/.

What is SoQt?
In order to implement Coin3D in Qt, SoQt is required. It acts as glue between Coin3D and Qt.
Type sudo apt-get install libsoqt4-dev in terminal. Now you have SoQt installed.

I had to use Coin3D with Qt. In order to accomplish this, I had to be clear how SoQt and Coin3D work.
The basic working principle is scenegraphs.

What is a scenegraph?
A graphical scene is logically represented using scenegraphs. A scene graph can be defined as collection of nodes in a graph or tree structure. I will be discuusing these in another post.
I created a simple program for cone. The program is:

#include <Inventor/Qt/SoQt.h>
#include <Inventor/Qt/viewers/SoQtExaminerViewer.h>
#include <Inventor/nodes/SoBaseColor.h>
#include <Inventor/nodes/SoCone.h>
#include <Inventor/nodes/SoSeparator.h>

int main(int argc, char ** argv)
{
// Initializes SoQt library
QWidget * mainwin = SoQt::init(argc, argv, argv[0]);

// Make a dead simple scene graph by using the Coin library.
SoSeparator * root = new SoSeparator;
root->ref();

SoBaseColor * col = new SoBaseColor;
col->rgb = SbColor(2, 3, 0);
root->addChild(col);

root->addChild(new SoCone);

// Use one of the convenient SoQt viewer classes.
SoQtExaminerViewer * eviewer = new SoQtExaminerViewer(mainwin);
eviewer->setSceneGraph(root);
eviewer->show();

// Pop up the main window.
SoQt::show(mainwin);
// Loop until exit.
SoQt::mainLoop();

// Clean up resources.
delete eviewer;
root->unref();
SoQt::done();

return 0;
}

The next step is open terminal and go to directory where you saved the file.
Follow these steps in terminal:
1. qmake -project : generates cone.pro file
2. qmake : generates Makefile
3. make : In case of some errors regarding SoQt missing (or something similar), open Makefile. Go to LIBS. Append this line with -lSoQt -lCoin and you are done. Again run make.
4. ./cone

An Examiner Viewer window will show a cone. That’s it. You used Coin3D with Qt. Yeah, was not tough so far. ๐Ÿ˜€ In case of any queries, do comment.

Coin3D

Coin3D is a high-level, retained-mode toolkit for effective 3D graphics development. It is API compatible with Open Inventor 2.1. Coin3D is a C++ object oriented retained mode 3D graphics API used to provide a higher layer of programming for OpenGL.

Let’s begin with its installation in your Ubuntu.

Installation:

  1. Download Coin-3.1.3.tar.gz fom https://bitbucket.org/Coin3D/coin/downloads.
  2. Next unzip the file using the following commands:
    • cd /tmp
    • gzip -cd Coin-3.1.3.tar.gz | tar xvf –
    • mkdir coin-build
  3. Run configure from the build directory:cd coin-build
    ../Coin-3.1.3/configure
    After the configuration is done, it may show some prefix problem.
    Instead use the following command:
    ../Coin-3.1.3/configure –prefix=/usr/local –bindir=/usr/local/bin
  4. Build the Coin library:
    make
    If this command runs fine, it is well and good. But you may get some errors namely Error1 and Error2 at the end. This can be solved by editing the file Coin-3.1.3/include/Inventor/SbBasic.h.
    Put #include <Inventor/C/errors/debugerror.h> in the beginning of this file. This is bound to solve the errors in case they appear.
  5. Install the Coin library:
    make install

This finishes the installation of the Coin3D library. Its implementation will be discussed in coming posts.

NP-completeness

Algorithms can be classified on different basis. A few of them have been considered below:

  • Type of operations used by the algorithm

      1. Deterministic Algorithms:

        A deterministic algorithm is an algorithm which, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. A deterministic algorithm computes a mathematical function, a function has a unique value for any given input, and the algorithm is a process that produces this particular value as output.
        Deterministic algorithms can be defined in terms of a state machine: a state describes what a machine is doing at a particular instant in time. State machines pass in a discrete manner from one state to another. Just after we enter the input, the machine is in its initial state or start state. If the machine is deterministic, this means that from this point onwards, its current state determines what its next state will be; its course through the set of states is predetermined. Note that a machine can be deterministic and still never stop or finish, and therefore fail to deliver a result.

        Disadvantages:

        1. Unfortunately, for some problems deterministic algorithms are also hard to find. For example, there are simple and efficient probabilistic algorithms that determine whether a given number is prime and have a very small chance of being wrong. The known deterministic algorithms remain considerably slower in practice.
        2. Another major problem with deterministic algorithms is that sometimes, we don’t want the results to be predictable. For example, if you are playing an on-line game of blackjack that shuffles its deck using a pseudorandom number generator, a clever gambler might guess precisely the numbers the generator will choose and so determine the entire contents of the deck ahead of time, allowing him to cheat; for example, the Software Security Group at Reliable Software Technologies was able to do this for an implementation of Texas Hold ’em Poker that is distributed by ASF Software, Inc, allowing them to consistently predict the outcome of hands ahead of time.
        3. Similar problems arise in cryptography, where private keys are often generated using such a generator. This sort of problem is generally avoided using a cryptographically secure pseudo-random number generator.

    ย 

    1. Non-Deterministic Algorithms:

      A non-deterministic algorithm is an algorithm that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A non-deterministic algorithm is different from its more familiar deterministic counterpart in its ability to arrive at outcomes using various routes. If a deterministic algorithm represents a single path from an input to an outcome, a non-deterministic algorithm represents a single path stemming into many paths, some of which may arrive at the same output and some of which may arrive at unique outputs. This property is captured mathematically in “non-deterministic” models of computation.
      Examples: Merge Sort, Spanning Tree

  • On the basis of time taken by algorithm to solve the problem

      1. Polynomial Time Algorithms:

        An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., T(n) = O(n^k) for some constant k. Problems for which a polynomial time algorithm exists belong to the complexity class P, which is central in the field of computational complexity theory.
        Examples: quick sort, basic arithmetic operations etc.

    ย 

    1. Non-Polynomial Time Algorithms:

      This group of algorithms consist of algorithms whose running time is not bounded by polynomial expressions.
      Example: Travelling salesperson problem

  • Based on the output of algorithms

    1. Decision Problems:

      A decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem “given two numbers x and y, does x evenly divide y?” is a decision problem. The answer can be either ‘yes’ or ‘no’, and depends upon the values of x and y.

    2. Optimization Problems:

      An optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete variables is known as a combinatonial optimization problem. In a combinatorial optimization problem, we are looking for an object such as an integer, permutation or graph from a finite (or possibly countable infinite) set.

These categories should be clear before studying NP-completeness. It helps to go on with the flow of the concepts.

Complexity Classes of Problems

A complexity class is a set of problems of related resource-based complexity. The simpler complexity classes are defined by the following factors:

  • The type of computational problem: The most commonly used problems are decision problems. However, complexity classes can be defined based on function problems, counting problems, optimization problems etc.
  • The model of computation: The most common model of computation is the deterministic Turing machine, but many complexity classes are based on non-deterministic Turing machines, boolean circuits, etc.
  • The resource (or resources) that are being bounded and the bounds: These two properties are usually stated together, such as polynomial time, logarithmic space, constant depth, etc.

P-complexity-class:

P, also known as PTIME, is one of the most fundamental complexity classes. It contains all decision problems that can be solved by a deterministic Turing machine in polynomial time.
A language L is in P if and only if there exists a deterministic Turing machine M, such that:

  • M runs for polynomial time on all inputs
  • For all x in L, M outputs 1
  • For all x not in L, M outputs 0

NP-complexity-class:

NP is one of the most fundamental complexity classes. The abbreviation NP refers to “non-deterministic polynomial time.”
NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine.
Example: Travelling Salesperson Problem

Hard to solve NP-problems

Because of the many important problems in this class, there have been extensive efforts to find polynomial-time algorithms for problems in NP. However, there remain a large number of problems in NP that defy such attempts, seeming to require super-polynomial time. Whether these problems really aren’t decidable in polynomial time is one of the greatest open questions in computer science.
An important notion in this context is the set of NP-complete decision problems, which is a subset of NP and might be informally described as the “hardest” problems in NP. If there is a polynomial-time algorithm for even one of them, then there is a polynomial-time algorithm for all the problems in NP. Because of this, and because dedicated research has failed to find a polynomial algorithm for any NP-complete problem, once a problem has been proven to be NP-complete this is widely regarded as a sign that a polynomial algorithm for this problem is unlikely to exist.

NP-Hard Problems

To understand this, you should know about reduction. In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A reduction from one problem to another may be used to show that the second problem is as difficult as the first. Intuitively, problem A is reducible to problem B if an algorithm for solving problem B efficiently (if it existed) could also be used as a subroutine to solve problem A efficiently. We say A is reducible to B. Different types of reduction are discussed in a subsequent section.
Coming to NP-Hard, a problem C can be defined as NP-Hard iff every problem that is in NP is reducible to C.
NP-hard problems are often tackled with rules-based languages in areas such as:

  • Configuration
  • Data mining
  • Selection
  • Diagnosis
  • Process monitoring and control
  • Scheduling etc.

NP-complete Problems

The complexity class NP-complete (abbreviated NP-C or NPC) is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems and also in the set of NP-hard problems.
NP-complete is a subset of NP. A problem p in NP is also NP-complete if every other problem in NP can be transformed into p in polynomial time. If any single problem in NP-complete can be solved quickly, then every problem in NP can also be quickly solved, because the definition of an NP-complete problem states that every problem in NP must be quickly reducible to every problem in NP-complete (that is, it can be reduced in polynomial time). Because of this, it is often said that the NP-complete problems are harder or more difficult than NP problems in general.
Example: Boolean Satisfiability Problem

Satisfiability Problems

  • Boolean Satisfiability Problem:
    In computer science, Boolean, or propositional, satisfiability (abbreviated SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it establishes if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE. If no such assignments exist, the function expressed by the formula is identically FALSE for all possible variable assignments. In this latter case, it is called unsatisfiable, otherwise satisfiable. For example, the formula “a AND NOT b” is satisfiable because one can find the values a = TRUE and b = FALSE, which make (a AND NOT b) = TRUE. In contrast, “a AND NOT a” is unsatisfiable.
  • Circuit Satisfiability Problem:
    In theoretical computer science, the circuit satisfiability problem (also known as CIRCUIT-SAT, CircuitSAT, CSAT, etc.) is the decision problem of determining whether a given Boolean circuit has an assignment of its inputs that makes the output true.
    CircuitSAT has been proven to be NP-complete. In fact, it is a prototypical NP-complete problem; the Cookโ€“Levin theorem is sometimes proved on CircuitSAT instead of on SAT for Boolean expressions and then reduced to the other satisfiability problems to prove their NP-completeness.
  • 3-Satisfiablity:
    Like the satisfiability problem for arbitrary formulas, determining the satisfiability of a formula in conjunctive normal form where each clause is limited to at most three literals is NP-complete also; this problem is called 3-SAT, 3CNFSAT, or 3-satisfiability. It is used as a starting point for proving that other problems are also NP-hard. This is done by polynomial-time reduction from 3-SAT to the other problem.

Cook-Levin Theorem

The Cookโ€“Levin theorem, also known as Cook’s theorem, states that the Boolean satisfiability problem is NP-complete. That is, any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the problem of determining whether a Boolean formula is satisfiable.
The theorem is named after Stephen Cook and Leonid Levin.
An important consequence of the theorem is that if there exists a deterministic polynomial time algorithm for solving Boolean satisfiability, then there exists a deterministic polynomial time algorithm for solving all problems in NP. Crucially, the same follows for any NP complete problem.

Clique Problem

The clique problem refers to any of the problems related to finding particular complete subgraphs (“cliques”) in a graph, i.e., sets of elements where each pair of elements is connected.
A clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result many algorithms for finding cliques have been studied.

A clique in an undirected graph G = (V, E) is a subset of the vertex set C โŠ† V, such that for every two vertices in C, there exists an edge connecting the two. This is equivalent to saying that the subgraph induced by C is complete (in some cases, the term clique may also refer to the subgraph).
A maximal clique is a clique to which no more vertices can be added. A maximum clique is a clique that includes the largest possible number of vertices, and the clique number ฯ‰(G) is the number of vertices in a maximum clique of G.

Vertex Cover

A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. It is an NP-complete problem.
Formally, a vertex cover of a graph G is a set C of vertices such that each edge of G is incident to at least one vertex in C. The set C is said to cover the edges of G. The following figure shows examples of vertex covers in two graphs (and the set C is marked with red).

200px-Vertex-cover.svg

A minimum vertex cover is a vertex cover of smallest possible size. The vertex cover number tau is the size of a minimum vertex cover. The following figure shows examples of minimum vertex covers in the previous graphs.

200px-Minimum-vertex-cover.svg

Set Cover

The set covering problem (SCP) is a classical question in computer science and complexity theory.
It is a problem “whose study has led to the development of fundamental techniques for the entire field” of approximation algorithms.
Given a set of elements {1,2,…,m} (called the universe) and a set S of n sets whose union equals the universe, the set cover problem is to identify the smallest subset of S whose union equals the universe. For example, consider the universe U = {1, 2, 3, 4, 5} and the set of sets S = {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}}. Clearly the union of S is U. However, we can cover all of the elements with the following, smaller number of sets: {{1, 2, 3}, {4, 5}}.
In the set covering decision problem, the input is a pair ({U}, {S}) and an integer k; the question is whether there is a set covering of size k or less. In the set covering optimization problem, the input is a pair ({U}, {S}), and the task is to find a set covering that uses the fewest sets.
The decision version of set covering is NP-complete, and the optimization version of set cover is NP-hard .

IDE interfaces(I)

ide-controller2

Introduction

Storage is an important part of your system. In fact, most personal computers have one or more of the following storage devices:

  • Floppy drive
  • Hard drive
  • CD-ROM drive

Usually, these devices connect to the computer through an Integrated Drive Electronics (IDE) interface. Essentially, an IDE interface is a standard way for a storage device to connect to a computer. The term Integrated Drive Electronics refers not just to the connector and interface definition, but also to the fact that the drive controller is integrated into the drive, as opposed to a separate controller on or connected to the motherboard.

Evolution

IDE was created as a way to standardize the use of hard drives in computers. The basic concept behind IDE is that the hard drive and the controller should be combined. The controller is a small circuit board with chips that provide guidance as to exactly how the hard drive stores and accesses data.
Before IDE, controllers and hard drives were separate and often proprietary. In other words, a controller from one manufacturer might not work with a hard drive from another manufacturer. The distance between the controller and the hard drive could result in poor signal quality and affect performance. Obviously, this caused much frustration for computer users.

IBM introduced the AT computer in 1984 with a couple of key innovations.

  • The slots in the computer for adding cards used a new version of the Industry Standard Architecture (ISA) bus. The new bus was capable of transmitting information 16 bits at a time, compared to 8 bits on the original ISA bus.
  • IBM also offered a hard drive for the AT that used a new combined drive/controller. A ribbon cable from the drive/controller combination ran to an ISA card to connect to the computer, giving birth to the AT Attachment (ATA) interface.