TDDD95 Algorithmic

Problem Solving
6hp, vt2025
Fredrik Heintz
Dept of Computer and Information Science
Linköping University
Outline 2

 What is algorithmic problem solving?

 Why is algorithmic problem solving important?
 What will be studied in this course?
 A method for algorithmic problem solving
 Common algorithmic problem-solving approaches
 Common data structures and algorithms
 Pragmatic algorithmic problem-solving using Kattis
What is Algorithmic Problem Solving? 3

 Algorithmic problem solving is about developing correct and

working algorithms to solve classes of problems.
 The problems are normally very well defined, and you know
there is a solution, but they can still be very hard.

Algorithms Programming
APS

Problem
Solving
Those that really understand
and take advantage of
software technology owns
the future!
Example: The 3n+1 problem 7
Example: The 3n+1 problem 8
Example: The 3n+1 problem 9

 Follow the instructions in the problem!

 Memoization to speed it up.
 Table lookup to solve it in constant time.
 Gotchas:
▪ j can be smaller than i.
▪ j can equal i.
▪ The order of i and j in output must be the same as the input, even when j
is smaller than i.
Course Goals 10

The goals of the course are you should be able to:

 analyze the efficiency of different approaches to solving a
problem to determine which approaches will be reasonably
efficient in a given situation,
 compare different problems in terms of their difficulty,
 use algorithm design techniques such as greedy algorithms,
dynamic programming, divide and conquer, and combinatorial
search to construct algorithms to solve given problems,
 strategies for testing and debugging algorithms and data
structures, and
 quickly and correctly implement a given specification of an
algorithm or data structure.
Examination 11

 LAB1 4hp
▪ individually solving the 4 lab assignments
▪ optionally participating in problem solving sessions
 UPPG1 2hp,
▪ individually solving the 13 weekly homework exercises, e.g.:
▪ Data structures
▪ Greedy Problems and Dynamic Programming
▪ Graph Algorithms
▪ Search
▪ Math-related Problems
▪ Computational Geometry.
Examination – Labs 12
Examination – Exercises 13
Examination – Course grade 14
The Schedule – VT 1 15

 22/1 How to solve algorithmic problems, intro seminar

 23/1 Practice problem solving session: 13.15-17.00 with discussion
 31/1 Deadline Ex 1 (Greedy and DP 1) – Seminar Ex1 and Data structures
 7/2 Deadline Ex2 (Data structures) – Seminar Ex2 and Arithmetic
 14/2 Deadline Ex3 (Arithmetic) – Seminar Ex3 and Problem solving
approaches
 20/2 Deadline Lab Assignment 1 (Data structures, Greedy/Dynamic,
Arithmetic)
 20/2 Problem solving session (individual based on Lab 1)
 21/2 Deadline Ex4 (Greedy and DP II) – Seminar Ex 4 and Graphs I
 28/2 Deadline Ex5 (Graphs I) – Seminar Ex5 and Graphs II
 7/3 Deadline Ex6 (Graphs II) – Seminar Ex6 and Graphs III
 12/3 Deadline Ex 7 (Graphs III) - Seminar Ex7 and Strings I
The Schedule – VT 2 16

 31/3 Deadline Lab Assignment 2 (Graphs)

 31/3 Problem solving session (individual based on Lab 2)
 4/4 Deadline Ex8 (Strings I) – Seminar Ex8 and Strings II
 11/4 Deadline Ex9 (Strings II) – Seminar Ex9 and Number Theory
 25/4 Deadline Ex10 (Number Theory) – Seminar Ex 11 and Combinatorial
Search
 28/4 Deadline Lab Assignment 3 (Strings, String Matching and Number
Theory)
 28/4 Problem solving session (individual based on Lab 3)
 30/4 Deadline Ex11 (Combinatorial Search) – Seminar Ex12 and
Computational Geometry
 9/5 Deadline Ex12 (Computational Geometry)
 16/5 Deadline Ex13 (Combinatorics and Probability Theory)
 19/5 Deadline Lab Assignment 4 (Computational Geometry)
 19/5 Problem solving session (individual based on Lab 4)
Steps in solving algorithmic problems 17

 Estimate the difficulty

▪ Theory (size of inputs, known algorithms, known theorems, …)
▪ Coding (size of program, many cases, complicated data structures, …)
▪ Have you seen this problem before? Have you solved it before? Do you
have useful code in your code library?
 Understand the problem!
▪ What is being asked for? What is given? How large can instances be?
▪ Can you draw a diagram to help you understand the problem?
▪ Can you explain the problem in your own words?
▪ Can you come up with good examples to test your understanding?
Steps in solving algorithmic problems 18

 Determine the right algorithm or algorithmic approach

▪ Can you solve the problem using brute force?
▪ Can you solve the problem using a greedy approach?
▪ Can you solve the problem using dynamic programming?
▪ Can you solve the problem using search?
▪ Can you solve the problem using a known algorithm in your code library?
▪ Can you modify an existing algorithm? Can you modify the problem to
suite an existing algorithm?
▪ Do you have to come up with your own algorithm?
 Solve the problem! ☺
Time Limits and Computational Complexity 19

 The normal time limit for a program is a few seconds.

 You may assume that your program can do about 100M
operations within this time limit.

n Worst AC Complexity Comments

≤ [10..11] O(n!), O(n6) Enumerating permutations
≤ [15..18] O(2n × n2) DP TSP
≤ [18..22] O(2n × n) DP with bitmask technique
≤ 100 O(n4) DP with 3 dimensions and O(n) loop
≤ 450 O(n3) Floyd Warshall’s (APSP)
≤ 2K O(n2 log2 n) 2-nested loops + tree search
≤ 10K O(n2) Bubble/Selection/Insertion sort
≤ 1M O(n log2 n) Merge Sort, Binary search
≤ 100M O(n), O(log2), O(1) Simulation, find average
Important Problem Solving Approaches 20

 Simulation/Ad hoc
▪ Do what is stated in the problem
▪ Example: Simulate a robot
 Greedy approaches
▪ Find the optimal solution by extending a partial solution by making locally
optimal decisions
▪ Example: Minimal spanning trees, coin change in certain currencies
 Divide and conquer
▪ Take a large problem and split it up in smaller parts that are solved individually
▪ Example: Merge sort and Quick sort
 Dynamic programming
▪ Find a recursive solution and compute it “backwards” or use memoization
▪ Example: Finding the shortest path in a graph and coin change in all currencies
 Search
▪ Create a search space and use a search algorithm to find a solution
▪ Example: Exhaustive search (breadth or depth first search), binary search,
heuristic search (A*, best first, branch and bound)
Complete Search a.k.a. Brute Force 21

 When a problem is small or (almost) all possibilities have to be

tried complete search is a candidate approach.
 To determine the feasibility of complete search estimate the
number of calculations that have to be made in the worst case.
 Iterative complete search uses nested loops to generate every
possible complete solution and filter out the valid ones.
▪ Iterating over all permutations using next_permutation
▪ Iterating over all subsets using bit set technique
 Recursive complete search extends a partial solution with one
element until a complete and valid solution is found.
▪ This approach is often called recursive backtracking.
▪ Pruning is used to significantly improve the efficiency by removing
partial solutions that can not lead to a solution as soon as possible. In the
best case only valid solutions are generated.
Complete Search a.k.a. Brute Force 22
Divide and Conquer 23

 Divide and conquer is very common and powerful technique

which divides a problem into smaller parts, solves each part
recursively and then puts together the answer from the pieces.
 Many well known algorithms are based on divide and conquer
such as quick sort, merge sort and binary search.
 Binary search is a very versatile and useful technique which can
be used to
▪ find a particular value in a sorted range,
▪ find the parameters of a (convex) function that gives a particular value,
▪ find the minimum/maximum value of a function.
 Binary search can be implemented either using built in
functions (lower_bound/upper_bound), iterating until the
difference between the end points is small enough or iterate a
constant but sufficiently large number of times.
Quick-Sort 24

 Quick-sort is a
randomized sorting x
algorithm based on the
divide-and-conquer
paradigm:
▪ Divide: pick a random
element x (called pivot) and x
partition S into
▪ L elements less than x
L E G
▪ E elements equal x
▪ G elements greater than x
▪ Recur: sort L and G
▪ Conquer: join L, E and G x

24
Quick-Sort Example 25

 Pivot selection

7 2 9 43 7 6 1 → 1 2 3 4 6 7 8 9

7 2 9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6

2→2 9 4 → 4 9 7→7 8→8

3→3 4→4
Quick-Sort Example 26

 Partition, recursive call, pivot selection

7 2 9 4 3 7 6 1→ 1 2 3 4 6 7 8 9

2 4 3 1→ 2 4 7 9 3 8 6 1 → 1 3 8 6

2→2 9 4 → 4 9 7→7 8→8

3→3 4→4
Quick-Sort Example 27

 Partition, recursive call, base case

7 2 9 43 7 6 1→→ 1 2 3 4 6 7 8 9

2 4 3 1 →→ 2 4 7 3 8 6 1 → 1 3 8 6

1→1 9 4 → 4 9 7→7 8→8

3→3 4→4
Quick-Sort Example 28

 Recursive call, …, base case, join

7 2 9 43 7 6 1→ 1 2 3 4 6 7 8 9

2 4 3 1 → 1 2 3 4 3 8 6 1 → 1 3 8 6

1→1 4 3 → 3 4 7→7 8→8

3→3 4→4
Quick-Sort Example 29

 Recursive call, pivot selection

7 2 9 43 7 6 1→ 1 2 3 4 6 7 8 9

2 4 3 1 → 1 2 3 4 7 9 7 1 → 1 3 8 6

1→1 4 3 → 3 4 7→7 9→9

3→3 4→4
Quick-Sort Example 30

 Partition, …, recursive call, base case

7 2 9 43 7 6 1→ 1 2 3 4 6 7 8 9

2 4 3 1 → 1 2 3 4 7 9 7 1 → 1 3 8 6

1→1 4 3 → 3 4 7→7 9→9

3→3 4→4
Quick-Sort Example 31

 Join, join

7 2 9 4 3 7 6 1 →1 2 3 4 6 7 7 9

2 4 3 1 → 1 2 3 4 7 9 7 → 17 7 9

1→1 4 3 → 3 4 7→7 9→9

3→3 4→4

31
Greedy 32

 An algorithm is said to be greedy if it makes a locally optimal

choice in each step towards the globally optimal solution.
 For a greedy algorithm to give a globally optimal result a
problem must have two properties:
▪ It has optimal sub-structures, i.e. an optimal solution contains the
optimal solutions to sub problems.
▪ It has the greedy choice property, i.e. if we extend a partial solution by
making a locally optimal choice we will get the optimal complete solution
without reconsidering previous choices.
 Classical examples: Coin change in some currencies, interval
coverage and load balancing.
 Greedy algorithms can be very useful as heuristics for example
in branch-and-bound search algorithms.
 In combinatorics matroids and the generalization greedoids
characterize classes of problems with greedy solutions.
Kruskal’s MST Algorithm 33

Consider an undirected, weight graph

3
10
F C
A 4
4
3
8
6
5
4
B D
4
H 1
2
3
G 3
E
Kruskal’s MST Algorithm 34

Sort the edges by increasing edge weight

3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1 (B,E) 4
8 (B,F) 4
6 (D,G) 2
5
4
B D (E,G) 3 (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3
E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
Kruskal’s MST Algorithm 35

Select first |V|–1 edges which do not

generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4
8 4
6 (D,G) 2 (B,F) 4
5
4
B D (E,G) 3 (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3
E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
Kruskal’s MST Algorithm 36

Select first |V|–1 edges which do not

generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4
8 4
6 (D,G) 2  (B,F) 4
5
4
B D (E,G) 3 (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3
E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
Kruskal’s MST Algorithm 37

Select first |V|–1 edges which do not

generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4
8 4
6 (D,G) 2  (B,F) 4
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3
E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10

Accepting edge (E,G) would create a cycle

Kruskal’s MST Algorithm 38

Select first |V|–1 edges which do not

generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4
8 4
6 (D,G) 2  (B,F) 4
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3
E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
Kruskal’s MST Algorithm 39

Select first |V|–1 edges which do not

generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4
8 4
6 (D,G) 2  (B,F) 4
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
Kruskal’s MST Algorithm 40

Select first |V|–1 edges which do not

generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4
8 4
6 (D,G) 2  (B,F) 4
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3  (A,B) 8
(B,C) 4 (A,F) 10
Kruskal’s MST Algorithm 41

Select first |V|–1 edges which do not

generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4
8 4
6 (D,G) 2  (B,F) 4
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3  (A,B) 8
(B,C) 4  (A,F) 10
Kruskal’s MST Algorithm 42

Select first |V|–1 edges which do not

generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4 
8 4
6 (D,G) 2  (B,F) 4
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3  (A,B) 8
(B,C) 4  (A,F) 10
Kruskal’s MST Algorithm 43

Select first |V|–1 edges which do not

generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4 
4
8
6 (D,G) 2  (B,F) 4 
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3  (A,B) 8
(B,C) 4  (A,F) 10
Kruskal’s MST Algorithm 44

Select first |V|–1 edges which do not

generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4 
4
8
6 (D,G) 2  (B,F) 4 
5
4
B D (E,G) 3  (B,H) 4 
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3  (A,B) 8
(B,C) 4  (A,F) 10
Kruskal’s MST Algorithm 45

Select first |V|–1 edges which do not

generate a cycle
3
10
F C edge dv edge dv

A 4 3 (D,E) 1  (B,E) 4 
4
8
6 (D,G) 2  (B,F) 4 
5
4
B D (E,G) 3  (B,H) 4 
4
H 1
(C,D) 3  (A,H) 5 
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3  (A,B) 8
(B,C) 4  (A,F) 10
Kruskal’s MST Algorithm 46

Select first |V|–1 edges which do not

generate a cycle
3
F C edge dv edge dv

A 3 (D,E) 1  (B,E) 4 
4
(D,G) 2  (B,F) 4 
5
B D (E,G) 3  (B,H) 4 
H 1
(C,D) 3  (A,H) 5 
2
3
G E
(G,H)
(C,F)
(B,C)
3
3
4



(D,F)
(A,B)
(A,F)
6
8
10
}
not
considere
d

Done
Total Cost =  dv = 21
Dynamic Programming 47

 Dynamic Programming is a problem-solving approach which

computes the answer for every possible state exactly once.
 For DP to be suitable a problem must have two properties:
▪ It has optimal sub-structures, i.e., an optimal solution contains the
optimal solutions to sub problems.
▪ Overlapping sub-problems, i.e. the same subproblem occurs many times.
 Top-down (memoization) vs Bottom-up
▪ Top-down: no need to consider the order of computations, only compute
states actually used, natural transition from complete search,
▪ Bottom-up: no recursion, computes every state, table size can be reduced
if only the previous row of states is used then only two rows are required.
 Displaying the optimal solution
▪ Store the previous state for each solution
▪ Use the DP table and the optimal sub-structures property to compute the
path.
Subset Sum 48

Given:
 an integer bound W, and
 a collection of n items, each with a positive, integer weight wi,
find a subset S of items that:

Motivation: You have a CPU with W free cycles and want to choose
the set of jobs (each taking wi time) that minimizes the number of
idle cycles.
Subset Sum 49

Notation:
 Let S* be an optimal choice of items (e.g. a set {1,4,8}).
 Let OPT(n, W) be the value of the optimal solution.
 We design a dynamic programming algorithm to compute
OPT(n, W).
Subproblems:
 To compute OPT(n, W): We need the optimal value for
subproblems consisting of the first j items for every knapsack size
0 <= w <= W.
 Denote the optimal value of these subproblems by OPT(j, w).
Subset Sum 50
Subset Sum 51
Subset Sum 52
Subset Sum 53
Subset Sum 54
Subset Sum 55

SubsetSum(n, W):
Initialize M[0,r] = 0 for each r = 0,...,W
Initialize M[j,0] = 0 for each j = 1,...,n

for j = 1,...,n: for every row

For r = 0,...,W: for every column
If w[j] > r: case where item can't fit
M[j,r] = M[j-1,r]
M[j,r] = max( which is best?
M[j-1,r],
w[j] + M[j-1, W-w[j]]
)
return M[n,W]
Subset Sum 56
Subset Sum 57

8, 5, 4, 2
General DP Principles 58

1. Optimal value of the original problem can be

computed easily from some subproblems.

2. There are only a polynomial # of subproblems.

3. There is a “natural” ordering of the subproblems from

smallest to largest such that you can obtain the
solution for a subproblem by only looking at smaller
subproblems.
General DP Principles 59

1. Optimal value of the original problem can be

computed easily from some subproblems.
OPT(j, w) = max of two subproblems
2. There are only a polynomial # of subproblems.
{(j, w)} for j = 1, …, n and w = 0, …, W
3. There is a “natural” ordering of the subproblems from
smallest to largest such that you can obtain the
solution for a subproblem by only looking at smaller
subproblems.
Considering items {1, 2, 3} is a smaller problem
than considering items {1, 2, 3, 4}
Classical DP Problems 60

 Max 1D sum
 Max 2D sum
 Longest increasing subsequence (LIS)
▪ Longest decreasing subsequence (LDS)
 0-1 Knapsack (subset sum)
 Coin Change (general version)
 Travelling Salesman Problem (TSP)

1D RSQ 2D RSQ LIS Knapsack CoinChange TSP

State (i) (i,j) (i) (id,remW) (v) (pos,mask)
Space O(n) O(n2) O(n) O(nS) O(V) O(n2n)
Transition subarray submatrix all j<i take/ignore all n coins all n cities
Time O(1) O(1) O(n2) O(nS) O(nV) O(2nn2)
Common Data Structures 61
Important Data Structures and Algorithms 62

 Data structures
▪ Standard library data structures
▪ Vector, stack, queue, heap, priority queue, sets, maps
▪ Other data structures
▪ Graph (adjacency list and adjacency matrix), Union/find, Segment tree,
Fenwick tree, Trie
 Sorting
▪ Quick sort, Merge sort, Radix sort, Bucket sort
 Strings
▪ String matching (Knuth Morris Pratt, Aho-Corasick), pattern matching,
trie, suffix trees, suffix arrays, recursive decent parsing
Important Data Structures and Algorithms 63

 Dynamic programming
▪ Longest common subsequence, Longest increasing subsequence, 0/1
Knapsack, Coin Change, Matrix Chain Multiplication, Subset sum,
Partitioning
 Graphs
▪ Traversal (pre-, in- and post-order), finding cycles, finding connected
components, finding articulation points, topological sort, flood fill, Euler
cycle/Euler path, SSSP - Single source shortest path (Dijkstra, Bellman-
Ford), APSP – All pairs shortest path (Floyd Warshall), transitive closure
(Floyd Warshall), MST – Minimum spanning tree (Prim, Kruskal (using
Union/find)), Maximal Bipartite Matching, Maximum flow, Maximum
flow minimal cost, Minimal cut
 Search
▪ Exhaustive search (depth-first, breadth-first search, backtracking),
binary search (divide and conquer), greedy search (hill climbing),
heuristic search (A*, branch and bound), search trees
Important Data Structures and Algorithms 64

 Mathematics
▪ Number theory (prime numbers, greatest common divisor (GCD),
modulus), big integers, combinatorics (count permutations), number
series (Fibonacci numbers, Catalan numbers, binomial coefficients),
probabilities, linear algebra (matrix inversion, linear equations systems),
finding roots to polynomial equations, diofantic equations, optimization
(simplex)
 Computational geometry
▪ Representations of points, lines, line segments, polygons, finding
intersections, point localization, triangulation, Voronoi diagrams, area
and volume calculations, convex hull (Graham scan), sweep line
algorithms
Kattis ([Link] 69
How Kattis checks a program 70

Compilation
Compiles? Error

For each test case

Runtime
Crashes? Error

Too slow? Time Limit

Exceeded

Incorrect Wrong
output? Answer

Accepted
UVA Online Judge 71

[Link]
Programming languages 72

 Allowed languages are C, C++, Java, and Python.

 C++ or Java is strongly recommended, use the language that
you are most familiar with and want to learn more about.
 Get to know their standard libraries.
 Get to know input and output. Remember that I/O in Java is
very slow, use Kattio. Remember that cout/cerr also is relatively
slow, learn how to use scanf/printf if you use C++.
 Learn to use an appropriate IDE such as eclipse, emacs, or vim
 Create a problem template to speed up problem solving and to
create a common format for your problems.
Pragmatic Algorithmic Problem Solving 73
Testing and debugging 74

 Always create an example input (.in) and example output (.out) file with
verbatim copies of the example input and output from the problem
statement!
 For most problems it is enough to diff your output with the example output:
./prog < [Link] | diff - [Link]
 Create additional tests, such as:
▪ Extreme inputs, i.e. smallest and largest values (0, 1, “”, empty line, 2^31-1)
▪ Small inputs that you can compute by hand
▪ Potentially tricky cases such as when all inputs are equal, in the case of floating
points numbers when you have to round both up and down
▪ Very large cases, randomly generated to test that your program computes an
answer fast enough (even though you might not know the correct answer).
 Use a correct but slow algorithm to compute answers.
 Print intermediate information, such as values of relevant variables.
cout << “a=“ << a << “; b=“ << b << endl;
Remember to remove the debug output before submitting! (or use cerr)
Summary 75

 What is algorithmic problem solving?

 Why is algorithmic problem solving important?
 What will be studied in this course?
 A method for algorithmic problem solving
 Common algorithmic problem-solving approaches
 Common data structures and algorithms
 Pragmatic algorithmic problem-solving using Kattis