Vectorized Subset Sum

In this series I am implementing Dynamic Programming Katas with vectorized solutions.

The first post explored the Vectorized Longest Increasing Subsequence problem, and in the second post I dived into the Checkerboard problem.

In this post I will explore a version of the Subset sum problem. I will not focus on the most efficient algorithm or implementation for this problem. Instead, I will present the most common approach to solve the problem using Dynamic Programming and then present a vectorized version of the algorithm.

Introduction

Find out more


Alternate Dictionary Lookup

This blog post is based on .NET 9 Preview 6. Bits and pieces of the underlying runtime will change for the final release.

In .NET9 a new extension method on Dictionary type allows creating an alternate lookup type for the dictionary. This is particularly useful for dictionaries that have a string key, as the alternate lookup allows an alternate type to be used for lookups in the dictionary, for example ReadOnlySpan<char>.

Most sets and dictionaries (immutable, frozen, etc.) support this new API. However, not all dictionaries support the alternate lookup equally. Some only support certain types as alternates. Hence, there is a second extension method TryGetAlternateLookup, which does not throw when the requested alternate type is not supported.

How to lookup an alternate key?

Find out more


Vectorized Checkerboard

In this series I am implementing Dynamic Programming Katas with vectorized implementations.

The first post explored the Vectorized Longest Increasing Subsequence problem, and in this post I will dive into the Checkerboard problem.

Introduction

Consider a checkerboard with n*n squares and a cost function c(i, j) which returns a cost associated with the indexes of (i,j). The checker starts in the first row. We would like to know the shortest path (the sum of the minimum costs at each visited row) to get to the last row. The checker could move only diagonally left forward, diagonally right forward, or straight forward. That is, a checker on (1,3) can move to (2,2), (2,3) or (2,4).

Find out more


Vectorized Longest Increasing Subsequence

In the problem of Longest Increasing Subsequence, the aim is to find an increasing sequence of elements in a given input. This new subsequence does not need to be continuous. The longest such sequence is the solution to the Longest Increasing Subsequence (LIS) problem.

For example, for input sequence of 0,8,4,5,2, the LIS will return 3 as the longest subsequence is 0,4,5.

In this post I will not focus on the most efficient implementation of LIS. Instead, I will present the most common approach to solve the problem using Dynamic Programming and then present a vectorized version of the algorithm.

The Base Solution

Find out more


CHttpExec Extension

I have been recently working on CHttp which is a tool to send HTTP requests and to measure the performance of REST APIs.

The primary goal of the tool is the ability to measure GET HTTP requests using version HTTP/2 and HTTP/3. As the tool is based on .NET (currently version 9), it requires a reasonably up-to-date Windows installation or the libmsquic package in case of Linux.

The tool exists of 3 components

  • CHttp

  • Chttp Visual Studio Code Extension

  • CHttpExec

Find out more