# 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

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

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.
• Summative Assessment
• Try to solve more problems with dynamic programming method.

## Legacy Cycle

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.

Implement the method with dynamic programming.

GO PUBLIC

Post software implementation over internet.

## Pre-Lesson Quiz

1. What is recursion?
2. What is the limitation of divide and conquer in solving a knapsack problem?
3. What is computational time for brute force method in solving a knapsack problem?