CSC 242

Winter 2024

Craig Miller

• Home
• Basic Information
• Grades and Policies
• Schedule

Weekly Notes

• Week 1
• Week 2
• Week 3
• Week 4
• Week 5
• Week 6
• Week 7
• Week 8
• Week 9
• Week 10

Labs

• Lab 1
• Lab 2
• Lab 3
• Lab 5
• Lab 6
• Lab 7
• Lab 8
• Lab 9

Assignments

• Assignment 1
• Assignment 2
• Assignment 3
• Assignment 4
• Assignment 5
• Assignment 6
• Assignment 7
• Assignment 8

Lab 5
Study a recursive algorithm that produces letter unscramblings
Submit after the end of the lab session

Overview

For this lab, you will study a recursive function that runs through all letter permutations (unscramblings) for a given string. In addition to counting the number of checked permutations, you will modify it so that it includes attempts that use any subset of the letters.

Instructions, questions, and code writing

1. Download the zip folder for the lab.
2. Run unscramble with strings of various lengths. At what string length does the function take too long for your patience?
3. In your own words, describe what happens to the source string and target string at each level.
4. How many permutations does a 3 letter string produce? How aboue 4 letters? Write down your answers! How do you know?
5. Uncomment the dictionary check (if target in ds) and indent the print so that it only prints actual words. Run it several times on different combinations of letters to see how it works.
6. Using the Counter class, add a counter that keeps track of how many dictionary checks occur:
   1. Create a counter object in unscramble before the recurrence function is called. Give it a meaningful variable name.
   2. Add the name of your counter object as a fifth argument/parameter to all recurrence calls and its definition.
   3. Just before the dictionary check in the recurrence function, call the count method on your Counter object.
   4. At the end of unscramble, print the counter object.
7. Run unscramble with the counter. Does its output confirm your predictions?
8. Create copies of unscramble and recurrence and call them unscramble2 and recurrence2. Make sure that your copies refer to the new name for all function calls. Modify recurrence2 so that it checks the character target even when there are still characters left in stock. This way, unscramble2 will report letter combinations that only use some of the characters from the original string. Test and check your new function.
9. Question: the recurrence function is somewhat inefficient in that it explores possibilities that won't produce any words. How could this function be made more efficient? Required: a throughtful, refective answer. Optional (somewhat advanced): an implementation of your efficient modification.

Deliverable

Create a text (preferred) or pdf file that contains the following:

1. A statement that summarizes your completion of the lab. As appropriate, the statement should include the following:
   • Who you worked with on the lab
   • Any difficulties you encountered
   • Answer to questions
   • Pasted output showing your functions running
2. A summary of the files included in the zip folder

Put your files in a folder, zip it and submit it under Lab 5 on D2L. Check that your submitted zip file is complete.

Grading

Your lab submission will be graded using the following rubric:

• + .5 --- Your submission is clearly formatted.
• + .5 --- Your submission includes a summary statement and includes how you collaborated.
• + .5 / 1.0 --- You submitted most of the lab (0.5) or you submitted all of the lab (1.0).
• + .5 --- Your lab submission is generally correct.