Monday, May 16, 2016

Algorithm Notes - Analysis

Introduction

Two basic rules:

Rule of sum: if an action is performed making A choices or B choices, then it can be performed ways.

Rule of product: If an action can be performed by making A choices followed by B choices, then it can be performed ways.

Permutation: an ordered list where every object appears exactly once

combinations: When order is not important and the repetition is not allowed, the number of ways to choose k from the distinct n is as for :

in general, choosing k out of n is same as not choose n-k out of n.

According to the Pascal’s Triangle:

Again from the pascal triangle:

ordered repeating
sequence yes
Permutation yes
Multisubset no
combination or no

It is sufficent to implement .: the programming construct is recursion because .

12 -fold way

Here D - distinct and I - identical. In the following table, if then all the values of the at most are zeros. if , then all the values of the at least are zeros.

A B any at most at least
D D
I D
D I 1 if else 0
I I 1 if else 0

In the above table, Stirling numbers of the second kind count the number of ways to partition a set of a elements into b nonempty subsets. Stirling numbers of the first kind count permutations of a objects with exactly b cycles.

In the above table, is the number of ways to partition the number a as the sum of b positive numbers since the order don’t matter. For :

Multi-choosing is the number of ways to choose k objects from a set of n objects where order is not important but repetition is allowed.

Simplification,

Multinomial theorem where

Principle of Inclusion-Exclusion

Formula for the sterling number:

Java

There are two choices for the intermediate represetiation

  1. portable machine language
  2. graph based

Initially Java was created only with byte code interpreter. But current Java has Just In Time (JIT) compiler.

There are two popular representations:

  1. Stack based - 0 operand
  2. Register based - 3 operand

Java uses Stack based representation.

If you consider the for single loop in Java

for (int i =0; i < N; i++){
  ...
}

The running time cost of the above loop is means linear. The running time cost of the double loop is quadratic. Triple loop running time is cubic.The worst running time can be something like exponential.

Order of the Growth

Fortunately there are limited models to consider. Here the growth from best running time to worst:

  1. (Knuth shuffle)
  2. (Mergesort, QuickSort)
  3. (selection =, insertion = 1/4 )

Each instance of the java.util.ArrayList has the capacity, when reach to the capacity, the array need to be increased. Assume, each time ArrayList is double when it reach to the capacity then the equation is

This is because ArrayList is using java array of Object as a implementation. Advantages are that every operation takes constant time of Amortised time( Average running time per operation over the worst case sequence of operations) and less wasted space compared to linked list implementation because linked list is based on object.

Sorting

There java.lang.Comparable<T> and java.util.Comparator<T> is based on the total order which is a binary relation that satisfy:

  • Antisymmetry: if and , then
  • Transitivity: if and , then
  • Totality: either or or both

Quicksort is little bit faster than Mergesort because Quicksort doesn’t exchange the elements always. However, quick sort wort case running time is quadratic () and average case is . Quciksort random shuffle is the probabilistic guarantee to avoid worst case.

The java.utils.Arrays sort() method is using Quicksort for the primitives and Mergesort for the objects.

Dijkstart 3-way partitioning is the way to compromise with the duplicate keys because lower bound is reduced linearithmic to linear for most of the applications as follows:

Algorithm Worst Average Best Remarks
selection N exchanges
insertions small N or partially
shell ? ? N tight code
merge guaranteed
quick probabilistic guarantee
3-way quick support duplicate keys
Heapsort In-place algo. Inner loop is longer than quicksort. Poor use of cache memory. Not stable.

Searching

Binary Search Tree (BST) is a binary tree(BT) in symmetric order. BT can be either empty or two disjoint binary trees at left and right(left/right nodes can be null).

In the BST every node has a key:

  • Larger than all keys in its left subtree
  • smaller than all keys in its right subtree

For the N number of distinct values in random order, the number of comparisons are .

Red-Black trees

The java.util.TreeMap is based on the Red-black tree. Here some of the characteristics of the Red-Black tree:

  • Represents 2-3 tree as
  • use internal left-leaning link to glue three nodes which is red link
  • no node has two red links
  • every path from root to null link there are same number of black links.

Appendix

quadratic

logarithmic ( is called linearithmic)

cubic ( is called quadratic)

Saturday, May 07, 2016

Spring 3 Part 9: Spring Security LDAP integration

The expectation of this blog is to enable developer to start LDAP integration quickly and easily with Spring Security. I have used ApacheDS which is embedded in the Apache Studio. Here the steps:
  1. The DN dc=example,dc=com is a example domain controller you can easily follow the documentation.
  2. Here the ldif document

        #[1] create domain (distinguished name)
        dn: dc=example,dc=com
        objectclass: top
        objectclass: domain
        dc: example

        #[2] create people organizational unit
        dn: ou=people,dc=example,dc=com
        objectClass: organizationalUnit
        objectClass: top
        ou: people

        #[3] create a user 
        dn: uid=ojitha,ou=people,dc=example,dc=com
        objectClass: organizationalPerson
        objectClass: person
        objectClass: inetOrgPerson
        objectClass: top
        cn: Ojitha Hewa
        sn: Hewa
        uid: ojitha

        #[4] create group
        dn: ou=groups,dc=example,dc=com
        objectClass: organizationalUnit
        objectClass: top
        ou: groups

        #[5] add the user to User group
        dn: cn=User,ou=groups,dc=example,dc=com
        objectClass: groupOfUniqueNames
        objectClass: top
        cn: User
        uniqueMember: uid=ojitha,ou=people,dc=example,dc=com
as above document shows
1.  create the example distinguished name: `dc=example,dc=com`
2.  create the group `people` under the distinguished name
3.  create an `intOrgPerson` user, in this case I created one with my name for example
4.  Now you have to add this user to the `User` group in the in the `group` as shown in the above idlf.
5.  create a `User` group and add the `uid=ojitha` user to that group.

After import the above LDAP definition from a ldif file, don't forget to add ther userPassword to the user `ojitha` .
  1. need to import the above ldif document to the apacheds studio.
Now the interesting part. Here is the security configuration of the project you can download from the GitHub.
<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xmlns:security="http://www.springframework.org/schema/security"
       xsi:schemaLocation="http://www.springframework.org/schema/beans
       http://www.springframework.org/schema/beans/spring-beans.xsd
       http://www.springframework.org/schema/security
       http://www.springframework.org/schema/security/spring-security.xsd">

       <security:http auto-config="true">
              <security:intercept-url pattern="/hello/**" access="ROLE_USER"/>
       </security:http>

       <!--security:authentication-manager>
              <security:authentication-provider>
                     <security:user-service>
                            <security:user name="ojitha" password="test" authorities="ROLE_USER, ROLE_ADMIN" />
                            <security:user name="bob" password="bobspassword" authorities="ROLE_USER" />
                     </security:user-service>
              </security:authentication-provider>
       </security:authentication-manager-->

       <security:authentication-manager>
              <security:ldap-authentication-provider user-dn-pattern="uid={0},ou=people" server-ref="ldapServer" />
       </security:authentication-manager>

       <security:ldap-server id="ldapServer" url="ldap://localhost:10389/dc=example,dc=com"/>

</beans>
As shown in the above security-config.xml, The commented code shows the standard memory based user service and which has been replaced by the LDAP configuration. The most important information is written in the last line wth the ldap server information.
Browse with the url http://localhost:8080/spring3part14/hello which will direct you the page title Login Page with the heading Login with Username and Password which is not part of this project. You have to enter the User (that is ojitha) and the password you have given under the userPassword (in this case test) and press the Login button. You must be redirected to the hello.jsp which is under the WEB-INF/jsp/hello.jsp.
<%--
  Created by IntelliJ IDEA.
  User: ojitha
  Date: 7/05/2016
  Time: 6:05 PM
  To change this template use File | Settings | File Templates.
--%>
<%@ page contentType="text/html;charset=UTF-8" language="java" %>
<html>
<head>
    <title></title>
</head>
<body>
  Hello Ojitha
</body>
</html>
the location of the JPS has been configured in the follow dispatcher-servlet.xml:
<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xmlns:context="http://www.springframework.org/schema/context"
       xsi:schemaLocation="http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans.xsd http://www.springframework.org/schema/context http://www.springframework.org/schema/context/spring-context.xsd">

       <context:component-scan base-package="au.com.blogspot.ojitha.part14.controller"/>

    <bean class="org.springframework.web.servlet.view.InternalResourceViewResolver">
        <property name="prefix" value="WEB-INF/jsp/"/>
        <property name="suffix" value=".jsp"/>
    </bean>
</beans>
The hello.jsp is called by the controller
package au.com.blogspot.ojitha.part14.controller;

import org.springframework.stereotype.Controller;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestMethod;

/**
 * Created by ojitha on 7/05/2016.
 */
@Controller
public class HelloController {
    @RequestMapping(value = "/hello", method = RequestMethod.GET)
    public String sayHello(){
        return "hello";
    }
}
When user browse the http://localhost:8080/spring3part14/hello, request will be directed to this controller an the sayHello because controller is already mapped in the dipatcher-servlet.xml.
But before reach to the sayHello method …
These resources are protected in the security-config.xml file. Before rich to this method, LDAP security was injected via filter as shown in the web.xml file:
<!DOCTYPE web-app PUBLIC
        "-//Sun Microsystems, Inc.//DTD Web Application 2.3//EN"
        "http://java.sun.com/dtd/web-app_2_3.dtd" >

<web-app>
  <display-name>Archetype Created Web Application</display-name>
    <context-param>
        <param-name>contextConfigLocation</param-name>
        <param-value>
            /WEB-INF/security-config.xml
            /WEB-INF/applicationContext.xml
            /WEB-INF/dispatcher-servlet.xml
        </param-value>
    </context-param>

    <filter>
        <filter-name>springSecurityFilterChain</filter-name>
        <filter-class>org.springframework.web.filter.DelegatingFilterProxy</filter-class>
    </filter>
    <filter-mapping>
        <filter-name>springSecurityFilterChain</filter-name>
        <url-pattern>/*</url-pattern>
    </filter-mapping>
    <listener>
        <listener-class>org.springframework.web.context.ContextLoaderListener</listener-class>
    </listener>

    <servlet>
        <servlet-name>dispatcher</servlet-name>
        <servlet-class>org.springframework.web.servlet.DispatcherServlet</servlet-class>
        <load-on-startup>1</load-on-startup>
    </servlet>
    <servlet-mapping>
        <servlet-name>dispatcher</servlet-name>
        <url-pattern>/</url-pattern>
    </servlet-mapping>
</web-app>
This is the simplest example so far I have created on LDAP. I found OpenDJ is another good LDAP server to play.
Here the pom.xml:
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
  xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">

  <modelVersion>4.0.0</modelVersion>

  <groupId>au.com.blogspot.ojitha</groupId>
  <artifactId>spring3part14</artifactId>
  <packaging>war</packaging>
  <version>1.0-SNAPSHOT</version>
  <name>spring3part14 Maven Webapp</name>
  <url>http://maven.apache.org</url>

  <properties>
    <spring.version>3.2.9.RELEASE</spring.version>
    <jdk.version>1.6</jdk.version>
  </properties>

  <dependencies>

    <!-- Spring -->
    <dependency>
      <groupId>org.springframework</groupId>
      <artifactId>spring-web</artifactId>
      <version>${spring.version}</version>
    </dependency>

    <dependency>
      <groupId>org.springframework</groupId>
      <artifactId>spring-webmvc</artifactId>
      <version>${spring.version}</version>
    </dependency>

    <dependency>
      <groupId>org.springframework</groupId>
      <artifactId>spring-core</artifactId>
      <version>${spring.version}</version>
    </dependency>

    <dependency>
      <groupId>org.springframework</groupId>
      <artifactId>spring-core</artifactId>
      <version>${spring.version}</version>
    </dependency>

    <dependency>
      <groupId>org.springframework.security</groupId>
      <artifactId>spring-security-config</artifactId>
      <version>${spring.version}</version>
    </dependency>

    <dependency>
      <groupId>org.springframework.security</groupId>
      <artifactId>spring-security-web</artifactId>
      <version>${spring.version}</version>
    </dependency>

    <dependency>
      <groupId>org.springframework.security</groupId>
      <artifactId>spring-security-ldap</artifactId>
      <version>${spring.version}</version>
    </dependency>

    <dependency>
      <groupId>org.springframework</groupId>
      <artifactId>spring-test</artifactId>
      <version>${spring.version}</version>
    </dependency>

    <dependency>
      <groupId>junit</groupId>
      <artifactId>junit</artifactId>
      <version>3.8.1</version>
      <scope>test</scope>
    </dependency>
  </dependencies>
  <build>
    <finalName>spring3part14</finalName>
    <plugins>
      <plugin>
        <groupId>org.apache.maven.plugins</groupId>
        <artifactId>maven-compiler-plugin</artifactId>
        <version>3.0</version>
        <configuration>
          <source>${jdk.version}</source>
          <target>${jdk.version}</target>
        </configuration>
      </plugin>
    </plugins>
  </build>
</project>
Windows Active Directory configuration is different. The spring security configuration is different as follows:
<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xmlns:security="http://www.springframework.org/schema/security"
       xmlns:context="http://www.springframework.org/schema/context"
       xsi:schemaLocation="http://www.springframework.org/schema/beans
       http://www.springframework.org/schema/beans/spring-beans.xsd
       http://www.springframework.org/schema/security
       http://www.springframework.org/schema/security/spring-security.xsd http://www.springframework.org/schema/context http://www.springframework.org/schema/context/spring-context.xsd">

       <context:property-placeholder location="classpath*:ldap.properties"/>

       <security:http auto-config="true" >
            <security:intercept-url pattern="/hello/**" access="ROLE_USER"/>
       </security:http>


       <security:authentication-manager>
           <security:authentication-provider ref="adAuthenticationProvider"/>
       </security:authentication-manager>


       <!-- This configuration only for the active directory, for LDAP follow the above commented configuration-->
       <bean id="adAuthenticationProvider"
             class="org.springframework.security.ldap.authentication.ad.ActiveDirectoryLdapAuthenticationProvider">
              <constructor-arg value="${ad.server.domain}"/>
              <constructor-arg value="${ldap.server.url}"/>
           <property name="authoritiesMapper" ref="GAMapper"/>
           <property name="searchFilter" value="${ad.search.filter}"/>
           <property name="convertSubErrorCodesToExceptions" value="true"/>
           <property name="useAuthenticationRequestCredentials" value="true"/>

       </bean>

       <bean id="GAMapper" class="au.com.blogspot.ojitha...DGAMapper">
           <property name="userGroups" value="${ad.wssuite.group}"/>
       </bean>
May be most interesting property is searchFilter which is available since Spring 3.2.9+. The default is always (&(objectClass=user)(userPrincipalName={0})) but the problem is if your principal name is not ending with the domain, search will be failed. For example, my principle name is such as ojithak@gmail.com which is then never find because domain is incompatibility. But as shown in the following properties file if extensionAttrib = ojithak@ad.ojitha.blogspot.com.auin the AD, then search will be successful because domain ad.ojitha.blogspot.com.au is compatible. Now you have to login with the username ojithak.
    ldap.server.url=ldap://12.25.192.246:389
    ad.server.domain=ad.ojitha.blogspot.com.au
    ad.search.filter=(&(objectClass=user)(extensionAttrib={0}))
    ad.wssuite.group=auth_users
Here the DGMapper for authorites
    public class IDGAMapper implements GrantedAuthoritiesMapper {

    final Logger logger = LoggerFactory.getLogger(IDGAMapper.class);
    private String userGroup;


    @Override
    public Collection<? extends GrantedAuthority> mapAuthorities(Collection<? extends GrantedAuthority> authorities) {
        Set<GrantedAuthority> roles = new HashSet<GrantedAuthority>();
        if (authorities.contains(new SimpleGrantedAuthority(this.userGroup)) ){
            roles.add(UserRoels.ROLE_USER);
            logger.debug("user is successfully authorized.");
        } else logger.warn("User is unauthorized");

        return roles;
    }

    public String getUserGroup() {
        return this.userGroup;
    }

    public void setUserGroups(String userGroup) {
        this.userGroup = userGroup;
    }
}
And
    public enum UserRoels implements GrantedAuthority {

    ROLE_USER; // read only role.

    @Override
    public String getAuthority() {
        return name();
    }
}
Download from the GitHub.