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
- Read more about recursion on Wikipedia
- Read more about dynamic programming on Wikipedia
- Read more about greedy algorithms on Wikipedia
- Read more about functional programming on Wikipedia