Algorithms and Data Structures in C#: Complete Tutorial

Explore abstract data types and data structures, clarifying how an abstract data type defines behavior and a data structure provides implementation, using a stack with push, pop, and peek.

Explore the definition of an algorithm, its input-output transformation, and the formal steps that produce correct results, using sorting and insertion sort examples described in pseudocode.

Explore time complexity of a brute-force zero-sum triplet counter using nested loops, reading integers from files, and benchmarking how running time scales non-linearly with input size.

Build a log-log plot to predict running time from input size, using log base two, derive t(n) = a n^3, and validate with experimental data.

Explore order of growth from exponential to logarithmic, including cubic, quadratic, linear, and linearithmic time, and review worst-case big O guarantees.

Discover the basics of arrays in C#, including initialization, zero-based indexing, and length; explore memory layout, resize limits, and multi-dimensional and jagged arrays, plus array class utilities.

Explore the time complexities of common array operations, including access by index, search, add, insert, update, and remove, and see how resizing and copying affect performance.

Explain how stable sorts preserve the relative order of duplicates, with bubble sort as a stable example, and how a tiny change can render a sort unstable.

See how selection sort selects the largest element each pass and swaps it into place, an in-place, unstable, quadratic-time algorithm that sorts an unsorted array using a wall and iterator.

Insertion sort partitions the array with a wall, inserting each unsorted value into the sorted left side by shifting elements, an in-place and stable algorithm with quadratic time.

Demonstrates implementing insertion sort in a C# sorting class with a static void method, shifting elements to insert each unsorted item, and unit testing to verify sorted results.

Extend shell sort by pre sorting with gaps, starting large and reducing to one. Recognize that it is in place and unstable, with performance depending on the gap sequence.

Implement shell sort for an integer array by a generalized insertion sort using a gap sequence, with outer and inner loops and swaps, and verify with unit tests.

Explore merge sort, a divide-and-conquer sort algorithm, and follow its splitting and merging phases using an auxiliary array. Understand its stability, not in place nature, and base two time complexity.

Explore quicksort theory, a divide-and-conquer, in-place recursive algorithm using a pivot to partition elements, with average O(n log n) time and worst-case O(n^2).

Explore quicksort in C#: implement a recursive quicksort with a partition method, using low and high boundaries, a first-element pivot, i and j pointers, swaps, and base-case termination.

Explore the built-in list in .net, showing how it uses an internal array, tracks count and capacity, resizes, and supports operations like sort, binary search, reverse, and read-only views.

Examine the singly linked list and its adding operations to the front and tail with head and tail pointers, and removing first or last, noting constant and linear time behavior.

Learn to implement a generic singly linked list in C# with add first, add last, remove first, remove last, including head, tail, count, and unit tests.

Compare singly and doubly linked lists: the latter uses two references, next and previous, enabling constant-time removal of the last node, and invites considerations of circular variants and memory trade-offs.

Explore the built-in doubly linked circular list in the BCL, detailing head and tail references, node structure, and constant-time insertions at ends or before/after a node.

Explore the theory of stacks as an abstract data type, a last in, first out structure with push, pop, and peak; compare array versus linked list backing.

Implement a linked stack backed by a singly linked list, with push, pop, peek, and count guarded by empty checks. Include unit tests and an enumerable interface demonstration.

Explore how a queue enforces first in, first out with enqueue, dequeue, and peek, compare array and linked list backings, and understand memory issues and efficient slot usage.

Implement a circular queue by wrapping the tail to the array start, improving memory use. Manage wrapped states, copy elements in order, and unwrap by doubling the array when needed.

Implement a circular queue in C# with a generic type, backed by an array, supporting enqueue, dequeue, peek, and enumeration. Manage wrapping, dynamic resizing, and track head, tail, and count.

Implement a queue with a singly linked list, delegating enqueue to add last, dequeue to remove first, and peek to read the head, with guard clauses.

Learn how the built-in queue in the .NET BCL uses a circular array, doubles capacity on resize, and offers enqueue, dequeue, peek, contains, and clear with varying time costs.

Explore linear search by iterating arrays and lists to find elements, implement exists and index of, compare lists with linq methods like find, where, and all, and discuss time complexity.

Implement binary search in C#, iteratively and recursively, returning the index or -1, and keep the input sorted for fast lookups with insertion sort for new elements.

Explore symbol tables, or dictionaries in Dotnet, using key-value pairs for fast insertion and retrieval. Examine four implementations—linked list, parallel arrays, balanced binary tree, and hash table.

Explore API of symbol tables, comparing ordered and unordered variants, and implement operations such as add, get and try-get, lazy removal, remove, contains, min, max, floor, ceiling, rank, and select.

Study a simple symbol table built on a linked list with generic key-value pairs; implement try-get, add, contains, and keys, and discuss linear search performance.

Implement remove method for a sequential search symbol table, ensuring non-null keys and no lazy removal, adjusting counter, removing the key-value pair fully, and returning true if found, false otherwise.

Explore a binary search based symbol table using two parallel arrays for keys and values, with rank, get value or default, add, remove, and capacity resizing.

Implement min, max, remove, select, sailing and floor in a binary search based symbol table, using rank for range queries and guarding null keys.