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)

What this book covers

Chapter 1, Data Types, introduces you to the topic of the data types available while developing applications in the C# programming language, both value and reference ones. You will learn about the built-in value types, such as integral or floating-point numbers, as well as constants, enumerations, value tuples, user-defined struct types, and nullable value types. As for the reference types, you will see object and string types, classes, records, interfaces, and delegate and dynamic types, as well as nullable reference types.

Chapter 2, Introduction to Algorithms, presents you with an algorithm definition and some real-world examples from your daily life. Then, you will learn a few notations for algorithms, namely natural language, a flowchart, pseudocode, and a programming language. Various types of algorithms are shown as well, including recursive, divide and conquer, back-tracking, greedy, heuristic, brute force, and dynamic programming. Computational complexity, including time complexity, is also presented and explained.

Chapter 3, Arrays and Sorting, covers scenarios storing data using some representatives of random access data structures, namely arrays. First, three variants of arrays are explained, that is, single-dimensional, multi-dimensional, and jagged. You’ll also get to know seven popular sorting algorithms, namely selection sort, insertion sort, bubble sort, merge sort, Shell sort, quicksort, and heap sort. All of these algorithms are shown with illustrations, implementation code, and detailed explanations.

Chapter 4, Variants of Lists, deals with other representatives of random access data structures, namely a few variants of lists. Lists are similar to arrays, but make it possible to dynamically increase the size of the collection if necessary. A few variants of lists, including a singly linked list, a doubly linked list, a circular singly linked list, and a circular doubly linked list are introduced. Such data structures are presented in illustrations, are implemented using C# code, and are explained in detail.

Chapter 5, Stacks and Queues, explains how to use two variants of limited access data structures, namely stacks and queues, including priority and circular queues. The chapter shows how to perform push and pop operations on a stack, and also describes the enqueue and dequeue operations in the case of a queue. To aid your understanding of these topics, a few examples are presented, including the Tower of Hanoi game and an application that simulates a call center with multiple consultants and callers.

Chapter 6, Dictionaries and Sets, focuses on data structures that make it possible to map keys to values, perform fast lookups, and carry out various operations on sets. The chapter introduces you to both non-generic and generic variants of a hash table, the sorted dictionary, and the high-performance solution to set operations allowing you to get union, intersection, subtraction, and symmetric difference. The “sorted” set concept is shown, as well.

Chapter 7, Variants of Trees, describes a few tree-related topics. First, it presents a basic tree, together with its implementation in C#, and examples showing it in action. The chapter also introduces you to binary trees, binary search trees, and self-balancing trees, namely AVL and red-black trees. Then, you’ll see a trie that is a great approach for performing string-related operations. The remainder of the chapter is dedicated to a brief introduction to the topic of binary heaps as other tree-based structures.

Chapter 8, Exploring Graphs, contains a lot of information about graphs, starting with an explanation of their basic concepts, including nodes and a few variants of edges. The C#-based implementation of a graph is also covered. The chapter introduces you to two modes of graph traversal, namely depth-first and breadth-first search. Then, it presents the subject of minimum spanning trees using Kruskal’s and Prim’s algorithms, the node coloring problem, and finding the shortest path in a graph using Dijkstra’s algorithm.

Chapter 9, See in Action, presents a few examples of various types of algorithms. You’ll see a recursive way to calculate a number from the Fibonacci series, with dynamic programming optimization. Then, you’ll learn a greedy approach to a minimum coin change problem, a divide-and-conquer method of getting the closest pair of points, a recursive way of generating fractals, a back-tracking and recursive way of solving rat in a maze and Sudoku puzzles, as well as a genetic algorithm and brute-force password guessing.

Chapter 10, Conclusion, is the conclusion of all the knowledge acquired from the previous chapters. It shows a brief classification of data structures, dividing them into two groups, namely linear and nonlinear. Finally, the chapter talks about the diversity of applications of various data structures. Each data structure is presented with a brief description and some of them are also shown with illustrations, to help you remember the information learned while reading the previous nine chapters.