# Essential Algorithms in C# with Examples and Complexities

A compact reference of the fundamental algorithms every programming student should learn — with C# examples, short explanations, and Big-O complexity.

---

## 📘 Table of Contents

1. [Finding Minimum and Maximum](#1-finding-minimum-and-maximum)
2. [Summation and Average](#2-summation-and-average)
3. [Filtering (Selection)](#3-filtering-selection)
4. [Linear Search](#4-linear-search)
5. [Binary Search](#5-binary-search)
6. [Sorting Algorithms](#6-sorting-algorithms)
7. [Counting Elements / Frequency Map](#7-counting-elements--frequency-map)
8. [Reversing a Collection](#8-reversing-a-collection)
9. [Recursion Basics](#9-recursion-basics)
10. [Tree Traversal (DFS)](#10-tree-traversal-depth-first-search)
11. [Graph Traversal (BFS)](#11-graph-traversal-breadth-first-search)
12. [Swapping Elements](#12-swapping-elements)
13. [Removing Duplicates](#13-removing-duplicates)
14. [Merging Two Sorted Arrays](#14-merging-two-sorted-arrays)
15. [Matrix Operations](#15-matrix-operations)
16. [String Algorithms](#16-string-algorithms)
17. [Sorting by Custom Criteria](#17-sorting-by-custom-criteria)
18. [Aggregate / Reduce](#18-aggregate--reduce)
19. [Algorithmic Thinking Summary](#19-algorithmic-thinking-summary)

---

## 1. Finding Minimum and Maximum

**Concept:** Iterate through elements and keep track of smallest/largest value.  
**Complexity:** O(n)

```csharp
int[] numbers = { 5, 2, 9, 1, 3 };
int min = numbers[0], max = numbers[0];

foreach (int n in numbers)
{
    if (n < min) min = n;
    if (n > max) max = n;
}
Console.WriteLine($"Min = {min}, Max = {max}");
```

---

## 2. Summation and Average

**Complexity:** O(n)

```csharp
int sum = numbers.Sum();
double avg = numbers.Average();
```

---

## 3. Filtering (Selection)

**Complexity:** O(n)

```csharp
List<int> even = numbers.Where(x => x % 2 == 0).ToList();
```

---

## 4. Linear Search

**Complexity:** O(n)

```csharp
int target = 3;
bool found = numbers.Contains(target);
```

---

## 5. Binary Search

**Requires sorted array.**  
**Complexity:** O(log n)

```csharp
int[] sorted = { 1, 2, 3, 4, 5, 6 };
int idx = Array.BinarySearch(sorted, 4);
```

---

## 6. Sorting Algorithms

### Bubble Sort (for teaching basics)
**Complexity:** O(n²)

```csharp
int[] arr = { 5, 3, 8, 1 };
for (int i = 0; i < arr.Length - 1; i++)
    for (int j = 0; j < arr.Length - i - 1; j++)
        if (arr[j] > arr[j + 1])
            (arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
```

### Built-in Sort (QuickSort / Timsort Hybrid)
**Complexity:** O(n log n)

```csharp
Array.Sort(arr);
```

---

## 7. Counting Elements / Frequency Map

**Complexity:** O(n)

```csharp
string text = "hello world";
Dictionary<char, int> freq = new();
foreach (char c in text)
{
    if (c == ' ') continue;
    freq[c] = freq.ContainsKey(c) ? freq[c] + 1 : 1;
}
```

---

## 8. Reversing a Collection

**Complexity:** O(n)

```csharp
int[] a = { 1, 2, 3, 4 };
Array.Reverse(a);
```

---

## 9. Recursion Basics

**Example:** Factorial  
**Complexity:** O(n)

```csharp
int Factorial(int n) => (n <= 1) ? 1 : n * Factorial(n - 1);
```

---

## 10. Tree Traversal (Depth-First Search)

**Complexity:** O(n)

```csharp
class Node { public int Val; public Node? Left, Right; public Node(int v) => Val = v; }

void InOrder(Node? n)
{
    if (n == null) return;
    InOrder(n.Left);
    Console.Write($"{n.Val} ");
    InOrder(n.Right);
}
```

---

## 11. Graph Traversal (Breadth-First Search)

**Complexity:** O(V + E)

```csharp
Dictionary<int, List<int>> graph = new() {
    [1] = new() { 2, 3 },
    [2] = new() { 4 },
    [3] = new() { 4 },
    [4] = new() { }
};

Queue<int> q = new();
HashSet<int> visited = new();
q.Enqueue(1);
visited.Add(1);

while (q.Count > 0)
{
    int node = q.Dequeue();
    Console.Write($"{node} ");
    foreach (int neigh in graph[node])
        if (!visited.Contains(neigh))
        {
            visited.Add(neigh);
            q.Enqueue(neigh);
        }
}
```

---

## 12. Swapping Elements

**Complexity:** O(1)

```csharp
int x = 5, y = 9;
(x, y) = (y, x);
```

---

## 13. Removing Duplicates

**Complexity:** O(n)

```csharp
int[] data = { 1, 2, 2, 3, 3, 4 };
var unique = data.Distinct().ToArray();
```

---

## 14. Merging Two Sorted Arrays

**Complexity:** O(n + m)

```csharp
int[] a1 = { 1, 3, 5 };
int[] a2 = { 2, 4, 6 };
int[] merged = a1.Concat(a2).OrderBy(x => x).ToArray();
```

---

## 15. Matrix Operations

**Complexity:** O(n²)

```csharp
int[,] matrix = { { 1, 2 }, { 3, 4 } };
int diagSum = 0;
for (int i = 0; i < 2; i++) diagSum += matrix[i, i];
```

---

## 16. String Algorithms

### Reverse String
```csharp
string s = "hello";
string rev = new string(s.Reverse().ToArray());
```

### Palindrome Check
```csharp
bool IsPalindrome(string str)
{
    str = str.ToLower();
    return str.SequenceEqual(str.Reverse());
}
```

---

## 17. Sorting by Custom Criteria

**Complexity:** O(n log n)

```csharp
var people = new[] {
    new { Name = "Bob", Age = 30 },
    new { Name = "Alice", Age = 25 }
};
var sorted = people.OrderBy(p => p.Age);
```

---

## 18. Aggregate / Reduce

**Complexity:** O(n)

```csharp
int product = numbers.Aggregate(1, (acc, x) => acc * x);
```

---

## 19. Algorithmic Thinking Summary

| Algorithm Type | Example | Typical Complexity |
|----------------|----------|--------------------|
| Find Min/Max | Linear scan | O(n) |
| Search (Linear) | Sequential | O(n) |
| Search (Binary) | Sorted array | O(log n) |
| Sort | Bubble / QuickSort | O(n²) / O(n log n) |
| Filter | Predicate | O(n) |
| Count Frequency | HashMap | O(n) |
| Reverse | Swap | O(n) |
| Recursion | Factorial | O(n) |
| Tree Traversal | DFS | O(n) |
| Graph Traversal | BFS | O(V + E) |
| Matrix Sum | Double loop | O(n²) |

---

**Author:** Dr. Stoyan Cheresharov  
**University:** Plovdiv University “Paisii Hilendarski”  
**Course:** Algorithms and Data Structures in C# (.NET)

---