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.

OBJECTIVE

By the next class period, students will be able to:

The objectives will require that students be able to:

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.

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?

What is the computational complexity of dynamic programming method for solving a knapsack problem?
Apply the method to the longest common sequence problem.