A list of useful snippets (Personal-use only)

The material in this repo are for

• revising basics

• Trying new(mainly C++ 17, 20) features

• some auxiliary prototypes for various work project

Algorithms and Strategies

Path finding

• A* version1
• A* better
• DFS

Dynamic Programming

Dynamic Programming is similar to backtracking except that we stop making redundant computations (i.e. Memoization. Calculate the answer to each subproblem only once)

• climb stairs
• Knapsack
• Fibonacci-DP-vs-iteration

Backtracking

The algorithm begins with anempty solution and extends the solution step by step. The search recursively goes through all different ways how a solution can be constructed. climb-stairs

(https://gcc.godbolt.org/z/aK8jzT)

NQueens

Find a way to place n queens on an nxn chessboard so that no two queens are attacking each other.

NQueens by recursion

Graph algorithms

Dijkstra's SSSP

topological sort using indegrees

Branch and Bound

BB is an optimization algorithm converts a maximization into a minimization problem.

• Travelling Sale Man
• Test of Travelling Sale Man
• TSP via unique ptr

Brute-force branch and bound

• dynamic programming solution with O(n*2^n)

Data structures

• bitmap

• bitset

Finite Difference with functor

• simple
• template
• template (multi)
• template (type_traits)

C++ general

• padding and alignment

• higer order function

• function object

• when do u still need macros?

• Should you use raw or unique ptr?

  • Example1

  • Example2

  • Example3

• non-owning pointer