Problem workshop
strings
String problems
Logistics
New pods!
Status flags
Each team has a status flag that you can use to help me focus where to go:
green: working, no questions
yellow: have a question, but not blocked from doing work
red: have a question, blocked from doing work
blue: done, just hanging out
Articulation practice
Remember: this is an opportunity to practice clear, concise and precise communication while working through the material!
Throughout the course, each of you must volunteer at least once to serve as the facilitator, who will:
Make sure everyone has a chance for their voice to be heard. For example, saying:
“X, we haven’t heard from you in a while. Do you have thoughts on this problem or is there another one you’d like to shift to?”Keep track of time to cover as much of each problem as possible
Post a clearly articulated report with a summary and/or questions to the corresponding Ed Discussion category
Please be sure to also post your pod # and other team members, as in “Report for Pod 2 (Audrey St. John, Mary Lyon, …)”
If you’d prefer to use a doc, post the link or turn it into an image to attach
If you have work from the board, you can take a photo and post it
Each group will work on one of the following problems that has to do with strings.
Group 1
String matching: determine every occurrence of one string within another string (which may be none).
Group 2
Longest common subsequence: given two strings, find the longest common subsequence. A subsequence is a sequence of letters in the string that maintains the order, but may drop some letters. For example, cat is a subsequence of acrobat obtained by dropping the letters at indices 0, 2, 3 and 4.
Group 3
Longest substring that can form a palindrome: given a string, find the longest substring (consecutive letters) that can be rearranged to form a palindrome. A palindrome is a string whose reverse is the same; for example, the word "kayak" is a palindrome.
Group 4
Longest valid parentheses substring: given a string of open and close parentheses, determine the longest substring that is well-formed. For example, ()(())() is well-formed, while ()()) is not.
The Agenda
Step 0 [10 minutes]
generate sample instances and expected output
if you can, come up with a "real-world" problem that could motivate the problemStep 1 [5 minutes]
formulate the problem precisely: write a function signatureStep 2 [20 minutes]
come up with a process that tries to solve the problem;
write pseudocodeStep 3 [5 minutes]
try to "break" your process by finding an instance for which it gives the incorrect outputStep 4 [10 minutes]
perform a big-O analysis for the process' timeDebrief [5 minutes/group]
report out your group's process