## Introduction

Two basic rules:

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

Rule of product: If an action can be performed by making A choices followed by B choices, then it can be performed $A\times B$ 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 $n \ge k \ge 0$:

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 $n^k$ yes
Permutation $_{n}P_{r}$ yes
Multisubset $\left(\!\!{n\choose k}\!\!\right)$ no
combination $_{n}C_{k}$ or $n \choose k$ no

It is sufficent to implement $n!$.: the programming construct is recursion because $n !=n(n-1)!$.

### 12 -fold way

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

A B any at most at least
D D $b^{a}$ $_{b}P_{a}$ $S(a,b)!b$
I D $\binom {a+b-1} {a}$ $_{b}C_{a}$ $x - 1 \choose b-1$
D I $\sum ^{b}_{k=1} S(a,k)$ 1 if $a \le b$ else 0 $S(a,b)$
I I $\sum ^{b}_{k=1} p_{k}(a)$ 1 if $a \le b$ else 0 $p_{b}(a)$

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

In the above table, $p_{b}(a)$ is the number of ways to partition the number a as the sum of b positive numbers since the order don’t matter. For $1 \lt k \lt n$:

Multi-choosing $\left(\!\!{n\choose k}\!\!\right)$ 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 $a, b,..,c > 0 \text{ and } a+b+ ... +c = n$

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 $N$ 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 $2^{N}$ exponential.

## Order of the Growth

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

1. $\log N$
2. $N$ (Knuth shuffle)
3. $N \log N$ (Mergesort, QuickSort)
4. $N^{2}$ (selection =$N^{2}/2$, insertion = 1/4 $N^{2}$ )
5. $N^{3}$
6. $2^{N}$

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 $v \leq w$ and $w \leq v$ , then $v = w$
• Transitivity: if $v \leq w$ and $w \leq x$ , then $v \leq x$
• Totality: either $v \leq w$ or $w \leq v$ 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 ($N^{2}$) and average case is $1.39 N \log N$. 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^{2}/2$ $N^{2}/2$ $N^{2}/2$ N exchanges
insertions $N^{2}/2$ $N^{2}/4$ $N$ small N or partially
shell ? ? N tight code
merge $N \lg N$ $N \lg N$ $N \lg N$ $N \lg N$ guaranteed
quick $N^{2}/2$ $2N \lg N$ $N \lg N$ $N \lg N$ probabilistic guarantee
3-way quick $N^{2}/2$ $2N \lg N$ $N$ support duplicate keys
Heapsort $2N \lg N$ $2N \lg N$ $N \lg N$ 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 $2 \ln N$.

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

logarithmic ( $N \ln N$ is called linearithmic)

cubic ( $N^{2}$ is called quadratic)

## Saturday, May 14, 2016

### Recommender System Notes.

These are the notes I've achieved certificate from the well known Recommender System course.

## 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-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>
<title></title>
<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>

<servlet>
<servlet-name>dispatcher</servlet-name>
<servlet-class>org.springframework.web.servlet.DispatcherServlet</servlet-class>
</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-manager>

<!-- This configuration only for the active directory, for LDAP follow the above commented configuration-->
<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.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)) ){
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 {

}