Skip to ContentGo to accessibility page
OpenStax Logo
Introduction to Computer Science

Thought Provokers

Introduction to Computer ScienceThought Provokers

Thought Provokers

1 .
Maps can be defined in terms of sets: every map is a set whose elements represent key-value pairs, where the key must be unique, but the value might not be unique. Consider other relationships between abstract data types. Can sets and maps be defined in terms of graphs? Can lists be defined in terms of maps? Can priority queues be defined in terms of maps? Why might it be useful to define abstract data types in terms of other data types?
2 .
Graph theory refers to the mathematical study of graphs. How might a graph theorist describe linked lists and tree data structures? How does this differ from our use of abstract data types?
3 .
Sorting and searching are two examples of data structure problems related to the storage and retrieval of elements. Where do sorting and searching appear in linear data structures, tree data structures, and/or graph data structures?
4 .
What are some benefits and drawbacks of simpler problem models, as they compare to more complicated problem models?
5 .
The formal definition of Big O notation does not exactly match our working definition for orders of growth. Do some additional research to explain why binary search is also in O(N).
6 .
Since binary search is in O(N), it is also true that binary search is in O(N2). Explain why computer scientists might find O(N2) to be a less useful description of the runtime of binary search compared to O(log N).
7 .
We can show that the worst-case order of growth for any comparison sorting algorithm must be at least linearithmic using an argument from combinatorial explosion in the number of unique permutations of elements in a list. What are the number of unique permutations of a list with N elements? How many comparison questions need to be asked to identify a particular permutation from among all the permutations? How do these questions relate to comparison sorting?
8 .
Breadth-first search is a fundamental algorithm design pattern for graph problems. How is breadth-first search applied as a foundation for designing greedy algorithms such as Prim’s algorithm and Dijkstra’s algorithm? How does Kruskal’s algorithm fit into these algorithm design patterns and paradigms? If Prim’s algorithm is analogous to sorting in Kruskal’s algorithm, why is there no analogue to the Dijkstra’s algorithm in sorting as well?
9 .
Suppose we want to find the longest path from a starting vertex to an ending vertex in a graph. How might a nondeterministic algorithm solve this problem in polynomial time?
10 .
Suppose we want to find the longest path from a starting vertex to an ending vertex in a graph (solving the function problem) without using a nondeterministic algorithm. Let’s say that P = NP and we have a deterministic polynomial-time algorithm that returns whether there is a path with exactly cost k (solving the decision problem). We also know the cost of the actual longest path. How can we repeatedly apply this decision algorithm to design a polynomial-time longest paths function algorithm?
PreviousNext
Order a print copy
Citation/Attribution
Reuse and redistribution of this content in digital or print format:
  • This book may not be used in the training of large language models or otherwise be ingested into large language models or generative AI offerings without OpenStax's prior written permission.
  • This book uses the Creative Commons Attribution-NonCommercial-ShareAlike License, which means that you can reuse and modify the material only for noncommercial purposes, must attribute OpenStax, and must distribute any derivative works under the same license.
  • Any commercial printing of this textbook, including using a local or custom printer, must be approved by OpenStax, and proper citation provided.
  • OpenStax-copyrighted images, activities, assessments, and similar components of this book are subject to the same licensing – CC-BY-NC-SA. They can be used for noncommercial purposes with attribution. Commercial use requires permission.
  • Permission requests: Anyone who intends to incorporate this content (including text, images, and other components) into large language models, use it in AI offerings, use it commercially (including in print), and/or has questions about another use case is welcome to complete our reuse request form.
Attribution information
  • If you are redistributing all or part of this book in a noncommercial print format, then you must include on every physical page the following attribution:

    Access for free at https://openstax.org/books/introduction-computer-science/pages/1-introduction

  • If you are redistributing all or part of this book in a noncommercial digital format, then for every page that includes OpenStax content, you must license the derivative work under the same CC-BY-NC-SA license as the original, and include on every digital page view the following attribution:

    Access for free at https://openstax.org/books/introduction-computer-science/pages/1-introduction

Citation information

The information below includes the information needed to generate citations in most major styles (APA, MLA, etc.); you must reformat and organize the information as needed to fit the requirements of the style. Use the information below to generate a citation. We recommend using a citation tool such as this one.

© Apr 23, 2026 OpenStax. Textbook content produced by OpenStax is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike License. The OpenStax name, OpenStax logo, OpenStax book covers, OpenStax CNX name, and OpenStax CNX logo, and Rice University name, and Rice University logo trademarks, or wordmarks are not subject to the Creative Commons license and may not be reproduced without the prior and express written consent of Rice University.