Module 12: Patterns of Algorithm

CMPS 260: Data Structures

Introduction

Besides what we have seen so far in terms of data structures and algorithms, there are other approaches that deserve some attention (we have seen some bits and pieces already). This includes recursion, dynamic programming, greedy algorithms, and functional programming. Recursion is a very elegant way to solve problems where a function repeatedly calls itself, and every call gets a little bit closer to the final solution. Dynamic programming divides a bigger problem into smaller, dependent subproblems and combines them to get to a final solution. Greedy programming is a simpler, heuristic approach that takes locally optimal decisions to potentially arrive at a globally optimal solution. Functional programming makes use of functions to solve problems and tries to avoid mutating state. Recursion is very common in the functional programming paradigm.

Module Objectives

  • Describe recursion
  • Implement recursion
  • Describe dynamic programming
  • Implement dynamic programming
  • Describe greedy algorithms
  • Implement greedy algorithms
  • Describe functional programming
  • Implement functional programming

Learning Resources

  • Module 12 Readings: Chapter 11
  • Module 12 Slides: Chapter 11

Learning Activities

  • Module 12 Assignment

For Further Study

Leave a Reply

Your email address will not be published. Required fields are marked *