Suggested problems

solution looking for a problem ?

Sept. 10, 2019, 9:56 p.m. by gwwdiehl

Biological Motivation

The idea is to use different/more complicated functions to score nodes (not just a simple max of previous node + cost of edge) but as in the making change 1+ min of prev nodes. You could also add a second number or even function/information at the prev. nodes and then at each step you create a score (polynomial or max, min etc all combined) and create the data for the current node from info at the chosen prev. node or nodes. The dynamic programming algorithm and code all work as before. This just adds new fields (one or more) for each node and allows the programmer to add more complex functions within the score calc. code.

No specific problem ... just an option for more complex issues.

...

Problem

A string is simply an ordered collection of symbols selected from some alphabet and formed into a word; the length of a string is the number of symbols that it contains.

An example of an DNA string (whose alphabet contains the symbols A, C, G, and T) is ATGCTTCAGAAAGGTCTTACG.

Given: A DNA string $s$ of length at most 1000 nucleotides.

Return: Four integers corresponding to the number of times that the symbols A, C, G, and T occur in $s$.

Sample Dataset

AGCTTTTCATTCTGACTGCAACGGGCAATATGTCTCTGTGTGGATTAAAAAAAGAGTGTCTGATAGCAGC

Sample Output

20 12 17 21