Assignment 2

Deadline: Nov, 18 2022 14:00 CET

Exercises

2.1 Implement a palindrome matrix

Return an n x n matrix (2-dimensional numpy array) where n is the length of the input string. palindrome_matrix[i][j] is True iff the substring between indices i and j (both inclusive) is a palindrome, otherwise it is False. All cells below the diagonal should be False. The diagonal is trivially always True.

For example, given the string 'aba', the function should return the following matrix:

[[ True, False, True  ]
 [ False, True, False ]
 [ False, False, True ]]

An implementation has been started for you.

2.2 Find the minumum numbers of palindromic segmentations of a string

Given a string, return the minimum number of segmentations such that all resulting substrings are palindromes.

For example, for the string "aab", the function should return 1 (consider the segmentation aa - b), whereas "abc" should return 2 (the best segmentation would be a - b - c).

Use a dynamic programming approach.

An implementation has been started for you.

Wrapping up

Do not forget to

• indicate your name(s) in the file header
• add the honor code (I/We pledge that this code represents my/our own work)
• commit all your changes
• push it to your GitHub repository