Algorithm Bounds
Table of contents
- Some math problems
- Ultimate Comparison Sort
- Puppy, cat, dog
- Sorting lower bound
- Algorithm lower bounds
- Algorithms for change
- How far we’ve come
- What’s next?
Some math problems
Ultimate Comparison Sort
Puppy, cat, dog
Sorting lower bound
Algorithm lower bounds
How can we apply the sorting lower bound to other problems in data structures and algorithms?
Question 1
Consider a priority queue implementation that guarantees worst-case Θ(1) runtime for all methods. Without knowing anything about the optimization, give a runtime argument for why this optimization is impossible. (What would this suggest about the worst-case runtime for heapsort?)
Question 2
Earlier, we learned that the problem of finding duplicates in an array reduces to sorting. If we know that the worst-case runtime for comparison-based sorting algorithms must be in Ω(Nlog N), is it true that the worst-case runtime for any duplicate-finding algorithm must also be in Ω(Nlog N)?
Explanation
A reduction to sorting is just one approach to detecting duplicates! Learning something about one algorithm for solving a problem doesn’t preclude other possible algorithms.
We could alternatively use a HashSet. Instantiate an empty HashSet. For each element in the (unsorted) input array, first check if it is in the HashSet. If the element is already in the HashSet, return true. Otherwise, add it to the HashSet and continue to the next element.
Algorithms for change
How far we’ve come
Starting with search trees, we designed faster data structures and algorithms: design as optimization.
- DNA Indexing
- Comparing tree search structures against array search algorithms.
But beyond understanding the past, algorithms are about shaping the future: design as engineering.
- Content Moderation
- Optimizing algorithms with a composition of data structures.
Beyond data structures, how we model problems determines social outcomes: design as philosophy.
- Image Processing
- Comparing graph abstractions and algorithms for DAG shortest paths.
What’s next?
Learning about data structures and algorithms opens the door to the broader field of computer science. What interests you?
- CSE 374: Intermediate Programming Concepts and Tools
- Learn popular tools used by professional programmers and exactly how hardware and code interact inside a physical computer.
- CSE 413: Programming Languages
- Learn new ways of thinking about problems through studying different programming languages as well as how they work under the hood.
- CSE 414: Database Systems
- Learn how to store, access, and query huge amounts of data in databases—more than what you can store in memory-backed data structures.
- CSE 415: Artificial Intelligence
- Learn about computational models of human cognition and techniques for learning, understanding signals, and solving problems.
- CSE 416: Machine Learning
- Learn how to apply machine learning algorithms to solve some of the hardest problems that we faced this quarter.
- CSE 163: Intermediate Data Programming
- Learn programming concepts, libraries, and tools to help people answer complicated questions and make informed decisions.
- CSE 154: Web Programming
- Learn the foundations and fundamentals of web development and web technologies to develop websites and web apps.
The entire field of computer science is now accessible to you: the research project is one way to start digging into all of the online learning resources with help from your project team. You’ve learned the fundamentals of algorithm design, analysis, and critique from three perspectives: design optimization, engineering, and philosophy. And in today’s lesson, we learned about what algorithms can and can’t do: design alone as insufficient.
- Research Project
- Exploring possibilities and limits of data structures and algorithms.