Introduction
Welcome to Module 10 of our Complete C# Course: From Beginner to Advanced! After mastering modern C# features in Module 9, it’s time to sharpen your algorithms and problem-solving skills with over 20 hands-on challenges. In this module, we’ll cover foundational algorithms like Fibonacci, prime numbers, factorial, and palindrome checks, as well as advanced topics like sorting algorithms, search algorithms, recursion, and dynamic programming. We’ll apply these in a practical algorithm workbench for a data analysis tool, inspired by real-world applications like financial modeling or inventory optimization. With detailed examples, best practices, and pros/cons, you’ll be ready to tackle coding interviews and optimize C# applications. Let’s dive in!
1. Fibonacci Series (Iterative & Recursive)
The Fibonacci series generates numbers where each number is the sum of the two preceding ones (e.g., 0, 1, 1, 2, 3, 5, ...).
Example: Fibonacci Calculator
using System;
namespace AlgorithmWorkbench
{
class Program
{
// Iterative Fibonacci
static long FibonacciIterative(int n)
{
if (n <= 1) return n;
long a = 0, b = 1;
for (int i = 2; i <= n; i++)
{
long temp = a + b;
a = b;
b = temp;
}
return b;
}
// Recursive Fibonacci
static long FibonacciRecursive(int n)
{
if (n <= 1) return n;
return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2);
}
static void Main()
{
Console.Write("Enter n for Fibonacci: ");
if (int.TryParse(Console.ReadLine(), out int n) && n >= 0)
{
Console.WriteLine($"Iterative Fibonacci({n}): {FibonacciIterative(n)}");
Console.WriteLine($"Recursive Fibonacci({n}): {FibonacciRecursive(n)}");
}
else
{
Console.WriteLine("Invalid input!");
}
}
}
}Real-World Use: Modeling financial growth, stock trends, or recursive processes in simulations.
Pros:
Iterative: Fast (O(n)), low memory usage.
Recursive: Simple, elegant code.
Cons:
Iterative: Less intuitive for beginners.
Recursive: O(2^n) complexity, stack overflow for large n.
Best Practices:
Use iterative for performance in production.
Cache results (memoization) for recursive if needed.
Validate input to prevent negative numbers.
Alternatives:
Memoized recursive Fibonacci.
Dynamic programming for optimized recursion.
2. Prime Numbers Check
Checks if a number is prime (divisible only by 1 and itself).
Example: Prime Validator
using System;
namespace AlgorithmWorkbench
{
class Program
{
static bool IsPrime(int number)
{
if (number <= 1) return false;
if (number == 2) return true;
if (number % 2 == 0) return false;
for (int i = 3; i <= Math.Sqrt(number); i += 2)
{
if (number % i == 0) return false;
}
return true;
}
static void Main()
{
Console.Write("Enter a number to check prime: ");
if (int.TryParse(Console.ReadLine(), out int num))
{
Console.WriteLine($"{num} is {(IsPrime(num) ? "prime" : "not prime")}.");
}
else
{
Console.WriteLine("Invalid input!");
}
}
}
}Real-World Use: Cryptography, hash functions, or product ID validation.
Pros:
Efficient with square root optimization (O(√n)).
Simple to implement.
Cons:
Slow for very large numbers without advanced algorithms.
Best Practices:
Optimize by checking only up to square root.
Skip even numbers after checking 2.
Alternatives:
Sieve of Eratosthenes for multiple primes.
Probabilistic primality tests for large numbers.
3. Factorial Calculation
Calculates the product of all positive integers up to n (e.g., 5! = 5 × 4 × 3 × 2 × 1 = 120).
Example: Factorial Calculator
using System;
namespace AlgorithmWorkbench
{
class Program
{
static long Factorial(int n)
{
if (n < 0) throw new ArgumentException("Negative input not allowed.");
if (n <= 1) return 1;
long result = 1;
for (int i = 2; i <= n; i++)
result *= i;
return result;
}
static void Main()
{
Console.Write("Enter n for factorial: ");
if (int.TryParse(Console.ReadLine(), out int n))
{
try
{
Console.WriteLine($"Factorial({n}): {Factorial(n)}");
}
catch (ArgumentException ex)
{
Console.WriteLine($"Error: {ex.Message}");
}
}
else
{
Console.WriteLine("Invalid input!");
}
}
}
}Real-World Use: Calculating permutations in scheduling or analytics.
Pros:
Simple iterative implementation.
O(n) time complexity.
Cons:
Overflow for large n (use BigInteger for large numbers).
Recursive version is less efficient.
Best Practices:
Use iterative approach for performance.
Handle overflow with checked or BigInteger.
Validate input for negative numbers.
Alternatives:
Recursive factorial.
BigInteger for large factorials.
4. Palindrome Check
Checks if a string or number reads the same forwards and backwards (e.g., "racecar").
Example: Palindrome Validator
using System;
namespace AlgorithmWorkbench
{
class Program
{
static bool IsPalindrome(string input)
{
input = input.ToLower().Replace(" ", "");
int left = 0, right = input.Length - 1;
while (left < right)
{
if (input[left] != input[right]) return false;
left++;
right--;
}
return true;
}
static void Main()
{
Console.Write("Enter a string to check palindrome: ");
string? input = Console.ReadLine();
if (input != null)
{
Console.WriteLine($"{input} is {(IsPalindrome(input) ? "a palindrome" : "not a palindrome")}.");
}
else
{
Console.WriteLine("Invalid input!");
}
}
}
}Real-World Use: Validating symmetric data like product codes or user IDs.
Pros:
O(n) time complexity, O(1) space.
Simple two-pointer approach.
Cons:
Case sensitivity and spaces require preprocessing.
Best Practices:
Normalize input (e.g., lowercase, remove spaces).
Use two pointers for efficiency.
Alternatives:
Reverse string comparison (O(n) space).
Regular expressions for complex patterns.
5. Armstrong Number
Checks if a number equals the sum of its digits raised to the power of the number of digits (e.g., 153 = 1³ + 5³ + 3³).
Example: Armstrong Number Checker
using System;
namespace AlgorithmWorkbench
{
class Program
{
static bool IsArmstrong(int number)
{
int original = number, sum = 0, digits = (int)Math.Floor(Math.Log10(number) + 1);
while (number > 0)
{
int digit = number % 10;
sum += (int)Math.Pow(digit, digits);
number /= 10;
}
return sum == original;
}
static void Main()
{
Console.Write("Enter a number to check Armstrong: ");
if (int.TryParse(Console.ReadLine(), out int num) && num >= 0)
{
Console.WriteLine($"{num} is {(IsArmstrong(num) ? "an Armstrong number" : "not an Armstrong number")}.");
}
else
{
Console.WriteLine("Invalid input!");
}
}
}
}Real-World Use: Validating checksums or generating special codes.
Pros:
Simple mathematical logic.
O(log n) time complexity.
Cons:
Limited practical use.
Overflow for large numbers.
Best Practices:
Use Math.Pow for clarity, optimize for large numbers if needed.
Validate input for non-negative numbers.
Alternatives:
String-based digit processing.
Precomputed lookup tables.
6. Reverse a Number / String
Reverses the digits of a number or characters of a string.
Example: Reverse Utility
using System;
using System.Text;
namespace AlgorithmWorkbench
{
class Program
{
static int ReverseNumber(int number)
{
int result = 0;
while (number > 0)
{
result = result * 10 + number % 10;
number /= 10;
}
return result;
}
static string ReverseString(string input)
{
char[] chars = input.ToCharArray();
Array.Reverse(chars);
return new string(chars);
}
static void Main()
{
Console.Write("Enter a number to reverse: ");
if (int.TryParse(Console.ReadLine(), out int num) && num >= 0)
{
Console.WriteLine($"Reversed number: {ReverseNumber(num)}");
}
Console.Write("Enter a string to reverse: ");
string? input = Console.ReadLine();
if (input != null)
{
Console.WriteLine($"Reversed string: {ReverseString(input)}");
}
}
}
}Real-World Use: Formatting data or validating reversed inputs in forms.
Pros:
Simple and efficient (O(n) for strings, O(log n) for numbers).
Built-in methods like Array.Reverse simplify string reversal.
Cons:
Number reversal may overflow.
String reversal requires memory allocation.
Best Practices:
Use Array.Reverse or LINQ for strings.
Check for overflow in number reversal.
Alternatives:
LINQ Reverse() for strings.
StringBuilder for efficient string manipulation.
7. GCD and LCM
GCD (Greatest Common Divisor) finds the largest number dividing two numbers. LCM (Least Common Multiple) uses GCD: LCM(a, b) = |a × b| / GCD(a, b).
Example: GCD and LCM Calculator
using System;
namespace AlgorithmWorkbench
{
class Program
{
static int GCD(int a, int b)
{
while (b != 0)
{
int temp = b;
b = a % b;
a = temp;
}
return a;
}
static int LCM(int a, int b)
{
return Math.Abs(a * b) / GCD(a, b);
}
static void Main()
{
Console.Write("Enter two numbers for GCD/LCM: ");
string[] inputs = Console.ReadLine()?.Split() ?? new string[0];
if (inputs.Length == 2 && int.TryParse(inputs[0], out int a) && int.TryParse(inputs[1], out int b))
{
Console.WriteLine($"GCD({a}, {b}): {GCD(a, b)}");
Console.WriteLine($"LCM({a}, {b}): {LCM(a, b)}");
}
else
{
Console.WriteLine("Invalid input!");
}
}
}
}Real-World Use: Scheduling tasks with different intervals or simplifying fractions.
Pros:
Euclidean algorithm is efficient (O(log min(a, b))).
LCM derived easily from GCD.
Cons:
Requires careful handling of negative numbers.
Best Practices:
Use Euclidean algorithm for GCD.
Handle edge cases (e.g., zero inputs).
Alternatives:
Recursive GCD.
Prime factorization (slower).
8. Binary Search
Searches a sorted array by repeatedly dividing the search interval in half (O(log n)).
Example: Product ID Search
using System;
namespace AlgorithmWorkbench
{
class Program
{
static int BinarySearch(int[] arr, int target)
{
int left = 0, right = arr.Length - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
static void Main()
{
int[] productIds = { 101, 203, 305, 407, 509 };
Console.Write("Enter product ID to search: ");
if (int.TryParse(Console.ReadLine(), out int id))
{
int index = BinarySearch(productIds, id);
Console.WriteLine(index >= 0 ? $"Found at index {index}" : "Not found");
}
}
}
}Real-World Use: Searching product catalogs or sorted databases.
Pros:
O(log n) time complexity.
Efficient for large sorted datasets.
Cons:
Requires sorted data.
Not suitable for unsorted or dynamic data.
Best Practices:
Ensure array is sorted before searching.
Use left + (right - left) / 2 to avoid overflow.
Alternatives:
Linear search for unsorted data.
Hash tables for O(1) lookups.
9. Linear Search
Searches an array sequentially (O(n)).
Example: Customer Name Search
using System;
namespace AlgorithmWorkbench
{
class Program
{
static int LinearSearch(string[] arr, string target)
{
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] == target) return i;
}
return -1;
}
static void Main()
{
string[] customers = { "Alice", "Bob", "Charlie" };
Console.Write("Enter customer name to search: ");
string? name = Console.ReadLine();
if (name != null)
{
int index = LinearSearch(customers, name);
Console.WriteLine(index >= 0 ? $"Found at index {index}" : "Not found");
}
}
}
}Real-World Use: Searching unsorted lists like customer records.
Pros:
Works on unsorted data.
Simple to implement.
Cons:
O(n) time complexity, slow for large datasets.
Best Practices:
Use for small or unsorted datasets.
Consider sorting for repeated searches.
Alternatives:
Binary search for sorted data.
HashSet for O(1) lookups.
10. Bubble Sort
Sorts an array by repeatedly swapping adjacent elements if they are in the wrong order (O(n²)).
Example: Sort Sales Data
using System;
namespace AlgorithmWorkbench
{
class Program
{
static void BubbleSort(int[] arr)
{
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]);
}
}
}
}
static void Main()
{
int[] sales = { 500, 200, 800, 100 };
BubbleSort(sales);
Console.WriteLine("Sorted sales: " + string.Join(", ", sales));
}
}
}Real-World Use: Sorting small datasets like sales reports.
Pros:
Simple to understand and implement.
Stable sorting algorithm.
Cons:
O(n²) time complexity, inefficient for large data.
Best Practices:
Use for small datasets or educational purposes.
Optimize with early exit if no swaps occur.
Alternatives:
Quick sort or merge sort for better performance.
Array.Sort for built-in efficiency.
11. Insertion Sort
Sorts an array by inserting each element into its correct position (O(n²)).
Example: Sort Employee IDs
using System;
namespace AlgorithmWorkbench
{
class Program
{
static void InsertionSort(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
static void Main()
{
int[] employeeIds = { 104, 102, 103, 101 };
InsertionSort(employeeIds);
Console.WriteLine("Sorted IDs: " + string.Join(", ", employeeIds));
}
}
}Real-World Use: Sorting small lists like employee records.
Pros:
Efficient for small or nearly sorted datasets.
Stable and adaptive.
Cons:
O(n²) time complexity.
Best Practices:
Use for small or partially sorted data.
Optimize by reducing shifts.
Alternatives:
Shell sort for improved performance.
Built-in Array.Sort.
12. Selection Sort
Sorts an array by repeatedly selecting the smallest element and placing it at the start (O(n²)).
Example: Sort Prices
using System;
namespace AlgorithmWorkbench
{
class Program
{
static void SelectionSort(double[] arr)
{
for (int i = 0; i < arr.Length - 1; i++)
{
int minIndex = i;
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[j] < arr[minIndex])
minIndex = j;
}
(arr[i], arr[minIndex]) = (arr[minIndex], arr[i]);
}
}
static void Main()
{
double[] prices = { 99.99, 49.99, 149.99, 29.99 };
SelectionSort(prices);
Console.WriteLine("Sorted prices: " + string.Join(", ", prices));
}
}
}Real-World Use: Sorting product prices in a catalog.
Pros:
Simple and predictable.
Minimal swaps (O(n)).
Cons:
O(n²) time complexity.
Not stable.
Best Practices:
Use for small datasets with expensive swaps.
Avoid for large or dynamic data.
Alternatives:
Insertion sort for stability.
Array.Sort for efficiency.
13. Merge Sort
Divides an array into halves, recursively sorts them, and merges them (O(n log n)).
Example: Sort Orders
using System;
namespace AlgorithmWorkbench
{
class Program
{
static void MergeSort(int[] arr, int left, int right)
{
if (left < right)
{
int mid = left + (right - left) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
}
}
static void Merge(int[] arr, int left, int mid, int right)
{
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right)
{
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
Array.Copy(temp, 0, arr, left, temp.Length);
}
static void Main()
{
int[] orders = { 500, 200, 800, 100 };
MergeSort(orders, 0, orders.Length - 1);
Console.WriteLine("Sorted orders: " + string.Join(", ", orders));
}
}
}Real-World Use: Sorting large datasets like order histories.
Pros:
O(n log n) time complexity.
Stable sorting.
Cons:
O(n) space complexity.
Recursive overhead.
Best Practices:
Use for large datasets requiring stability.
Optimize by reusing arrays if possible.
Alternatives:
Quick sort for in-place sorting.
Array.Sort for built-in efficiency.
14. Quick Sort
Sorts an array by selecting a pivot and partitioning elements around it (O(n log n) average).
Example: Sort Inventory
using System;
namespace AlgorithmWorkbench
{
class Program
{
static void QuickSort(int[] arr, int low, int high)
{
if (low < high)
{
int pi = Partition(arr, low, high);
QuickSort(arr, low, pi - 1);
QuickSort(arr, pi + 1, high);
}
}
static int Partition(int[] arr, int low, int high)
{
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++)
{
if (arr[j] <= pivot)
{
i++;
(arr[i], arr[j]) = (arr[j], arr[i]);
}
}
(arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
return i + 1;
}
static void Main()
{
int[] inventory = { 50, 20, 80, 10 };
QuickSort(inventory, 0, inventory.Length - 1);
Console.WriteLine("Sorted inventory: " + string.Join(", ", inventory));
}
}
}Real-World Use: Sorting inventory or customer lists.
Pros:
O(n log n) average time complexity.
In-place sorting (O(log n) space).
Cons:
O(n²) worst-case for sorted arrays.
Not stable.
Best Practices:
Choose random pivot to avoid worst-case.
Use for large datasets with random data.
Alternatives:
Merge sort for stability.
Array.Sort (uses QuickSort internally).
15. Heap Sort
Sorts an array using a binary heap (O(n log n)).
Example: Sort Sales
using System;
namespace AlgorithmWorkbench
{
class Program
{
static void HeapSort(int[] arr)
{
int n = arr.Length;
for (int i = n / 2 - 1; i >= 0; i--)
Heapify(arr, n, i);
for (int i = n - 1; i > 0; i--)
{
(arr[0], arr[i]) = (arr[i], arr[0]);
Heapify(arr, i, 0);
}
}
static void Heapify(int[] arr, int n, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i)
{
(arr[i], arr[largest]) = (arr[largest], arr[i]);
Heapify(arr, n, largest);
}
}
static void Main()
{
int[] sales = { 500, 200, 800, 100 };
HeapSort(sales);
Console.WriteLine("Sorted sales: " + string.Join(", ", sales));
}
}
}Real-World Use: Priority-based scheduling or sorting large datasets.
Pros:
Guaranteed O(n log n) time complexity.
In-place sorting.
Cons:
Not stable.
Slower than QuickSort in practice.
Best Practices:
Use for guaranteed performance.
Implement max-heap for ascending order.
Alternatives:
Quick sort for better average performance.
Array.Sort for simplicity.
16. Count Sort
Sorts an array by counting occurrences of each value (O(n + k), where k is the range of values).
Example: Sort Ratings
using System;
namespace AlgorithmWorkbench
{
class Program
{
static void CountSort(int[] arr, int max)
{
int[] count = new int[max + 1];
int[] output = new int[arr.Length];
foreach (int num in arr) count[num]++;
for (int i = 1; i <= max; i++) count[i] += count[i - 1];
for (int i = arr.Length - 1; i >= 0; i--)
{
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
Array.Copy(output, arr, arr.Length);
}
static void Main()
{
int[] ratings = { 4, 2, 5, 1, 3 };
CountSort(ratings, 5);
Console.WriteLine("Sorted ratings: " + string.Join(", ", ratings));
}
}
}Real-World Use: Sorting ratings or discrete scores.
Pros:
O(n + k) time complexity.
Stable sorting.
Cons:
Requires known range of values (k).
High memory for large k.
Best Practices:
Use for small, discrete ranges.
Optimize count array size.
Alternatives:
Radix sort for larger ranges.
Array.Sort for general use.
17. String Anagram Check
Checks if two strings are anagrams (same characters, different order).
Example: Anagram Validator
using System;
namespace AlgorithmWorkbench
{
class Program
{
static bool AreAnagrams(string s1, string s2)
{
if (s1.Length != s2.Length) return false;
int[] count = new int[26];
for (int i = 0; i < s1.Length; i++)
{
count[s1[i] - 'a']++;
count[s2[i] - 'a']--;
}
return count.All(c => c == 0);
}
static void Main()
{
Console.Write("Enter two strings to check anagrams: ");
string[] inputs = Console.ReadLine()?.ToLower().Split() ?? new string[0];
if (inputs.Length == 2)
{
Console.WriteLine($"{inputs[0]} and {inputs[1]} are {(AreAnagrams(inputs[0], inputs[1]) ? "anagrams" : "not anagrams")}.");
}
else
{
Console.WriteLine("Invalid input!");
}
}
}
}Real-World Use: Validating product codes or matching strings in search.
Pros:
O(n) time complexity with counting.
Simple for fixed alphabets.
Cons:
Limited to specific character sets.
Memory overhead for large alphabets.
Best Practices:
Normalize input (lowercase, remove spaces).
Use counting array for efficiency.
Alternatives:
Sort and compare (O(n log n)).
Dictionary-based counting.
18. Balanced Parentheses Check
Checks if a string of parentheses is balanced (e.g., "({[]})" is balanced).
Example: Parentheses Validator
using System;
using System.Collections.Generic;
namespace AlgorithmWorkbench
{
class Program
{
static bool IsBalanced(string s)
{
Stack<char> stack = new Stack<char>();
foreach (char c in s)
{
if (c == '(' || c == '{' || c == '[')
stack.Push(c);
else if (c == ')' && stack.Count > 0 && stack.Pop() != '(') return false;
else if (c == '}' && stack.Count > 0 && stack.Pop() != '{') return false;
else if (c == ']' && stack.Count > 0 && stack.Pop() != '[') return false;
}
return stack.Count == 0;
}
static void Main()
{
Console.Write("Enter parentheses string: ");
string? input = Console.ReadLine();
if (input != null)
{
Console.WriteLine($"{input} is {(IsBalanced(input) ? "balanced" : "not balanced")}.");
}
}
}
}Real-World Use: Validating code syntax or JSON structures.
Pros:
O(n) time complexity.
Simple stack-based solution.
Cons:
Limited to parentheses-like structures.
Best Practices:
Use a stack for matching pairs.
Validate input for valid characters.
Alternatives:
Counter-based for simple cases.
Recursive parsing for complex grammars.
19. Matrix Multiplication
Multiplies two matrices (result[i,j] = sum of row i × column j).
Example: Matrix Multiplier
using System;
namespace AlgorithmWorkbench
{
class Program
{
static int[,] MultiplyMatrices(int[,] a, int[,] b)
{
int rowsA = a.GetLength(0), colsA = a.GetLength(1);
int colsB = b.GetLength(1);
int[,] result = new int[rowsA, colsB];
for (int i = 0; i < rowsA; i++)
{
for (int j = 0; j < colsB; j++)
{
for (int k = 0; k < colsA; k++)
{
result[i, j] += a[i, k] * b[k, j];
}
}
}
return result;
}
static void Main()
{
int[,] a = { { 1, 2 }, { 3, 4 } };
int[,] b = { { 5, 6 }, { 7, 8 } };
int[,] result = MultiplyMatrices(a, b);
Console.WriteLine("Result Matrix:");
for (int i = 0; i < result.GetLength(0); i++)
{
for (int j = 0; j < result.GetLength(1); j++)
{
Console.Write(result[i, j] + " ");
}
Console.WriteLine();
}
}
}
}Real-World Use: Image processing or financial modeling.
Pros:
O(n³) for standard algorithm.
Well-defined for matrix operations.
Cons:
High time complexity.
Requires compatible matrix dimensions.
Best Practices:
Validate matrix dimensions.
Use libraries for optimized implementations.
Alternatives:
Strassen’s algorithm for faster multiplication.
Math libraries (e.g., MathNet.Numerics).
20. Tower of Hanoi
Solves the recursive puzzle of moving n disks between three poles.
Example: Tower of Hanoi Solver
using System;
namespace AlgorithmWorkbench
{
class Program
{
static void TowerOfHanoi(int n, char source, char auxiliary, char destination)
{
if (n == 1)
{
Console.WriteLine($"Move disk 1 from {source} to {destination}");
return;
}
TowerOfHanoi(n - 1, source, destination, auxiliary);
Console.WriteLine($"Move disk {n} from {source} to {destination}");
TowerOfHanoi(n - 1, auxiliary, source, destination);
}
static void Main()
{
Console.Write("Enter number of disks: ");
if (int.TryParse(Console.ReadLine(), out int n) && n > 0)
{
TowerOfHanoi(n, 'A', 'B', 'C');
}
else
{
Console.WriteLine("Invalid input!");
}
}
}
}Real-World Use: Teaching recursion or modeling stacked processes.
Pros:
Elegant recursive solution.
O(2^n) moves are optimal.
Cons:
Exponential time complexity.
Limited practical use.
Best Practices:
Use recursion for clarity.
Validate input for positive numbers.
Alternatives:
Iterative solutions (complex).
Simulation-based approaches.
21. Nth Largest/Smallest Element in Array
Finds the nth largest or smallest element in an array.
Example: Nth Largest Finder
using System;
using System.Linq;
namespace AlgorithmWorkbench
{
class Program
{
static int FindNthLargest(int[] arr, int n)
{
return arr.OrderByDescending(x => x).ElementAt(n - 1);
}
static void Main()
{
int[] numbers = { 50, 20, 80, 10, 30 };
Console.Write("Enter n for nth largest: ");
if (int.TryParse(Console.ReadLine(), out int n) && n > 0 && n <= numbers.Length)
{
Console.WriteLine($"Nth largest: {FindNthLargest(numbers, n)}");
}
else
{
Console.WriteLine("Invalid input!");
}
}
}
}Real-World Use: Finding top sales or lowest prices.
Pros:
Simple with LINQ (O(n log n)).
Flexible for any n.
Cons:
Sorting-based approach is slow for large data.
Best Practices:
Use LINQ for simplicity in small datasets.
Consider QuickSelect for O(n) average time.
Alternatives:
QuickSelect algorithm.
Heap-based selection.
22. Dynamic Programming Basics (Knapsack, Coin Change)
Dynamic programming solves problems by breaking them into overlapping subproblems.
Example: 0/1 Knapsack
using System;
namespace AlgorithmWorkbench
{
class Program
{
static int Knapsack(int capacity, int[] weights, int[] values, int n)
{
int[,] dp = new int[n + 1, capacity + 1];
for (int i = 0; i <= n; i++)
{
for (int w = 0; w <= capacity; w++)
{
if (i == 0 || w == 0)
dp[i, w] = 0;
else if (weights[i - 1] <= w)
dp[i, w] = Math.Max(values[i - 1] + dp[i - 1, w - weights[i - 1]], dp[i - 1, w]);
else
dp[i, w] = dp[i - 1, w];
}
}
return dp[n, capacity];
}
static void Main()
{
int[] weights = { 10, 20, 30 };
int[] values = { 60, 100, 120 };
int capacity = 50;
Console.WriteLine($"Max value in knapsack: {Knapsack(capacity, weights, values, weights.Length)}");
}
}
}Example: Coin Change
using System;
namespace AlgorithmWorkbench
{
class Program
{
static int CoinChange(int[] coins, int amount)
{
int[] dp = new int[amount + 1];
Array.Fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++)
{
foreach (int coin in coins)
{
if (coin <= i)
dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
static void Main()
{
int[] coins = { 1, 5, 10, 25 };
Console.Write("Enter amount for coin change: ");
if (int.TryParse(Console.ReadLine(), out int amount))
{
int result = CoinChange(coins, amount);
Console.WriteLine(result >= 0 ? $"Minimum coins: {result}" : "No solution");
}
}
}
}Real-World Use: Optimizing inventory (Knapsack) or cash register change (Coin Change).
Pros:
Efficient for overlapping subproblems.
O(n × capacity) for Knapsack, O(n × amount) for Coin Change.
Cons:
High space complexity (O(n × capacity)).
Complex to design for beginners.
Best Practices:
Use bottom-up DP for performance.
Optimize space with rolling arrays if possible.
Validate inputs for edge cases.
Alternatives:
Greedy algorithms (may not be optimal).
Recursive solutions with memoization.
Interactive Example: Algorithm Workbench
Let’s build a console-based algorithm workbench to test these algorithms interactively.
// File: Models/DataItem.cs
namespace AlgorithmWorkbench.Models
{
public record DataItem(int Id, string Name, double Value);
}
// File: Services/AlgorithmService.cs
namespace AlgorithmWorkbench.Services
{
using System;
using System.Collections.Generic;
using System.Linq;
public class AlgorithmService
{
public long Fibonacci(int n) => n <= 1 ? n : Fibonacci(n - 1) + Fibonacci(n - 2);
public bool IsPrime(int n)
{
if (n <= 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i <= Math.Sqrt(n); i += 2)
if (n % i == 0) return false;
return true;
}
public bool IsPalindrome(string s) => s.ToLower().Replace(" ", "").SequenceEqual(s.ToLower().Replace(" ", "").Reverse());
public int[] QuickSort(int[] arr)
{
var copy = arr.ToArray();
Array.Sort(copy); // Simplified for demo
return copy;
}
public int BinarySearch(int[] arr, int target)
{
int left = 0, right = arr.Length - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
}
}
// File: Program.cs
using System;
using AlgorithmWorkbench.Services;
Console.WriteLine("Algorithm Workbench");
var service = new AlgorithmWorkbench.Services.AlgorithmService();
while (true)
{
Console.WriteLine("\n1. Fibonacci");
Console.WriteLine("2. Prime Check");
Console.WriteLine("3. Palindrome Check");
Console.WriteLine("4. Quick Sort");
Console.WriteLine("5. Binary Search");
Console.WriteLine("6. Exit");
Console.Write("Choose an option: ");
string? choice = Console.ReadLine();
if (choice == "6") break;
switch (choice)
{
case "1":
Console.Write("Enter n for Fibonacci: ");
if (int.TryParse(Console.ReadLine(), out int n) && n >= 0)
Console.WriteLine($"Fibonacci({n}): {service.Fibonacci(n)}");
else
Console.WriteLine("Invalid input!");
break;
case "2":
Console.Write("Enter number for prime check: ");
if (int.TryParse(Console.ReadLine(), out int num))
Console.WriteLine($"{num} is {(service.IsPrime(num) ? "prime" : "not prime")}.");
else
Console.WriteLine("Invalid input!");
break;
case "3":
Console.Write("Enter string for palindrome check: ");
string? input = Console.ReadLine();
if (input != null)
Console.WriteLine($"{input} is {(service.IsPalindrome(input) ? "a palindrome" : "not a palindrome")}.");
else
Console.WriteLine("Invalid input!");
break;
case "4":
Console.Write("Enter numbers to sort (space-separated): ");
string[] nums = Console.ReadLine()?.Split() ?? new string[0];
int[] arr = Array.ConvertAll(nums, int.Parse);
Console.WriteLine("Sorted: " + string.Join(", ", service.QuickSort(arr)));
break;
case "5":
Console.Write("Enter sorted numbers (space-separated): ");
nums = Console.ReadLine()?.Split() ?? new string[0];
arr = Array.ConvertAll(nums, int.Parse);
Console.Write("Enter number to search: ");
if (int.TryParse(Console.ReadLine(), out int target))
{
int index = service.BinarySearch(arr, target);
Console.WriteLine(index >= 0 ? $"Found at index {index}" : "Not found");
}
else
Console.WriteLine("Invalid input!");
break;
default:
Console.WriteLine("Invalid option!");
break;
}
}How It Works:
Implements a subset of algorithms (Fibonacci, Prime, Palindrome, QuickSort, BinarySearch).
Uses top-level statements for simplicity.
Modular design with a service class for algorithm logic.
Interactive console interface for testing.
Why It’s Useful: Mimics algorithm testing environments for coding interviews or data analysis tools.
Setup: Create a new Console App in Visual Studio or run dotnet new console -langVersion 12. Organize files as shown. Requires .NET 6+.
Best Standards for Module 10
Fibonacci: Use iterative for production; recursive for learning.
Prime Check: Optimize with square root and even number checks.
Factorial: Use iterative; handle overflow with BigInteger.
Palindrome: Normalize input; use two pointers for efficiency.
Armstrong: Validate inputs; optimize digit extraction.
Reverse: Use built-in methods for strings; check number overflow.
GCD/LCM: Use Euclidean algorithm; handle edge cases.
Searches: Use binary for sorted data, linear for unsorted.
Sorting: Use Array.Sort for production; understand algorithms for interviews.
Dynamic Programming: Use bottom-up DP; optimize space with rolling arrays.
Conclusion
You’ve just mastered algorithms and problem-solving in C# with over 20 hands-on challenges! By learning Fibonacci, prime checks, sorting, searching, recursion, and dynamic programming, you’re ready to tackle coding interviews and optimize real-world applications. The algorithm workbench demonstrates how these techniques apply to practical scenarios.
0 comments:
Post a Comment