data structure

CS 124 Section 1 Binary Min/Max Heaps Yash Nair February 2021 Yash Nair Section 1 February 2021 1 / 25 Table of Contents What is a Heap and Why do we Use Them? Heap Basics Representing a Heap Implementing Heap Operations Problems Yash Nair Section 1 February 2021 2 / 25 Purpose of Heaps Data

CS124 Lecture 6 Spring 2011 Disjoint set (Union-Find) For Kruskal’s algorithm for the minimum spanning tree problem, we found that we needed a data structure for maintaining a collection of disjoint sets. That is, we need a data structure that can handle the following operations: • MAKESET(x) – create a new set containing the single

CS124 Lecture 4 Spring 2011 Breadth-First Search A searching technique with different properties than DFS is Breadth-First Search (BFS). While DFS used an implicit stack, BFS uses an explicit queue structure in determining the order in which vertices are searched. Also, generally one does not restart BFS, because BFS only makes sense in the context

CS 124 Lecture 2 In order to discuss algorithms effectively, we need to start with a basic set of tools. Here, we explain these tools and provide a few examples. Rather than spend time honing our use of these tools, we will learn how to use them by applying them in our studies of actual

CS124 Lecture 3 Spring 2011 Graphs and modeling Formulating a simple, precise specification of a computational problem is often a prerequisite to writing a computer program for solving the problem. Many computational problems are best stated in terms of graphs. A directed graph G(V,E) consists of a finite set of vertices V and a set

Amortized Analysis and Hashing Ted Pyne Table of Contents ¡ñ Amortized Analysis ¡ñ Hashing Amortized Analysis ¡ñ Normal: Require our data structure to be fast on every operation ¡ñ Amortized: Require our data structure to be fast ¡°in total¡± Track runtime using potential function Cost of operation = real work + change in potential function