Due: Friday before class (submit on Moodle + be ready to demo)
Overview
You will improve the wall-designer-starter Python algorithm.
The current algorithm is simple and produces acceptable but weak results. Your task is to design and implement a significantly better greedy algorithm.
The emphasis is not just on the final result, but on trying multiple ideas, evaluating them, and explaining what works.
Your Task
You will:
- Modify the Python wall designer.
- Try multiple improvements to the greedy strategy.
- Compare results using the visualizer.
- Select your best version.
- Submit a short writeup explaining your work.
Requirements
1. Implement an Improved Greedy Algorithm
Your algorithm must still be greedy, meaning:
- it builds the wall step by step
- it makes decisions incrementally
However, it should be substantially better than the starter version.
2. Try Multiple Improvements
You must try at least 3 different improvement ideas.
Examples of possible improvements:
Scoring-Aware Selection
- At each step, try adding multiple candidates
- Evaluate using the scoring function
- Choose the best next addition
Better Candidate Ordering
- Sort artworks before placement by:
- focal weight
- size
- visual intensity
- theme
Smarter Placement Decisions
- Improve spacing
- Avoid awkward gaps
- Consider alignment or grouping
Multi-Start Greedy
- Run your algorithm multiple times with different orderings
- Keep the best result
Filtering or Pruning
- Remove clearly bad candidates early
- Avoid overcrowding
Local Improvement Step
- After building a wall:
- swap artworks
- remove weak choices
- try replacements
Hybrid Ideas
- Combine multiple strategies above
3. Test and Compare
For at least 2 different walls:
- Run your different algorithm versions
- Upload results to the web app
- Use the visualizer to compare outcomes
You should clearly see differences between your approaches.
Deliverables
A. Code
- Your modified Python algorithm
B. Writeup (1–2 pages)
Your writeup must include:
1. Description of Improvements
- What ideas did you try?
- How did each version differ?
2. Results
- Which approaches worked better?
- Which did not work well?
3. Final Algorithm
- What is your final approach?
- Why is it better than the original?
4. Reflection
- What did you learn about greedy algorithms?
- What would you try next if you had more time?
C. In-Class Demonstration
Be prepared to show:
- one or two walls
- different versions you tried
- your final result
- a brief explanation of your approach
Grading Rubric (100 points)
Exploration and Effort (40 points)
- 10 pts: Tried at least 2 improvements
- 20 pts: Tried at least 3 meaningful improvements
- 30 pts: Tried several distinct approaches
- 40 pts: Extensive exploration with thoughtful variations
Algorithm Quality (25 points)
- 10 pts: Minor improvement over baseline
- 15 pts: Clear improvement in behavior
- 20 pts: Strong improvement in most cases
- 25 pts: Consistently produces noticeably better walls
Understanding and Explanation (25 points)
- 10 pts: Basic explanation of approach
- 15 pts: Clear explanation of ideas and results
- 20 pts: Good analysis of what worked and why
- 25 pts: Insightful explanation with strong reasoning
Code Quality (10 points)
- 5 pts: Code runs correctly
- 8 pts: Code is reasonably organized
- 10 pts: Clean, readable, and well-structured
Summary
- Modify the greedy algorithm
- Try multiple improvements
- Compare results
- Explain what worked
Key Idea
This is not about finding the best algorithm.
It is about learning how:
algorithm design = experimentation + evaluation + iteration