Lesson plan

Dynamic problem (algorithms)

In computer science, dynamic problems are problems stated in terms of changing input data. In its most general form, a problem in this category is usually stated as follows: * Given a structure composed of objects, find efficient algorithms and data structures to answer certain queries about the structure, while also efficiently supporting update operations such as insertion, deletion or modification of objects in the structure. Problems in this class have the following measures of complexity: * Space the amount of memory space required to store the data structure; * Initialization time time required for the initial construction of the data structure; * Insertion time time required for the update of the data structure when one more input element is added; * Deletion time time required for the update of the data structure when an input element is deleted; * Query time time required to answer a query; * Other operations specific to the problem in question The overall set of computations for a dynamic problem is called a dynamic algorithm. Many algorithmic problems stated in terms of fixed input data (called static problems in this context and solved by static algorithms) have meaningful dynamic versions.

Back to article

Article summary

In computer science, dynamic problems are problems stated in terms of changing input data. In its most general form, a problem in this category is usually stated as follows: * Given a structure composed of objects, find efficient algorithms and data structures to answer certain queries about the structure, while also efficiently supporting update operations such as insertion, deletion or modification of objects in the structure. Problems in this class have the following measures of complexity: * Space the amount of memory space required to store the data structure; * Initialization time time required for the initial construction of the data structure; * Insertion time time required for the update of the data structure when one more input element is added; * Deletion time time required for the update of the data structure when an input element is deleted; * Query time time required to answer a query; * Other operations specific to the problem in question The overall set of computations for a dynamic problem is called a dynamic algorithm. Many algorithmic problems stated in terms of fixed input data (called static problems in this context and solved by static algorithms) have meaningful dynamic versions.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.