UTPA STEM/CBI Courses/Computer Science/Algorithm Design
Course Title: Computer Science
Lecture Topic: Algorithm Desigm
Instructor: Bin Fu
Institution: University of Texas - Pan American
Backwards Design
[edit | edit source]Course Objectives
- Primary Objectives- By the next class period students will be able to:
- Understand the basic dynamic programming method
- Find the recursion for dynamic programming
- Find the right order to build up the table for dynamic programming
- Solve a knapsack problem with dynamic programming
- Sub Objectives- The objectives will require that students be able to:
- Input of data
- Implementation
- Performance
- Complexity analysis
- Difficulties- Students may have difficulty:
- Identifying the recursion for dynamic programming, and the hardship to build up the table.
- Real-World Contexts- There are many ways that students can use this material in the real-world, such as:
- A knapsack problem has many interesting applications. It is one of the classical NP-hard problems.
Model of Knowledge
- Concept Map
- Recursion
- Dynamic Programming
- Greedy Method
- Approximation
- NP-completeness
- Content Priorities
- Enduring Understanding
- Recursion
- Dynamic Programming
- Greedy Method
- Approximation
- Important to Do and Know
- Find the size of sub-problems
- Determine the size of the table of dynamic programming
- Finding an accurate approximation
- Worth Being Familiar with
- Memory allocation
- Complexity analysis
- Approximation
- Enduring Understanding
Assessment of Learning
- Formative Assessment
- In Class (groups)
- Give an example to the students and ask them solve it with dynamic programming method.
- Homework (individual)
- Ask them to solve the Knapsack problem with dynamic programming method.
- In Class (groups)
- Summative Assessment
- Try to solve more problems with dynamic programming method.
Legacy Cycle
[edit | edit source]OBJECTIVE
By the next class period, students will be able to:
- Be efficient in finding a recursion for solving a computational problem.
The objectives will require that students be able to:
- Effectively shrink a computational problem.
THE CHALLENGE
How to handle the exponential number of cases in a knapsack problem.
GENERATE IDEAS
When the size of a knapsack is not too large, using a table to save the sum of subsets is better than trying all subsets.
MULTIPLE PERSPECTIVES
NP-hardness.
The methods of algorithm design depend on problems.
Each method can be applied to a specific class of problems.
RESEARCH & REVISE
Find new method to attack the problem with large Knapsack.
TEST YOUR METTLE
Implement the method with dynamic programming.
GO PUBLIC
Post software implementation over internet.
Pre-Lesson Quiz
[edit | edit source]- What is recursion?
- What is the limitation of divide and conquer in solving a knapsack problem?
- What is computational time for brute force method in solving a knapsack problem?
Test Your Mettle Quiz
[edit | edit source]- What is the computational complexity of dynamic programming method for solving a knapsack problem?
- Apply the method to the longest common sequence problem.