Book Image

C# Data Structures and Algorithms - Second Edition

By : Marcin Jamro
Book Image

C# Data Structures and Algorithms - Second Edition

By: Marcin Jamro

Overview of this book

Building your own applications is exciting but challenging, especially when tackling complex problems tied to advanced data structures and algorithms. This endeavor demands profound knowledge of the programming language as well as data structures and algorithms – precisely what this book offers to C# developers. Starting with an introduction to algorithms, this book gradually immerses you in the world of arrays, lists, stacks, queues, dictionaries, and sets. Real-world examples, enriched with code snippets and illustrations, provide a practical understanding of these concepts. You’ll also learn how to sort arrays using various algorithms, setting a solid foundation for your programming expertise. As you progress through the book, you’ll venture into more complex data structures – trees and graphs – and discover algorithms for tasks such as determining the shortest path in a graph before advancing to see various algorithms in action, such as solving Sudoku. By the end of the book, you’ll have learned how to use the C# language to build algorithmic components that are not only easy to understand and debug but also seamlessly applicable in various applications, spanning web and mobile platforms.
Table of Contents (13 chapters)

Closest pair of points

Another example is an algorithm to find the closest pair of points located on the two-dimensional surface. It is an interesting algorithmic problem that can be solved using the divide-and-conquer paradigm.

Each point is represented by x and y coordinates, with values starting from (0, 0) in the top-left corner of the surface. To find the closest pair of points, you first sort all points according to the x coordinate, as shown in the following diagrams, marked from A to N:

Figure 9.3 – Diagrams of the algorithm to find the closest pair of points

Figure 9.3 – Diagrams of the algorithm to find the closest pair of points

Then, you divide the surface into two halves. You can do this by calculating half of the points count, namely 7 in our example, and taking the first 7 points as the left half and the next 7 points as the right half.

Here is a task for recursion, so you recursively find the closest points in both halves and store data as rl (points D and E) and rr (points I and K). You choose the...