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 approximations and order of growth by trimming insignificant terms with tilt approximation, focusing on frequency of statement execution and how constants and high-order terms shape running time estimates.

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 how arrays are laid out in memory as reference types, with heap data and stack references, including contiguity and constant-time access, and how 32-bit versus 64-bit pointers differ.

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.

Explore bubble sort theory with animated demonstrations, tracking i and j and the wall that divides sorted and unsorted parts, and learn its in-place, stable, quadratic time limitations.

Implement a bubble sort in C# with a swap helper and a decreasing wall, and validate results using unit tests in dotnet and NUnit.

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.

Implement selection sort in C# by tracking the largest element each pass and swapping it with the unsorted portion. Validate with unit tests and note the quadratic time complexity.

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.

Explore recursion by tracing a recursive factorial and its base case, compare it with an iterative version, and understand stack overflow and recursion depth limits.

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.

Implement a merge sort in C# with local functions inside the merge sort method, including sorting, merging, an auxiliary array, and a unit test.

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.

Explore linked lists by treating a node as the basic building block that stores data and points to the next node, then implement a Node class and iterate the chain.

Explore linked lists as an abstract data type, detailing head and tail references, core operations (add, remove, find, enumerate), and the differences between singly and doubly linked lists.

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 generic array stack in C# with push, peak, and pop; expose is empty and count; and support enumeration via IEnumerable<T> and yield return, guided by tests and TDD.

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 the built-in dotnet stack from system.collections.generic, its array-backed design, and operations like push, pop, and peek, with constant time for peek and pop and linear time for resizing.

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.

Explore how to implement a queue based on an array using generics, with head and tail, enqueue and dequeue operations, and dynamic resizing when full.

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.

Binary search divides a sorted array in halves, compares the middle element, and continues in the left or right half to locate the target in log n steps.

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.

Implement the remove method for a singly linked list, guarding with argument null exception on a null key, and update first, current, and previous references to return true when removed.

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 methods based on key ordering for a binary search-based symbol table, covering min, max, remove min, remove max, select by index, sailing, floor, and range queries.

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

Explore how symbol tables enable fast key-based data retrieval, comparing ordered and unordered forms and why binary search symbol tables trade log n search time for linear insertion.