Thought Provokers

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?

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?

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?

What are some benefits and drawbacks of simpler problem models, as they compare to more complicated problem models?

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).

Since binary search is in O(N), it is also true that binary search is in O(N²). Explain why computer scientists might find O(N²) to be a less useful description of the runtime of binary search compared to O(log N).

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?

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?

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?

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?