July 01, 2022
I attended top conference session at Korea Computer Congress.
Researchers from POSTECH presented Farthest-point Voronoi diagrams in the presence of rectangular obstacles which was published in SoCG 2022. Despite my relatively poor background knowledge on computational geometry, underlying ideas using monotone-path observations and plane-sweeping algorithm was indeed interesting.
July 02, 2022
I participated in UCPC 2022 online preliminary, competitive programming contest in Korea. Problems (in Korean)
Problem H was the most interesting, basically an advanced version of the well known “balanced parenthesis problem”. Algorithmic arguments using stack and clever combinatorial arguments about Catalan numbers was crucial.
July 04, 2022
In preparation for UCPC 2022 final round, I participated in Codeforces Round 804 (Div 2).
July 06-08, 2022
I spent some time cleaning up my old codes and implementations of several algorithms.
July 09, 2022
In preparation for UCPC 2022 final round, our team solved ACM-ICPC Seoul Regional 2021. Our performance was not the best, and I suffered from implementing weird inclusion-exclusion stuff. Maybe I will write about this team practice session on my blog?
July 11, 2022
I wrote the post-content writeup for UCPC 2022 Online preliminary round on my blog (in Korean)
July 12, 2022
Combinatorial optimization with famous book by Prof. Jon Lee. Reviewed some basic terminology about linear programming.
July 14, 2022
As preparation for my upcoming graduate studies at computer theory lab, I reviewed string matching algorithms (Chap.32 of CLRS)
July 15, 2022
I participated in SCPC (Samsung Collegiate Programing Cup) 2022 First round.
July 16, 2022
I studied van Emde Boas trees by listening to MIT 6.046 lecture from OCW.
July 17, 2022
In preparation for UCPC 2022 final round, our team solved ACM-ICPC Jakarta Regional 2019. Problems were interesting, and we checked our strategy on team competitions (mainly how to distribute computer-time)
July 18, 2022
I studied suffix arrays, LCP arrays and Manber-Myers algorithm, by MIT 6.851 lecture and other sources.
Suffix arrays are much simpler than suffix trees, both conceptually and in implementation. However it retains considerable functionalities, solving otherwise difficult problems on strings in a quite elegant manner.
July 19, 2022
I read Order Preserving Matching (Kim et al, Theoretical Computer Science 2014). While the problem has variety of natural applications, yet the algorithm itself is quite elegant and simple extension of well-known KMP algorithm. Considering that in most usecases $n$ (data size) is much larger than $m$ (pattern size), the performance in the realm of $O(n)$ is exceptionally good.
July 20, 2022
I implemented $O(n + m \log m)$ algorithm for order preserving pattern matching problem myself.
This algorithm have been showcased in competitive programming contests, even multiple times. Most recent one is the ICPC Korea regional 2021, which my implementation solves. This problem allows duplicates in the pattern and data, but treatment of duplicates isn’t much of a hassle.
July 21, 2022
Combinatorial optimization, section 0.3-0.4. I learned simplex algorithm for solving linear programs.
July 23, 2022
UCPC 2022 (competitive programming contest). We (team SGD) achieved 26th place, which is slightly below what we had expected - we struggled on implementing some problems :(
Writeup (more like post-mortem) will appear in my blog.
July 24, 2022
Combinatorial optimization, section 0.6-0.8. Lagrangian relaxation, subgradient method and totally unimodular matrices.
Most of the material until now is a slightly more computation-oriented treatment of what I learned in optimization course. Still, several concepts tied to combinatorial optimization such as totally unimodular is new to me….
July 25, 2022 - Aug 04, 2022
Wasn’t able to do anything due to paper revision period :(