UTPA STEM/CBI Courses/Computer Science/Algorithm Design

From Wikiversity
Jump to navigation Jump to search

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

Legacy Cycle[edit | edit source]


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.


How to handle the exponential number of cases in a knapsack problem.


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.



The methods of algorithm design depend on problems.

Each method can be applied to a specific class of problems.


Find new method to attack the problem with large Knapsack.


Implement the method with dynamic programming.


Post software implementation over internet.

Pre-Lesson Quiz[edit | edit source]

  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?

Test Your Mettle Quiz[edit | edit source]

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