Skip to content

Instantly share code, notes, and snippets.

View chaoxu's full-sized avatar
😀

Chao Xu chaoxu

😀
  • University of Electronic Science and Technology of China
  • Chengdu, Sichuan, China
View GitHub Profile
import networkx as nx
import random
# Note NetworkX, flow must have positive capacity
# Hence we must build edges in both directions
# This is undesirable but we can't do much about it
# We assume in the graph, if (a,b) is an edge, then (b,a) is also an edge
# We also assume the default orientation is (a,b) where a<b
@chaoxu
chaoxu / RegIntIntval.hs
Last active March 5, 2024 09:01
Build a regular expression to match all non-negative integers between a and b.
module RegIntIntval (RegEx, matchIntRange, matchLessThan, matchGreaterThan) where
import Data.Digits
import Text.Regex.PCRE.Light
import Data.ByteString (pack)
import Data.ByteString.Internal (c2w)
import Data.Maybe
import Data.List
import FreeMonoidCompress
@chaoxu
chaoxu / leetcode.md
Last active November 27, 2023 01:42
Interesting leetcode problems

This is an index of leetcode problems that I find interesting.

You can see many theoretical solutions by hqztrue here.

TCS Problems

Likely only people who work in the area knows the current best solution. The best solution is either in some paper, or requires advanced tricks.

  • 001 2SUM
  • 004 Median of Two Sorted Arrays
@chaoxu
chaoxu / chao.sty
Last active January 20, 2023 15:00
chao.sty
% ========================-*- LaTeX -*-=========================
%
% chao.sty -- modified from jeffe.sty
% jeffe.sty can be found at http://web.engr.illinois.edu/~jeffe/pubs/latex.html
%
% ==========================================================
\ProvidesPackage{chao}
% remarkable size
---
title: "Dial-a-Ride in Small Graphs"
author: "Yike Chen, **Chao Xu**, Jianbo Wang"
format:
revealjs:
incremental: false
css: custom.css
callout-icon: false
---
@chaoxu
chaoxu / README.MD
Last active February 3, 2022 17:28

This is a python implementation of a subset sum algorithm by Konstantinos Koiliaris and me.

Given a set of n positive integers, the algorithm finds all the values t<=u such that there exists a subset that sums to t.

The running time is O(sqrt(n)u) with some extra polylog factors.

There is also a C++ implementation of the standard dynamic programming algorithm for subset sum. The DP table gets packed into 64 bit unsigned integers. It's probably the fastest possibe implementation of the O(nu) time algorithm without getting into ASM and parallelism.

from gurobipy import *
from itertools import *
from functools import partial, reduce
import random
import sys
import math
from operator import mul
### Set and partition operations
@chaoxu
chaoxu / lipschitz
Created January 18, 2015 12:45
Lipschitz regression
![stuff](http://i.imgur.com/a9bAYas.png)
We have a sequence $a_1,\ldots,a_n$ and $\epsilon$. We want to output $x_1,\ldots,x_n$ such that $|a_i-x_i|\leq \epsilon$ for all $i$ and $\sum_{i=1}^n |a_i-x_i|$ is minimized.
**Claim:** We can solve the problem in $O(n\log^2 n)$ time.
**Reduction**
We reduce the problem to min-cost circulation in a outerplanar graph.
@chaoxu
chaoxu / mathconf.js
Last active May 2, 2021 06:36
Typora mathjax config. Need to change the file in `/Applications/Typora.app/Contents/Resources/TypeMark/index.html`
MathJax.Hub.Config({
skipStartupTypeset: true,
jax: ["input/TeX", "output/SVG"],
extensions: ["tex2jax.js", "toMathML.js"],
TeX: {
extensions: ["noUndefined.js", "autoload-all.js", "AMSmath.js", "AMSsymbols.js", "mediawiki-texvc.js"],
mhchem: { legacy: false },
Macros: {
R: '{\\mathbb{R}}',
@chaoxu
chaoxu / description.md
Last active March 18, 2021 18:09
Subset sum

This is demo code for the journal version of the faster subset sum paper.

Konstantinos Koiliaris and Chao Xu. 2019. Faster Pseudopolynomial Time Algorithms for Subset Sum. ACM Trans. Algorithms 15, 3, Article 40 (July 2019), 20 pages. DOI:https://doi.org/10.1145/3329863