# CS577 Study Group (Thursday 4:00-5:00pm)

## Palindrom Partition
Given a string, find the minimum number of partitions needed to split the string into palindromes.

For example, ```BABABCBADCD```, the min required is

Desing an algorithm that runs in $O(n^3)$ or $O(n^2)$.

[Problem source and Solution](https://www.techiedelight.com/find-minimum-cuts-needed-palindromic-partition-string/)

## Alternating Subsequence
Given an array, find the longest "alternating" subsequence. An "alternating" sequence $a$ is such that if $a_i \geq a_{i+1}$, then $a_{i+1} \leq a_{i+2}$ and vice versa.

[Problem source and Solution](https://www.techiedelight.com/longest-alternating-subsequence/)

## Gerry Mandering (Review Problem)
Gerrymandering is the practice of carving up electoral districts in very careful ways so as to lead to outcomes that favor a particular political party. Recent court challenges to the practice have argued that through this calculated redistricting, large numbers of voters are being effectively (and intentionally) disenfranchised.
Suppose we have a set of n precincts P1 , P2 , · · · , Pn , each containing m registered voters. We’re supposed to divide these precincts into two districts, each consisting of n/2 of the precincts. Now, for each precinct, we have information on how many voters are registered to each of two political parties. (Suppose, for simplicity, that every voter is registered to one of these two.) We’ll say that the set of precincts is susceptible to gerrymandering if it is possible to perform the division into two districts in such a way that the same party holds a majority in both districts.
Give an algorithm to determine whether a given set of precincts is susceptible to gerrymandering; the running time of your algorithm should be polynomial in n and m.

## Independent Set On Tree (Jeff's Note page 24 Dynamic Programming 3.10)
**DEF**: An independent set in a graph is a subset of the vertices with no edges
between them.
[Link](http://jeffe.cs.illinois.edu/teaching/algorithms/book/03-dynprog.pdf)


(More Chalenging Problem)
--- 
## Guardians of the Lunatics (Divide and Conquer + DP)
The cells form a single row and are numbered from  $1$ to $L$. Cell  houses exactly one lunatic whose craziness level is $C_i$.

Each lunatic should have one guard watching over him/her. Ideally, you should have one guard watching over each lunatic. However, due to budget constraints, you only have  $G$ guards to assign. Each guardian would have to watch over a set of lunatics.

Of course, you should assign each guard to a set of **adjacent** cells. The risk level  that the lunatic in cell  can escape is given by the product of his/her craziness level  $C_i$ and the number of lunatics the guard assigned to him/her is watching over.

Given  lunatics and  guards, what is the minimum possible value of the total risk?


Design an algorithm that runs in $O(LG \log G)$.

[Technique Used](https://cp-algorithms.com/dynamic_programming/divide-and-conquer-dp.html)

[Problem Source](https://www.hackerrank.com/contests/ioi-2014-practice-contest-2/challenges/guardians-lunatics-ioi14/problem)