Skip to content

Instantly share code, notes, and snippets.

View chaoxu's full-sized avatar
😀

Chao Xu chaoxu

😀
382 followers · 17 following
  • University of Electronic Science and Technology of China
  • Chengdu, Sichuan, China
View GitHub Profile
@chaoxu
chaoxu / piecewise linear infimal convolution
Created March 30, 2016 07:23
data = {0, 10, 0, 20, 10, 30, 0};
breaks = MapIndexed[
With[{pos = First[#2], y1 = First[#],
y2 = Last[#]}, {y1 (1 + pos - x) + y2 (x - pos),
pos <= x < pos + 1}] &, Partition[data, 2, 1]];
f[x_] := Piecewise[breaks];
Plot[f[x], {x, 1, Length[data]}]
h[lambda_] :=
lambda + Max[
Table[MaxValue[{breaks[[i]][[1]] - x,
@chaoxu
chaoxu / testgust
Created January 26, 2015 04:32
min-cost flow bounded treewidth
<p>We have a graph <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-1-Frame" role="textbox" aria-readonly="true"><nobr><span class="math" id="MathJax-Span-1" style="width: 5.123em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.447em; height: 0px; font-size: 115%;"><span style="position: absolute; clip: rect(1.693em 1000.002em 2.853em -0.384em); top: -2.51em; left: 0.002em;"><span class="mrow" id="MathJax-Span-2"><span class="mi" id="MathJax-Span-3" style="font-family: STIXGeneral-Italic;">G</span><span class="mo" id="MathJax-Span-4" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">=</span><span class="mo" id="MathJax-Span-5" style="font-family: STIXGeneral-Regular; padding-left: 0.292em;">(</span><span class="mi" id="MathJax-Span-6" style="font-family: STIXGeneral-Italic;">V<span style="display: inline-block; overflow: hidden; height: 1px; width: 0.099em;"></span></span><span class="mo" id="MathJax-Span-7" style="font-fam
@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 / freediagram.nb
Created December 15, 2014 03:19
buildSegment[a_, xs_, x_] :=
If[Length[xs] == 1, {},
Join[{ { xs[[1]] + (x - a)*Sign[xs[[2]] - xs[[1]]],
a <= x <= a + Abs[xs[[1]] - xs[[2]]]} },
buildSegment[ a + Abs[xs[[1]] - xs[[2]]], Rest[xs], x]] ]
Curve[xs_, x_] := Piecewise[buildSegment[0, xs, x]]
MaxLength[xs_] :=
Sum[ Abs[xs[[i]] - xs[[i + 1]]], {i, 1, Length[xs] - 1}]
FreeDiagram[xs_, ys_, epsilon_] :=
RegionPlot[
@chaoxu
chaoxu / DecomposableDequeue.hs
Last active August 29, 2015 14:09
Decomposable Dequeue
module DecomposableDequeue (DecomposableDequeue, emptyDecomposableDequeue, pushFront, pushBack, popFront, popBack, measure) where
import qualified Data.Dequeue as D
emptyDecomposableDequeue :: (x->f->f)->f->(b->x->b)->b->(f->b->y)->DecomposableDequeue x f b y
emptyDecomposableDequeue fpush fid bpush bid comb = DecomposableDequeue comb (flip fpush) bpush fid bid D.empty [] []
measure :: DecomposableDequeue x f b y -> y
measure deq = combine deq (peek (idf deq) (frontStack deq)) (peek (idb deq) (backStack deq))
where peek a b
| null b = a
@chaoxu
chaoxu / Markdown.tmLanguage
Last active August 29, 2015 14:05
For sublime text 3, make Markdown also highlight latex codes in between $, $$, \[
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
<dict>
<key>fileTypes</key>
<array>
<string>mdown</string>
<string>markdown</string>
<string>markdn</string>
<string>md</string>
@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
@chaoxu
chaoxu / dyalog2014.apl
Last active August 29, 2015 14:02
3rd place entry for Dyalog APL problem solving competition 2014. The problems are here: https://studentcompetitions-general.s3.amazonaws.com/testing-challenge/dyalog/2014%20APL%20Problem%20Solving%20Competition%20Phase%20II%20Problems.pdf
U←⎕A
L←⎕UCS 32+⎕UCS U
Count←{+/⍵⍷⍺}
MostFrequent←{
kmers←∪⍵,/⍺
counts←(⊂⍺)Count¨kmers
(counts=⌈/counts)/kmers
}
@chaoxu
chaoxu / Polyominoes.apl
Last active December 22, 2015 13:19
This is the solution to the first problem in http://studentcompetitions-general.s3.amazonaws.com/dyalog-apl/phase_2/2013%20APL%20Problem%20Solving%20Competition%20Phase%20II%20Problems.pdf
⍝ The canonical representation.
⍝ The matrix with width <= height and has
⍝ the smalelst value if expressed as a binary number.
CanonPoly←{
⍝ Remove zero rows
rm←{(⍵∨.≠0)⌿⍵}
allMatrix←{
⍝ Every mutation of the matrix(reflection and rotation)
allHorMat←{(⍵)(⍉⊖⍉⊖⍵)(⊖⍵)(⍉⊖⍉⍵)}
allVerMat←{(⍉⊖⍵)(⊖⍉⍵)(⍉⍵)(⊖⍉⊖⍵)}
@chaoxu
chaoxu / cs573template.tex
Last active December 21, 2015 20:28
% I copy pasted some codes from here: http://www.latextemplates.com/template/structured-general-purpose-assignment
\documentclass{article}
\usepackage{fancyhdr} % Required for custom headers
\usepackage{lastpage} % Required to determine the last page for the footer
\usepackage{extramarks} % Required for headers and footers
% Margins
\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in