data structure

CIS 121—Data Structures and Algorithms—Spring 2020 Dijkstra’s and Minimum Spanning Trees—Monday, March 30 / Tuesday, March 31 Readings • Lecture Notes Chapter 20: Dijkstra’s Algorithm • Lecture Notes Chapter 21: Minimum Spanning Trees Problems Problem 1 1. True or false: Dijkstra’s algorithm will not terminate if run on a graph with negative edge weights. Solution: […]

Readings CIS 121—Data Structures and Algorithms—Spring 2020 Hashing—Monday, April 13 / Tuesday, April 14 • Lecture Notes Chapter 23: Hashing Problems Problem 1 With n distinct balls in m distinct bins what is the probability that no bucket has more than 1 ball? You may assume that n ≤ m. Solution We will treat this

Readings CIS 121—Data Structures and Algorithms—Spring 2020 Stacks, Queues & Heaps—Monday, February 17/Tuesday, February 18 Solution Set • Lecture Notes Chapter 13: Stacks & Queues • Lecture Notes Chapter 14: Binary Heaps & Heapsort Problems Problem 1 Consider an indefinitely long stream of unsorted integers. We are interested in knowing the median (in sorted order)

Readings CIS 121—Data Structures and Algorithms—Spring 2020 Shortest Path in DAGs + Union-Find—Monday, April 6 Solution Set • Lecture Notes Chapter 20.3: Shortest Path in DAGs • Lecture Notes Chapter 22: Union Find Problems Problem 1 True or False: The shortest path algorithm in an edge weighted DAG works even with negative edge weights. Solution

Deadline + Late Penalty¶ Note : It will take you quite some time to complete this project, therefore, we earnestly recommend that you start working as early as possible. • Submission deadline for the Project is 20:59:59 on 24th Apr, 2020 (Sydney Time). • LATE PENALTY: Late Penalty: 10-% on day-1 and 20% on each

Readings Divide Conquer Combine Can we divide this into equivalent subproblems? Yes, we can divide this array into two halves each with n elements. Thus, each is an equivalent subproblem. 2 How can we recursively sort the two halves? That’s easy! Since we already broke it into subprob- lems, we will recurse using Mergesort on