# 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

**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.