Logback

Description

Logback is a log module.

logger, appender, layout are tags of logback

Configuration

1. Create a logback.xml in resources package

2. Defines some properties of the logback configuration.

3. Defines the appenders.

Info, Error is the same as Debug.

4. Defines the logger

Debug: We should change all MaxHistory to maxHistory in the appenders.
Debug: We should change all append-ref to appender-ref in the appenders.

Practice

1. Initialize a Logger instance in the AreaController.

2. Add some test info statements in the function.

3. Check the console and the file.
   

Here we can search catalina.base to get to the directory of our log files.

Notes of O2O projcet

Tech stack

1. SSM: Spring, SpringMVC, MyBatis

   Project Structure

   General Structure

   Front End

   

Shop

Administrator

Product

Concrete Class

Area

1. Build the class in Java

1. Build the table in database

Q: Why do we use DateTime rather than TimeStamp in mySQL?
A: Because DateTime has a larger range of 0000 -> 9999 year, while TimeStamp can only varies between 1970 and 2037. However, TimeStamp can automatically adjust to the current time zone.

Q: What’s the difference between InnoDB and MYISAM?
A: MYISAM has a table lock that doesn’t allow multiple threads modifying the table while current thread working on it. InnoDB is locked by row. Also, MYISAM has a better read performance, while InnoDB has a better write performance.

PersonInfo

WechatAuth and LocalAuth

Here we should also change open_id in tb_wechat_auth into a unique key.

Q: Why do we want to set username to be unique?
A: Because we want to improve the performance of lookup.

HeadLine

ShopCategory

parentId is like a recurrence relation here. if the parent is null, that means the category is the root. Any child node can traverl all the way back to root.

Shop

ProductCategory

ProductImg

Product

Configurations

Packages of the projects

Dependencies

1. Junit

   Has to be higher than 4.12, otherwise there’s error.

2. Logback
   

Here we want to remove \test\, since we also want it to appear in the actual scope.

3. spring

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

   <properties> <spring.version>4.3.7.RELEASE</spring.version> </properties> <dependencies> <!-- Spring --> <!-- 1)包含Spring 框架基本的核心工具类。Spring 其它组件要都要使用到这个包里的类，是其它组件的基本核心 --> <dependency> <groupId>org.springframework</groupId> <artifactId>spring-core</artifactId> <version>${spring.version}</version> </dependency> <!-- 2)这个jar 文件是所有应用都要用到的，它包含访问配置文件、创建和管理bean 以及进行Inversion of Control / Dependency Injection（IoC/DI）操作相关的所有类。如果应用只需基本的IoC/DI 支持，引入spring-core.jar 及spring-beans.jar 文件就可以了。 --> <dependency> <groupId>org.springframework</groupId> <artifactId>spring-beans</artifactId> <version>${spring.version}</version> </dependency> <!-- 3)这个jar 文件为Spring 核心提供了大量扩展。可以找到使用Spring ApplicationContext特性时所需的全部类，JDNI 所需的全部类，instrumentation组件以及校验Validation 方面的相关类。 --> <dependency> <groupId>org.springframework</groupId> <artifactId>spring-context</artifactId> <version>${spring.version}</version> </dependency> <!-- 4) 这个jar 文件包含对Spring 对JDBC 数据访问进行封装的所有类。 --> <dependency> <groupId>org.springframework</groupId> <artifactId>spring-jdbc</artifactId> <version>${spring.version}</version> </dependency> <!-- 5) 为JDBC、Hibernate、JDO、JPA等提供的一致的声明式和编程式事务管理。 --> <dependency> <groupId>org.springframework</groupId> <artifactId>spring-tx</artifactId> <version>${spring.version}</version> </dependency> <!-- 6)Spring web 包含Web应用开发时，用到Spring框架时所需的核心类，包括自动载入WebApplicationContext特性的类、Struts与JSF集成类、文件上传的支持类、Filter类和大量工具辅助类。 --> <dependency> <groupId>org.springframework</groupId> <artifactId>spring-web</artifactId> <version>${spring.version}</version> </dependency> <!-- 7)包含SpringMVC框架相关的所有类。 --> <dependency> <groupId>org.springframework</groupId> <artifactId>spring-webmvc</artifactId> <version>${spring.version}</version> </dependency> <!-- 8)Spring test 对JUNIT等测试框架的简单封装 --> <dependency> <groupId>org.springframework</groupId> <artifactId>spring-test</artifactId> <version>${spring.version}</version> <scope>test</scope> </dependencies>

4. Servlet
   Servlet serevice dependency

   1 2 3 4 5 6

   <!-- Servlet web --> <dependency> <groupId>javax.servlet</groupId> <artifactId>javax.servlet-api</artifactId> <version>4.0.1</version> </dependency>

5. json support for front-end

   1 2 3 4 5 6

   <!-- json解析 --> <dependency> <groupId>com.fasterxml.jackson.core</groupId> <artifactId>jackson-databind</artifactId> <version>2.9.9</version> </dependency>

6. spring-core dependency

   1 2 3 4 5 6

   <!-- Map工具类 对标准java Collection的扩展 spring-core.jar需commons-collections.jar --> <dependency> <groupId>commons-collections</groupId> <artifactId>commons-collections</artifactId> <version>3.2.2</version> </dependency>

7. mybatis dependency

   1 2 3 4 5 6 7 8 9 10 11

   <!-- DAO: MyBatis --> <dependency> <groupId>org.mybatis</groupId> <artifactId>mybatis</artifactId> <version>3.5.1</version> </dependency> <dependency> <groupId>org.mybatis</groupId> <artifactId>mybatis-spring</artifactId> <version>2.0.1</version> </dependency>

8. mysql
   mysql-connector-java supports sql api
   com.mchange supports connection pool

1
2
3
4
5
6
7
8
9
10
11
12

<!-- 数据库 -->
<dependency>
    <groupId>mysql</groupId>
    <artifactId>mysql-connector-java</artifactId>
    <version>8.0.16</version>
</dependency>
<!-- https://mvnrepository.com/artifact/com.mchange/c3p0 -->
<dependency>
    <groupId>com.mchange</groupId>
    <artifactId>c3p0</artifactId>
    <version>0.9.5.4</version>
</dependency>

1
2
3
4
5
6
7
8
9
10

什么是连接池
数据库连接池负责分配、管理和释放数据库连接，它允许应用程序重复使用一个现有的数据库连接，而不是再重新建立一个。

为什么要使用连接池
 数据库连接是一种关键的有限的昂贵的资源，这一点在多用户的网页应用程序中体现得尤为突出。  一个数据库连接对象均对应一个物理数据库连接，每次操作都打开一个物理连接，使用完都关闭连接，这样造成系统的 性能低下。 数据库连接池的解决方案是在应用程序启动时建立足够的数据库连接，并讲这些连接组成一个连接池(简单说：在一个“池”里放了好多半成品的数据库联接对象)，由应用程序动态地对池中的连接进行申请、使用和释放。对于多于连接池中连接数的并发请求，应该在请求队列中排队等待。并且应用程序可以根据池中连接的使用率，动态增加或减少池中的连接数。 连接池技术尽可能多地重用了消耗内存地资源，大大节省了内存，提高了服务器地服务效率，能够支持更多的客户服务。通过使用连接池，将大大提高程序运行效率，同时，我们可以通过其自身的管理机制来监视数据库连接的数量、使用情况等。 
--------------------- 
作者：CrankZ 
来源：CSDN 
原文：https://blog.csdn.net/crankz/article/details/82874158 
版权声明：本文为博主原创文章，转载请附上博文链接！

Configurations

1. jdbc
   File name is jdbc.properties, save it under src/main/resources

   1 2 3 4

   jdbc.driver = com.mysql.jdbc.Driver jdbc.url = jdbc:mysql://localhost:3306/o2o?useUnicode=true&characterEncoding=utf8 jdbc.username = root #jdbc.password = password

2. mybatis
   File name is mybatis-config.xml, save it under src/main/resources

   1 2 3 4 5 6 7 8

   <!-- 使用jdbc的getGeneratedKeys获取数据库自增主键值 --> <setting name="useGeneratedKeys" value="true" /> <!-- 使用列标签替换列别名 默认:true --> <setting name="useColumnLabel" value="true" /> <!-- 开启驼峰命名转换:Table{create_time} -> Entity{createTime} --> <setting name="mapUnderscoreToCamelCase" value="true" />

3. spring
   spring-dao.xml

   1 2 3 4 5

   <!-- 配置整合mybatis过程 --> <!-- 1.配置数据库相关参数properties的属性：${url} --> <!-- 2.配置连接池属性 --> <!-- 3.配置SqlSessionFactory对象 --> <!-- 4.配置扫描Dao接口包，动态实现Dao接口，注入到spring容器中 -->

spring-service.xml

1
2
3
4

<!-- 扫描service包下所有使用注解的类型 -->
  <!-- 配置事务管理器 -->
      <!-- 注入数据库连接池 -->
<!-- 配置基于注解的声明式事务 -->

spring-web.xml

1
2
3
4
5

<!-- 配置SpringMVC -->
<!-- 1.开启SpringMVC注解模式 -->
  <!-- 2.静态资源默认servlet配置 (1)加入对静态资源的处理：js,gif,png (2)允许使用"/"做整体映射 -->
<!-- 3.定义视图解析器 -->
<!-- 4.扫描web相关的bean -->

4. web.xml
   Integrate the configuration of Spring

   1 2 3 4 5 6 7 8 9 10 11 12 13

   <servlet> <servlet-name>spring-dispatcher</servlet-name> <servlet-class>org.springframework.web.servlet.DispatcherServlet</servlet-class> <init-param> <param-name>contextConfigLocation</param-name> <param-value>classpath:spring/spring-*.xml</param-value> </init-param> </servlet> <servlet-mapping> <servlet-name>spring-dispatcher</servlet-name> <!-- 默认匹配所有的请求 --> <url-pattern>/</url-pattern> </servlet-mapping>

5. Review
   

Test for DAO

Take Area class as an example, we try to implement its DAO.

Q: What is DAO?
A: DAO是Data Access Object数据访问接口，数据访问：顾名思义就是与数据库打交道。In computer software, a data access object (DAO) is an object that provides an abstract interface to some type of database or other persistence mechanism. By mapping application calls to the persistence layer, the DAO provides some specific data operations without exposing details of the database. This isolation supports the single responsibility principle. It separates what data access the application needs, in terms of domain-specific objects and data types (the public interface of the DAO), from how these needs can be satisfied with a specific DBMS, database schema, etc. (the implementation of the DAO).

We first implement the interface of user’s operation(such as insertion, deletion, update, query), and then map the DAO in the myBatis (mapper package) to the entity class. There we define the type of the operation and return type, then we can write SQLs to execute the actual queries.

Step:

1. create interface AreaDao in o2o.dao
2. create config file AreaDao.xml in resources.mapper

   Here we don’t need to implement the actual AreaDao class but simply provide an interface is enough. MyBatis will do the job for us. We just need to map it to MyBatis.

3. Specify the namespace, id, and resultType
   
4. Write the test for the dao.

First, create a BaseTest class in test/…/o2o/, which is used to initialize Spring and Junit configuration

@RunWith and @ContextConfiguratiion are often used together. First one indicate what test runner we want to use for junit. @ContextConfiguration indicates the Config file of Spring DAO.

Then create a concrete test class AreaDaoTest in ~/o2o.dao extending the BaseTest.

@Autowired is used to assemble the DAO class by Spring. Every time we declare an interface with @Autowired, Spring will automatically use its implementation class.

5. Debug.

• in jdbc.properties, password line cannot be omitted
• jdbc.driver is deprecated, shoule be changed to com.mysql.cj.jdbc.Driver
• Add &serverTimezone=UTC to jdbc url
• Make sure all paths are configured correctly.

Test for Service

1. Create AreaService interface in service package, which has a getAreaList API.
2. Create AreaServiceImpl class in service.impl package, create a DAO and implement the API. Just simply return the DAO’s queryArea() API.

3. Create serevice.AreaServiceTest in test package, and add config file to the BaseTest.

   1	@ContextConfiguration({"classpath:spring/spring-dao.xml", "classpath:spring/spring-service.xml"})

4. Same as testDao, test the getAreaList() API we defined in interface AreaService. Here we changed a way to test it. Notice that since we configure the mapper with AreaDao.xml, we know that the result return from the database is exactly the field we defined in entity class Area.

Test for Controller

1. Since we use a super admin to control the Area, we create a superadmin package to manage related behaviour. Create web.superadmin.AreaController.
2. Implement this class.

@Controller tag means this is an implementation class of Controller(just like @Service). Here we don’t have a Controller interface.

@RequestMapping means when we have a request calling superadmin, we direct it to our current class AreaController. Same as the following. Notice that we use lower case here for url.

@ResponseBody is used to write the data we have in controller to the body of response. Could be html, json or xml. In this case, we return json.

The reason why we use a Map<String, Object> here is because this data structure is like a json. We can put whatever we want as the value of a certain String, including error message.

We can test it at http://localhost:8080/superadmin/listarea

and get something like

1

{"total":2,"rows":[{"areaId":2,"areaName":"Chicago","priority":2,"createTime":null,"lastEditTime":null},{"areaId":1,"areaName":"Seattle","priority":1,"createTime":null,"lastEditTime":null}]}

Debug: There’s a serious bug about bean multipartResolver. Annotate it will be fine.

Review

1. Create the interface in DAO, and create certain APIs
2. Create config file in mapper for this DAO, and Use SQL to execute operations on Database.
3. Call DAO API in Service
4. Call Service API in Controller and return it to front end(write to response).

Algorithm Review

Greedy

Monotonic Stack

Binary Search

Prefix Sum

Divide & Conquer

DP

Design Datastructre

Sliding Window

Tree

Graph

UnionFind

SubMatrix

For this type of question, always try to reduce the time complexity to n^3. Try to fix an edge/point and search other points.

String Parsing

HashMap

Substring/Subsequence/SubArray

Trie

Math

Stack

Segmant Tree

Random

Backtrack

Bucket Sort

Class 1 05/06/2019

Fibonacci numbers

Fibonacci numbers (Exponential Algorithm)

1
2
3
4
5
6

0, 1, 1, 2, 3, 5, 8, 13, 21
a0, a1, a3, a3, a4, a5, a6, a7

an = an-1 + an-2
a0 = 0
a1 = 1

Code

1
2
3
4
5
6

fib1(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fib1(n-1) + fib1(n-2);
}

Time Complexity

Answer O(2^n)

Less intuitive, not like

1
2

for i in range(10):
    a[i] = a[i-1] + 2

Recursion Tree

$ T(n) = \text {runtime of fib1(n)}$

1
2
3
4
5
6
7

              T(n)
       /              \
    T(n-1)           T(n-2)
   /     \           /     \
T(n-2)   T(n-3)    T(n-3)   T(n-4)
            ......
T(1)    T(0)    T(1)    T(0) ...

When hit 0 or 1, the recursion ends.

1
2
3
4
5
6
7
8
9
10
11

            /\
           /  \
          /____\
         /     /
        /  _ /
       / _/
      /_/
left side = n
right side = n/2

T(n) = num of nodes in this recursion tree

1
2
3
4
5

in first half of this tree
            /\
           /  \
          /____\
num of nodes = 2^k-1 = 2 ^ (n/2) - 1

Thus we have

$ 2 ^ {n/2} <= T(n) <= 2 ^ n $

Therefore

$ 2 ^ {n/2} = (\sqrt {2}) ^ n ~= 1.4n $

Clearly, this is a bad time complexity algorithm.

1
2
3
4
5
6
7
8
9

                  T(n)
           /              \
        T(n-1)           T(n-2)
       /     \           /     \
    T(n-2)   T(n-3)    T(n-3)   T(n-4)

There are a lot of repetition in the process of calculation. 

e.g. T(n-2) T(n-3)

Linear algorithm

Code

1
2
3
4
5
6
7
8

fib2(int n) {
    int[] A = new int[n];
    A[0] = 0; A[1] = 1;
    for (int i = 2; i <= n; i++) {
        A[i] = A[i-1] + A[i-2];
    }
    return A[n];
}

Time Complexity

Linear time: O(n)

Constant space algorithm

Code

1
2
3
4
5
6
7
8

fib2(int n) {
    int[] A = new int[2];
    A[0] = 0; A[1] = 1;
    for (int i = 2; i <= n; i++) {
        A[i%2] = A[(i-1)%2] + A[(i-2)%2];
    }
    return A[n%2];
}

Analysis

1
2
3

i varies between 0 and 1
A[1] = A[0] + A[1]
A[0] = A[1] + A[0]

Matrix solution

Idea

$$
A = \left[
\begin{matrix}
1 & 1 \
1 & 0
\end{matrix}
\right]
$$

$$
A^2 = \left[
\begin{matrix}
1 & 1 \
1 & 0
\end{matrix}
\right] *
\left[
\begin{matrix}
1 & 1 \
1 & 0
\end{matrix}
\right] =
\left[
\begin{matrix}
2 & 1 \
1 & 1
\end{matrix}
\right]
$$

1
2
3
4
5
6
7
8
9
10
11
12
13

A = | 1  1 | = | a2  a1 |
    | 1  0 |   | a1  a0 |

A^2 = | 1  1 |    | 1  1 |      | 2  1 |   | a3  a2 |
      | 1  0 | *  | 1  0 |  =   | 1  1 | = | a2  a1 |

A^3 = | 2  1 |    | 1  1 |      | 3  2 |   | a4  a5 |
      | 1  1 | *  | 1  0 |  =   | 2  1 | = | a3  a2 |           

.....

 A^k = | a(k+1)  ak   |   
       | ak      ak-1 |

Time Complexity

Basic: O(n)

Optimized: O(logn)

Strategy

Since we are dealing with A^n, the optimized time complexity of pow(x, n) is O(logn)

1
2
3
4

A^n =   |A(n/2)^2         | n is even
        |A((n-1)/2)^2 * A | n is odd

A^64 = (A^32)^2 = ((A^16))^2^2 = A^(2^6)

Asymptotic Notation

Comparison of each notation

Mathematical Derivation

f(n) = O(g(n))

1
2

iff exists constants C and n0
s.t. when n > n0, f(n) <= C * g(n)

1
2
3

lim(n->inf) f(n)/g(n) =     0           | fn = O/o(g(n))
                            constant    | fn = O/Θ/Ω(g(n))
                            inf         | fn = Ω/ω(g(n))

Practice:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

lim(n->inf) (100n)/(n+100) = 100 
fn = O/Θ/Ω(g(n))

f(n) = nlgn   g(n) = n^2
f(n) = O/o(g(n))

f(n) = 2^n   g(n) = 3^n
f(n) = O/o(g(n))
lim(n->inf) f(n)/g(n) = lim(n->inf) (2/3)^n = 0

f(n) = n+3   g(n) = 2 * sqrt(n)
f(n) = Ω/ω(g(n))


f(n) = log2(n)   g(n) = log3(n)
f(n) = Ω/O/Θ(g(n))
lim(n->inf) f(n)/g(n) = lim(n->inf) log2n/log3n = log3/log2

f(n) = (logn)^2   g(n) = log(n^2) = 2logn
f(n) = Ω/ω(g(n))

Master’s Theorem

Idea of merge sort

T(n) = 2T(n/2) + n

1
2
3
4
5
6
7

             T(n) n                         | n
          /          \
    T(n/2) n/2          T(n/2) n/2          | n
   /     \           /     \
T(n/4)   T(n/4)    T(n/4)   T(n/4)          | n
            ......
T(1)    T(1)    T(1)    T(1) ...            | n

Time Complexity of merge sort

T(n) = height T(level) = logn n = nlogn

Master’s Theorem

1
2
3
4
5
6
7

T(n) = a * T(n/b) + n^c, where a, b, c are constants

Examples:
T(n) = 2 * T(n/2) + n
T(n) = 8 * T(n/2) + n^2
T(n) = T(n/2) + 1
T(n) = T(n/3) + T(2n/3) + n  (Not master's theorem)

Now we have to compare logb(a) and c

• logb(a) > c, T(n) = Θ(n^(logb(a)))
• logb(a) = c, T(n) = Θ((n^c) * logn)
• logb(a) < c, T(n) = Θ(n^c)

Practice

1
2
3
4
5
6

T(n) = T(n/2) + 1   T(n) = Θ(lgn)
T(n) = 8T(n/2) + n^2   T(n) = Θ(n^3)
T(n) = 7T(n/2) + n^2   T(n) = Θ(n^(log2(7)))
T(n) = 4T(n/2) + n^2   T(n) = Θ(n^2 * (logn))
T(n) = T(n/2) + n  T(n) = Θ(n)
T(n) = T(n-1) + n  (Not master's theorem)

Draw the Recursion Tree of the last one

1
2
3
4
5
6
7
8
9
10
11
12
13

Recursion Tree of T(n) = T(n-1) + n 

        T(n) n
        T(n-1) n-1
        T(n-2) n-2
        ...
        T(1) 1




T(n) = 1 + 2 + 3 + ... + n = n(n+1)/2
Θ(n) = n^2

Other useful Summation Formula

1
2
3
4
5

1 + 2 + 3 + .. + n = n(n+1)/2

q^0 + q^1 + q^2 + ... q^n = (q^(n+1) -1)/(q-1)

1 + 1/2 + 1/3 + ... + 1/n = Θ(ln(n))

Normal case

T(n) = T(n/3) + T(2n/3) + n

1
2
3
4
5
6
7

             T(n) n                         | n
          /          \
    T(n/3) n/3        T(2n/3)  2n/3         | n
   /     \           /     \
T(n/9)   T(2n/9)    T(2n/9)   T(4n/9)       | n
            ......
T(1)    T(1)    T(1)    T(1) ...            | n

1
2
3
4
5
6
7
8
9
10
11
12
13
14

            /\
           /  \
          /____\
          \     \
            \    \
              \   \
                \_\

left side = log3n
right side = log3/2(n)

T(n) = num of nodes in this recursion tree

n * log3(n) <= T(n) <= n * log3/2(n)

Time Complexity of Normal recursion tree

T(n) = Θ(nlgn)

Some examples

1
2
3

T(n) = T(n/4) + T(3n/4) + n             T(n) = Θ(nlgn)
T(n) = T(n/1000) + T(999n/1000) + n     T(n) = Θ(nlgn)
T(n) = T(n-1) + T(1) + n                T(n) = Θ(n^2)

Quick Sort

Partition

1
2
3
4
5
6
7
8
9
10

Given array like

|1 |9 |2 |8 |3 |8 |7 |5 |6 |


Choose a pivot, put all num < pivot in left, others in right

|    nums <=  pivot  |pivot|  nums > pivot   |

The process is partition(A[], i, j)

Code

1
2
3
4
5
6

QuickSort(int[] A, int i, int j) {
    if (i >= j) {return;}
    int pivot_pos = Partition(A, i, j);
    QuickSort(A, i, pivot_pos-1);
    QuickSort(A, pivot_pos+1, j);
}

Time Complexity

1
2
3
4
5
6

T(n) = 2T(n/2) + n = Θ(nlogn)
T(n) = T(n/3) + T(2n/3) + n = Θ(nlogn)
T(n) = T(n/1000) + T(999n/1000) + n = Θ(nlogn)

Worst Case
T(n) = T(n-1) + n = Θ(n^2)

Average T(n) = Θ(nlogn)

Worst T(n) = Θ(n^2)

Code of Partition

1
2
3
4
5
6

pivot = A[j]
| i |  ... | p | p+1 |  ...  | cur |  ...  | j |

i - p: <= pivot
p - p+1: > pivot
cur: current pointer

• A[cur] > pivot

  1

  cur += 1

• A[cur] <= pivot

  1 2 3

  swap(A[cur], A[p+1]); p += 1; cur += 1

1
2
3
4
5
6
7
8
9
10
11
12

Partition(int[] A, int i, int j) {
    int pivot = A[j];
    int p = i - 1;
    for (int cur = i; cur <= j-1; cur++) {
        if (A[cur] <= pivot) {
            swap(A[cur], A[p+1]);
            p += 1;
        }
    }
    swap(A[j], A[p+1]);
    return p+1;
}

Class 2 05/13/2019

Review

Review of quicksort

Stable Sort

1
2
3
4
5
6
7

| ... | 5(1) | ...  |  ...  | 5(2) |  ...  |

After sort

| ... | 5(1)| 5(2) |  ...  |

If two 5 are still in their relative positions, then this is a stable sort.

Runtime of Quick Sort

Runtime:

Average: $O(nlogn)$
Worst: $O(n^2)$

The worst case is $T(n) = T(n-1) + n$

Pivot Selection

• Median of Three

1

| i | ... | (i+j)/2 | ... |  j  |

Heap Sort

Types of Heap

1. Max Heap
2. Min Heap

Operations (of Heap)

• Insert(E) $O(logn)$
• getMax() $O(1)$
• deleteMax() $O(logn)$

Operations (of Sorted Array)

• Insert(E) $O(n)$
• getMax() $O(1)$
• deleteMax() $O(1)$

Comparison of array and heap

The worst time of heap operation is logn.

However, A sorted array takes On time to insert, which is the bottleneck of the overall time complexity.

Logical View and Physical View

Logical View

1
2
3
4
5
6
7
8
9

          7(1)
         /    \
      3(2)      6(3)
     /   \       /
   1(4)  2(5)  5(6)

Almost-Full Binary Tree
Parent must be >= both children

Physical View

1
2
3

               1   2   3   4   5   6
Array        | 7 | 3 | 6 | 1 | 2 | 5 |

helper functions of heap

i is the index

parent(i) = i / 2
leftChild(i) = i 2
rightChild = i 2+1

getMax() O(1)

getMax() - return A[1]

insert() O(logn)

Case 1

1
2
3
4
5
6
7

           7(1)
         /      \
      3(2)      6(3)
     /   \       / \
   1(4)  2(5)  5(6) 3(7)

No need to adjust

Case 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

           7(1)
         /      \
      3(2)      6(3)
     /   \       / \
   1(4)  2(5)  5(6) 8(7)

Swap 8 with 6

           7(1)
         /      \
      3(2)      8(3)
     /   \       / \
   1(4)  2(5)  5(6) 6(7)

Swap 7 with 8

           8(1)
         /      \
      3(2)      7(3)
     /   \       / \
   1(4)  2(5)  5(6) 6(7)  

Complete inserting.

                        1   2   3   4   5   6   7
Array(after insert)   | 8 | 3 | 7 | 1 | 2 | 5 | 6|

Code of insert()

1
2
3
4
5
6
7
8
9
10
11
12
13

void insert(int e) {
    // increase the size n of the heap
    n += 1;
    // insert the item to heap A
    A[n] = e;
    // Adjust from index i=n
    int i = n;
    // if cur node has a parent and the parent is smaller
    while (parent(i) > 0 && A[parent(i)] < A[i]) {
        swap(A[parent(i)], A[i]);
        i = parent(i);
    }
}

deleteMax()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

           8(1)
         /      \
      3(2)      7(3)
     /   \       / \
   1(4)  2(5)  5(6) 6(7)  

Swap 6 with 8, and delete 8

           6(1)
         /      \
      3(2)      7(3)
     /   \       / 
   1(4)  2(5)  5(6) 

                      1   2   3   4   5   6  
Array(after swap)   | 6 | 3 | 7 | 1 | 2 | 5 | 

Swap 6 with 7

           7(1)
         /      \
      3(2)      6(3)
     /   \       / 
   1(4)  2(5)  5(6) 

                      1   2   3   4   5   6  
Array(after swap)   | 7 | 3 | 6 | 1 | 2 | 5 | 

Heap is balanced. 
deleteMax() completed.

heapify()

1
2
3
4
5
6
7
8
9
10

           6(1)
         /      \
      3(2)      7(3)
     /   \       / 
   1(4)  2(5)  5(6)  

The subTree of root 3 is a MaxHeap
The subTree of root 7 is a MaxHeap
However, the tree of root 6 is not a MaxHeap.
Now we need the heapify().

Code of heapify()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void heapify(int[] A, i) {
    int largest = i;
    // Find the largest of cur root(i) and its children
    // if left child exists and left child is bigger than cur root
    if (leftChild(i) <= n && A[leftChild(i)] > A[largest]) {
        largest = leftChild(i);
    }
    // if left child exists and left child is bigger than cur root
    if (rightChild(i) <= n && A[rightChild(i)] > A[largest]) {
        largest = rightChild(i);
    }

    // check largest
    if (largest == i) return;

    // let the cur largest node be the root
    swap(A[i], A[largest]);
    // continue heapifying down the swapped node recursively
    heapify(A, largest);
}

Code of deleteMax()

1
2
3
4
5
6
7
8

void deleteMax() {
    // swap the cur root with the last node
    swap(A[1], A[n]);
    // delete the last node
    n -= 1;
    // heapify the whole heap
    heapify(A, 1);
}

Heap Sort

Max Heap

1
2
3
4
5
6
7
8
9

          1   2   3   4   5   6  
Array   | 7 | 3 | 6 | 1 | 2 | 5 | 

Pretend we are deleting the max val.(deleteMax())

                         1   2   3   4   5 || 6  
Array(after deleted)   | 5 | 3 | 6 | 1 | 2 || 7(max) |
Now we get the biggest node in the tail of the array.
continue sort the rest.

Code of Heap Sort

1
2
3
4
5

void heapSort(int[] A) {
    for(int i = n; i >= 1; i--) {
        deleteHeap(A, 1, i);
    }
}

makeHeap()

Solution 1 insert n times O(nlogn)

Solution 2

1
2
3
4
5
6
7
8

           6(1)
         /      \
      3(2)      7(3)
     /   \       / 
   1(4)  2(5)  5(6)  

n = 3 is the last non-trivil node
we heapify the 7, 3, 6 nodes, where we ensure that all children are valid heap.

Code of makeHeap()

1
2
3
4
5

// On time 
// n/2 means the last non-trivil node in the heap
for (int i = n/2; i >=1; i--) {
    heapify(A, i);
}

Example of heap sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

First, make this into a heap.

           9(1)
         /      \
      2(2)      6(3)
     /   \       / 
   1(4)  4(5)  3(6)  

          1   2   3   4   5   6  
Array   | 9 | 2 | 6 | 1 | 4 | 3 |    

call makeHeap() on 6

call makeHeap() on 2

           9(1)
         /      \
      4(2)      6(3)
     /   \       / 
   1(4)  2(5)  3(6)  

          1   2   3   4   5   6  
Array   | 9 | 4 | 6 | 1 | 2 | 3 |  

call deleteHeap() on 9

           3(1)
         /      \
      4(2)      6(3)
     /   \       
   1(4)  2(5)  

          1   2   3   4   5    6  
Array   | 3 | 4 | 6 | 1 | 2 || 9 |

call heapify() on 3

           6(1)
         /      \
      4(2)      3(3)
     /   \       
   1(4)  2(5)  

          1   2   3   4   5    6  
Array   | 6 | 4 | 3 | 1 | 2 || 9 |

call deleteHeap() on 6

           2(1)
         /      \
      4(2)      3(3)
     /       
   1(4)  

          1   2   3   4    5   6  
Array   | 2 | 4 | 3 | 1 || 6 | 9 |

call heapify() on 2

           4(1)
         /      \
      2(2)      3(3)
     /         
   1(4)   

          1   2   3   4    5   6  
Array   | 4 | 2 | 3 | 1 || 6 | 9 |

call deleteHeap() on 4

           1(1)
         /      \
      2(2)      3(3)
     /          
   4(4)   

          1   2   3    4   5   6  
Array   | 1 | 2 | 3 || 4 | 6 | 9 |
...
The array is sorted.

Sorting Algorithms

Types of sorting algorithms

Theorem of comparison based sorting algorithm

Comparison based sorting algorithm always run in $Ω(nlogn)$.

Counting Sort

1
2
3
4
5
6
7
8
9
10
11
12

Assume we have array A
The input nums should satisfy 0 <= A[i] <= k

input   A    | 2 | 1 | 3 | 5 | 4 | 2 | 1 | 0 | 3 |

               0   1   2   3   4   5
bucket  B    | 1 | 2 | 2 | 2 | 1 | 1 |

               0   1   2   3   4   5
bucket  B'   | 1 | 3 | 5 | 7 | 8 | 9 |

output  C    | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 5 |

Code of Counting Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

//Step of counting sort
// fill the num in the buckets
for (int i = 0; i < n; i++) {
    B[A[i]] += 1
}

// indicates where the curr digit ends in the ouput array
for (int i = 1; i <= k; i++) {
    B[i] += B[i-1];
}

// fill the digit into the array
for (int i = n-1; i >= 0; i--) {
    C[B[A[i]]] = A[i];
    B[A[i]] -= 1;
}

return C;

problems of Counting Sort

Q: Why 0-based?
A: To represent the case where the input has 0.

Q: what happened if we have negative input?
A: Map the input to the form we want. e.g. [-10, 10] -> [0, 20]

Q: Is this algorithm stable?
A: In this case, yes.

Analysis of Counting Sort

Run time: $O(n+k)$
Space: $O(k)$

Radix Sort

Introduction

Also known as digit sort.

Only for positive base 10 integers.

Example

1
2
3
4
5
6
7
8
9
10

Use the counting sort to sort the colomn

100      100     100       4
 23       41       4      13
123      512     512      23  
512       23     013      41
  4  =>  123 =>   23  => 100
 13       13     123     123
 41        4      41     512
999      999     999     999

Analysis

d is the number of digits, k is the range of the inputs(e.g. 32 bit integer)
Run time: $O((n+k)d)$
Space:

e.g.

1
2
3
4

32-bit int
| 8-bit | 8-bit | 8-bit | 8-bit |  
d = 4 times of counting sort
k = 2^8 = 256

Class 3 05/20/2019

Questions about Order Statistics

Given a collection of integers, get the min/max value, median, 25% element, rth smallest element, etc.

Question: How do we find the rth smallest element?

Solution1 Sort the array

1. sort array
2. return A[k]

The run time should be O(nlgn)

Solution2 Based Partition

Idea

1
2
3
4
5
6
7
8
9
10
11
12

Definition 2

| 1 | ... | start | ... | end | ... | 10 |

A   | 1 | 2 | 3 | 6 | 7 | 5 | 4 |

pos = partition(A, 1, 7, 5)
pos = 3

if we get the 3 as the pivot position, which means we still have to find 2 more elements

we continue searching on kth(A, 4, 7, 2)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// definition 1
int findKth(int[] A, int k) {
    int pos = partition(A, 1, n);
    if (pos == k) return A[k];
    if (pos > k) return findKth(A, 1, pos);
    if (pos < k) return findKth(A, pos+1, n);
}

// definition 2
// global index
// rank of number with A[begin...end]
int findKth(int[]A, int begin, int end, int k) {
    
}

Analysis

$ T(n) = T(n/2) + n = O(n)$

1
2
3
4

Example 
T(n) = T(2n/3) + n = O(n)
T(n) = T(99n/100) + n = O(n)
T(n) = T(n-1) + n = O(n^2)

Find Top K

Solution 1 Sort the array

1. Sort the array
2. return A[1:k]

Time: $ O(nlogn) $

Solution 2 findKth algorithm

1. partition
2. return A[1:k]

Time: $ O(n) $

Solution 3 Min Heap

1. make a min heap
2. delete k times

Time: $O(n + klogn)$ (depends on which one’s bigger)

Solution 4 Max Heap

1. m make a max heap A[1:k]

1
2
3
4
5

for (i = k+1, ... , n)
    if(A[i] < getMax()) {
        deleteMax();
        insert(A[i]);
    }

Time: $ O(k + (n-k)*logk)$
When n is large, $ O(nlogk) $
When k is large, $ O(k) $

Big Integer Multiplication

for integers of 32-bit(unsigned), we have a range of $ (0, 2^{32}-1) $, which are 10 digits

for integers of 64-bit(unsigned), we have a range of $ (0, 2^{64}-1) $, which are 10 digits

RSA

An encryption algorithm using large integer multiplication.

Idea

Input: 2 integers of n-bits
Example:

1
2
3

    1110 = 14
*   0101 =  5
 1000110 = 70

Time : $ O(n^2) $

Divide and Conquer

a can be split to a1 | a2

for example,
a = 1110 = $ 11 * 2^2 + 10 $ (Shift left by 2 bit)

Therefore,
$ a = a_12^{n/2} + a_2 $
$ b = b_12^{n/2} + b_2 $
$ a b = a_1b_12^{n} + (a_1b_2+a_2b_1)2^{n/2} + a_2b_2 $

We divide the 1 problem to 4 child problem.

T(n) = 4T(n/2) + n(sum 2 n-bit integers) = O(n^2)

Improve the running time

$ p_1 = a_1b_1$
$ p_2 = a_2b_2$
$ p_3 = (a_1+a_2)(b_1+b_2)$
$ a b = p_12^{n} + (p_3-p_1-p_2)2^{n/2} + p_2 $

We can save the Time to

T(n) = 3T(n/2) + n
$ T(n) = O(n^{log_2{3}}) $

Extra cases

What if 2 integers are not with the same digits?
Pad the 0’s to the nearest exponential of 2.

1
2
3

For example
110 -> 0110
10010 -> 00010010

Square Matrix Multiplication

Idea

input: 2 n*n matrices

$
X = \left[
\begin{matrix}
A & B \
C & D
\end{matrix}
\right]_{n*n}
$

$Y = \left[
\begin{matrix}
E & F \
G & H
\end{matrix}
\right]_{n*n}
$

$ X*Y = O(n^3) $

Here we use the block of matrix to Divide & Conquer

$
X = \left[
\begin{matrix}
1 & 1 \
1 & 0
\end{matrix}
\right]_{n*n} = \left[
\begin{matrix}
A & B \
C & D
\end{matrix}
\right]
$

$Y = \left[
\begin{matrix}
1 & 1 \
1 & 0
\end{matrix}
\right]_{n*n} = \left[
\begin{matrix}
E & F \
G & H
\end{matrix}
\right]
$

$ XY = \left[
\begin{matrix}
{AE+BG} & {AF+BH} \
{CE+DG} & {CF+DH}
\end{matrix}
\right]_{nn}
$

Therefore, $ T(n) = 8T(\frac{n}{2}) + n^2 = O(n^3)$

Optimization

$ XY = \left[
\begin{matrix}
{AE+BG} & {AF+BH} \
{CE+DG} & {CF+DH}
\end{matrix}
\right]_{nn} = \left[
\begin{matrix}
{Q} & {R} \
{S} & {T}
\end{matrix}
\right]
$

$Assume:$
$P_1 = A(F-H)$
$P_2 = H(A+B)$
$P_3 = E(C+D)$
$P_4 = D(G-E)$
$P_5 = (A+D)(E+H)$
$P_6 = (B-D)(G+H)$
$P_7 = (A-C)(E+F)$
$Q = P_4 + P_5 - P_2 + P_6$
$R = P_1 + P_2$
$S = P_3 + P_4$
$T = P_1 + P_5 - P_3 - P_7$

$ X*Y = \left[
\begin{matrix}
{AE+BG} & {AF+BH} \
{CE+DG} & {CF+DH}
\end{matrix}
\right] = \left[
\begin{matrix}
{P_4 + P_5 - P_2 + P_6} & {P_1 + P_2} \
{P_3 + P_4} & {P_1 + P_5 - P_3 - P_7}
\end{matrix}
\right]
$

Therefore, $ T(n) = 7T(\frac{n}{2}) + n^2 = O(n^3)$, Successfully optimized.

Counting Inversions

Idea

1
2
3
4
5
6

Inversion: if i < j && A[i] > A[j], then (i, j) is an inversion.

If my favorite list is [1, 2, 3], num of inversion is 0
If list is [2, 1, 3], num of inversion is 1
If list is [2, 3, 1], num of inversion is 2
If list is [3, 2, 1], num of inversion is 3, we have a completely different taste

Max num of inversions of a n list is $ C^{2}_{n} = O(n^2) $

Code

1
2
3
4
5
6
7
8
9

// Brute force
int count = 0;
for (int i = 0; i <=n; i++) {
    for(int j = i+1; j <=n; j++) {
        if (A[i] > A[j]) {
            count++;
        }
    }
}

Better Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

        1         n/2 n/2+1       n
A       |      x     |       y    |

num of cross inversions + x + y


        begin        mid mid+1      end
A       |     1  3  5   |  0  2  6   |
              p            q

given A[p] = 1, A[q] = 0, A[p] > A[q], we have inv += 3, q++
A[p] < A[q], p++
A[q] < A[p], inv += 2, q++
A[p] < A[q], p++
A[p] < A[q], p++, end

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int CountInv(int[] A, int begin, int end) {
    if (begin >= end) return 0;
    int mid = (mid + end) / 2;
    int x = CountInv(A, begin, mid);
    int y = CountInv(A, mid+1, end);
    int z = CrossInv(A, begin, mid, end);
    return x + y + z;
}

// o nlogn time
int CrossInv(int[] A, int begin, int mid, int end) {
    sort(A, begin, mid);
    sort(A, mid+1, end);
    int p = begin, q = mid + 1, count = 0;
    while (p <= mid && q <= end) {
        if (A[p] < A[q]) p++;
        else {
          count += mid - p+1;
          q++;
        }
    }
    return count;
}

Analysis

$ T(n) = 2T(\frac{n}{2}) + nlogn = O(nlognlogn)$

Optimization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int CountInv(int[] A, int begin, int end) {
    if (begin >= end) return 0;
    int mid = (mid + end) / 2;
    int x = CountInv(A, begin, mid); // sort the left
    int y = CountInv(A, mid+1, end); // sort the right
    int z = CrossInv(A, begin, mid, end); // count the cross
    //merge left and right 
    merge(A, begin, mid, end);
    return x + y + z;
}

// on time
int CrossInv(int[] A, int begin, int mid, int end) {
    int p = begin, q = mid + 1, count = 0;
    while (p <= mid && q <= end) {
        if (A[p] < A[q]) p++;
        else {
          count += mid - p+1;
          q++;
        }
    }
    return count;
}

$ T(n) = 2T(\frac{n}{2}) + n = O(nlogn)$

Example

1
2
3
4
5
6
7
8
9

        | 7 | 2 | 3 | 4 | 1 | 6 | 5 | 8 |
        | 2 | 3 | 4 | 7 | 1 | 6 | 5 | 8 |
                    /    \ 
           3                    
  | 2 | 7 | 3 | 4 |         | 1 | 6 | 5 | 8 |

    /       \                   /       \
   1         0                 
| 7 | 2 |  | 3 | 4 |        | 1 | 6 |   | 5 | 8 |

Class 4 06/03/2019

Binary Search Tree and Hashtable

Difference between two data structures

Binary Search Tree

Definition

1
2
3
4
5

class Node {
    int key;
    Node left;
    Node right;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

     5
   /   \
  3     8
   \
    4
This is a BST

     5
   /   \
  3     8
   \
    6
This is not a BST

1. Left subtree is BST
2. Right subtree is BST
3. root.key > all keys in left subtree
   and root.key < all keys in right subtree

Tree Traversals

1. Level-order
2. Pre-order
3. Post-order
4. In-order

Level-order Traversal

1
2
3
4
5
6
7
8
9
10

void LevelOrder(Node root) {
    Queue<Node> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        Node cur = q.poll();
        // processing on cur; print cur.key;
        if (cur.left != null) q.offer(cur.left);
        if (cur.right != null) q.offer(cur.right);
    }
}

Right Side View Question

1
2
3
4
5
6

     5
   /   \
  3     8
   \
    4
we get the right side view as [5, 8, 4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// we can just modify the original code by
cur, curLevel = q.dequeue();
res[cur_level] = cur.key


class Solution {
    // level order traversal 
    // on time on space
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if (root == null) return res;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offerLast(root);
        int size = 1;
        while (!queue.isEmpty()) {
            int temp=0;
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.pollFirst();
                if (cur.left != null) queue.offerLast(cur.left);
                if (cur.right != null) queue.offerLast(cur.right);
                temp = cur.val;
            }
            res.add(temp);
            size = queue.size();
        }
        return res;
    }
}

Pre-order Traversal

1
2
3
4
5
6

void PreOrder(Node cur) {
    if (cur == null) return;
    Process(cur);
    PreOrder(cur.left);
    PreOrder(cur.right);
}

In-order Traversal

1
2
3
4
5
6

     5
   /   \
  3     8
   \
    4
we get the inorder node list as [3, 4, 5, 8], which is  sorted.

Represent duplicate keys in BST

Requirement

Has to support root >= all left and root < all right.

1. MultiSet
2. MultiMap

1
2
3
4
5
6
7

     5
   /   \
  5     8
/
3     
 \
  4

Implementation

Lookup

1
2
3
4
5
6

boolean Lookup(Node cur, int key) {
    if (cur == null) return false;
    if (cur.key == key) return true;
    if (cur.key < key) return Lookup(cur.right, key);
    return Lookup(cur.left, key);
}

Insert

1
2
3
4
5
6
7
8
9
10

Node insert(Node cur, int key, String val) {
    if (cur == null) return new Node(key, val);
    if (key == cur.key) cur.val = val;
    else if (key < cur.key) {
        cur.left = insert(cur.left, key, val);
    } else {
        cur.right = insert(cur.right, key, val);
    }
    return cur;
}

Delete

1
2
3
4
5
6
7
8
9
10
11
12
13

          5
        /   \
       3     6
     /  \
    2    4

Delete 5(2 children)

          4
        /   \
       3     6
     /  
    2

Case 1: No children
update parent’s reference

Case 2: Single child
Parent pointing to child

Case 2: two children

1. find predecessor p
2. swap
3. delete recursively

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # O logn time O logn space
    # Recursion
    # recursively find the root to delete
    # 3 edge cases
    # if no children, then simply return None
    # if 1 left child, then find the predecessor, swap, and delete the predecessor
    # if 1 right child, then find the successor, swap, and delete the successor
    # in common case, a node has both children, in this case we can find the predecessor as newNode or successor as new Node
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root:
            return None
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
        else:
            if not root.left and not root.right:
                root = None
            elif root.left:
                root.val = self.getPrev(root)
                root.left = self.deleteNode(root.left, root.val)
            else:
                root.val = self.getNext(root)
                root.right = self.deleteNode(root.right, root.val)
        return root
    def getPrev(self, root):
        temp = root.left
        while temp.right:
            temp = temp.right
        return temp.val
    def getNext(self, root):
        temp = root.right
        while temp.left:
            temp = temp.left
        return temp.val

Class 5 06/10/2019

Recap of BST

Predecessor and Successor

Logical view

1
2
3
4
5
6
7
8
9

          5
        /   \
       3     8
     /  \   /  \ 
    2    4 6    10
   /        \
  1          7
pre(8) = 7
pre(6) = 5

Predecessor

1. case1: rightmost node of the left subtree
2. case2: find smaller node on the ancestor path

Re-Definition of node

1
2
3
4
5
6

class Node {
    int key;
    Node left;
    Node right;
    Node parent;
}

Find Kth key in BST

Idea of In-order traversal

We can find the kth key by stopping at kth step during in-order traversal.

Our goal is to control the time in O(h).

Re-definition of Node

1
2
3
4
5
6

class Node {
    int key;
    Node left;
    Node right;
    Node parent;
}

Logical View

1
2
3
4
5

      5(5)
    /      \
   3(3)     10(1)
 /    \   
2(1)   4(1)

Code

1
2
3
4
5
6

int kth(Node root, int k) {
    rank = root.left.size + 1;
    if (rank == k) return root;
    if (rank < k) return kth(root.right, k - rank);
    return kth(root.left, k);
}

Example

1
2
3
4
5
6
7
8
9

          5(5)
        /      \
       3(3)     10(1)
     /    \   
    2(1)   4(1)

to find kth(4), rank = 4 = k, we just return 5

to find kth(3), rank = 2 < k, we call the func on 4(1), rank = 1 = k, return 4

Hashing/ HashTable

Pre-hash and Hash

Difference

Example

HashTable<String , T> means we have String as key, T as value.

1
2
3
4

class Pair {
    int x;
    int y;
}

HashTable<Pair, T> means we represent a coordinate as key.

In java, we overwrite the HashCode() as the pre-hash function.

For a String , a practical pre-hash function would be calculating the ascii code.

ASCII is a 8 bit representation of a char data type.

e.g.

For “hello” and “hell”, we have

1
2

Hashcode("hello") = 'h' * 41^3 + 'e' * 41^2
+ 'l' * 41^1 + 'l'

p.s. the hashcode of single letter depends on the encoding way. If simple english, we just use its ascii. If unicode, we use another way.

e.g. To represent Pair, we can use x^y as its hash function.

SubSet : We can split the string and calculate each part of it, while we have a bigger chance to collision and worse time consumption.
Caching : For extra long String, we can only call the hash function once, and store the pre-hash value in the memory.

HashTable

Idea

key = Integer[in large space]
Suppose key ranges from (0, m-1), then we have to map the integer from 0 to m-1
insert(key)
hash: int -> int [0, m)

How do we choose m?

m changes dynamically

Load Factor $ \alpha = n/m $
n = number of k-v pairs
m = size of current hashtable
Here, we increase m exponentially.
e.g. m = 1024, next m would be 2048

Question: Why don’t we increase m by 100 each time?
Answer: Suppose we have $ \alpha = 1$, then every time we hit the bottle neck, we have to find a continuous memory to store all the stuff, which is a expensive On operation.

Question: what happens if we do insert n times with m increasing by 100?
Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13

C, C, C, ..., C, 100C
C, C, ..., 200C
C, C, ..., 300C
C, C, ..., n/100C

Overall: 100 + 200 + 300 + .. n/100 ~= O(n^2) time, which is super expensive. 

C, C, C, ..., C, n/lognC
C, C, ..., n/8C
C, C, ..., n/4C
C, C, ..., n/2C

Overall: n/logn + n/8 + n/4 + .. n/2 ~= O(n) time, which is much better.

Question: what happens if we have to adjust the size?
Answer: Suppose $ \alpha < 0.2$, we would like to shrink the size by half. If $ \alpha > 0.8$, we would like to double the size. The threshold shold be decided wisely.

what should be the hash function?

hash function: (large space)int -> int [0, m)

Division Method

$ H(x) = x \% m $

If m is a power of 2, then this function is bad. e.g. If m = 1024, if pre-hash only consists of even numbers, then half of the space is wasted. We should pick prime number as m. (disadvantage)

Multiplication Method

$ H(x) = a * x \% 2^{32} >> (32 - r) $
$ m = 2^r $
a is constant chosen randomly.

Explanation: Since m = 2^r, we only need r bit to represent the hashcode. Suppose x is 32 bit, and a is 32 bit, then a*x is 64 bit. Then we mod it by 2^32, where we throw away half of the number. Next we right shift till we get only r digits, so that the hashtable con contain the num.

1
2
3

x = | 1 | 1 | 0 | ... | 1 | 0 | 1| (32)
a = | 0 | 0 | 1 | ... | 1 | 0 | 1| (32)
a is random and every 1 means we duplicate a x and left shift by x k digits. In this way the middle part is more random than right part, because e use more information of thee original x in the middle(than the edge).

Collision

Birthday Paradox

Suppose we randomly select x people, what’s the probability that two people have same birthday?

To get a 50% of prob, we should select 23 people.

This example showws the impact of collision.

There are 2 ways to deal with collision, Chaining, Probing.

Chaining

$ h(x_{1}) = k $
$ h(x_{2}) = k $
Then we have key k -> $x_1$ => $x_2$

run time O(1 + $ \alpha $)
$ \alpha $ is load factor n/m
worst case insert: len n/m logn

Probing

Here we are talking about Linear Probing.

$ h(x_{1}) = k $
$ h(x_{2}) = k $
Then we have key k ($x_1$) -> n slots taken -> (k+n) $x_2$

Delete: When wew delete an element, all the following elements have to be re-hashed.

Suppose $ \alpha = n/m = 0.1$
90 % of time is empty
Therefore we need $1 / (1-\alpha)$ space to get a slot.

time complexity: O n

Class 6 06/17/2019

Dynamic Programming

Steps of DP problem

1. Situations of DP

   • Optimization : max/min problem
   • Counting: binomial
   • Feasibility: if the target is possible to get

2. Design recursion

3. Naive recursive implementation yields bad running time(Usually exponential)

   • e.g. Recompute the same thing. Fibonacci.

4. Caching

   • bottom -> up( small -> large)
   • top -> down with memoization

Longest Common Subsequences

Description

1
2
3
4
5
6

input: A[1 ... n]
       B[1 ... n] 
e.g.
A = [1, 5, 2, 3, 4]
sub can be [1]  [1, 3]  [1, 2, 4]
not [3, 2, 4]

Solution

1
2
3
4
5
6
7
8
9
10
11
12

define f(i, j) = length of the LCS given A[1 ... i] & B[1 ... j]

A | 1 | ... | i |
B | 1 | ... | j |

case 1: A[i] = B[j]
f(i, j) = f(i-1, j-1) + 1

case 2: A[i] != B[j]
f(i, j) = max(f(i-1, j), f(i, j-1))

base case: f(0, j) = f(i, 0) = 0

Pseudocode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

// O 2^n time O m+n space
int LCS_slow(int[] A, int[] B, int i, int j) {
    if (i == 0 || j == 0) return 0;
    if (A[i] == B[j]) return 1 + LCS_slow(A, B, i-1, j-1);
    return Math.max(LCS_slow(A, B, i, j-1), LCS_slow(A, B, i-1, j));
}

// 2-d array dp(bottom up)
// O mn time O mn space
int LCS(int[] A, int[] B, int i, int j) {
    for (int i = 0 ... n) dp[i, 0] = 0;
    for (int j = 0 ... m) dp[0, j] = 0;
    for (int i = 1 ... n) {
        for (int j = 1 ... m) {
            if (A[i] == B[j]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = max(dp[i-1, j], dp[i, j-1]);
        }
    }
    return dp[n, m]
}

// optimized recursive solution (top down)
int LCS(int[] A, int[] B, int i, int j, int[][] dp) {
    if (i == 0 || j == 0) return 0;
    if (dp[i][j] != -1) return dp[i][j];
    if (A[i] == B[j]) {
        dp[i][j] = LCS(A, B, i-1, j-1, dp) + 1;
    } else {
        dp[i][j] = Math.max(LCS(A, B, i-1, j, dp), LCS(A, B, i, j-1, dp));    }

    return dp[i][j];
}

// get the result set out of 2-d ap array
// O m+n time
int constructSolution(int[] A, int[] B, int[][] dp) {
    List<Integer> l = new ArrayList<>();
    int i = A.length;
    int j = B.length;
    while (i > 0 && j > 0) {
        if (A[i] == B[j]) {
            l.add(A[i]);
            i--;
            j--;
        } else if (dp[i-1][j] < dp[i][j-1]) {
            j--;
        } else i--;
    }
    return l.reverse();
}

// optimized space solution
// O min(m, n) space O mn time
// dp row = 2, col = n
int LCS(int[] A, int[] B, int i, int j) {
    for (int i = 1 ... n) {
        for (int j = 1 ... m) {
            if (A[i] == B[j]) dp[i%2][j] = dp[(i-1)%2][j-1] + 1;
            else dp[i%2][j] = max(dp[(i-1)%2, j], dp[i%2, j-1]);
        }
    }
    return dp[n, m]
}