Algorithms In .NET

Complexity: A Guided Tour by Melanie Mitchell My rating: 4 of 5 stars I enjoy reading in systems and complexity, and this was a nice addition to my shelf, with a slightly different take than other books. I found a few areas in the first half a bit tedious, overly long, repetitive, and not illuminating, but generally, it's a great overview of seminal work and very thought-provoking. The first half overlaps but nicely differs from other books I've read, covering things like chaos and information processing, and the latter half of the book I found more engaging, focused on models, computation, network science, and scaling. As mentioned, although I found the first half a bit of a slog at times, the second half was very engaging. View all my reviews

Responding to a question on HashNode, Developers who practise algorithms are better at software development than people who just do development. Is it true? , I wrote the following: My feeling is that algorithms help make one a better programmer, but that is likely true of many coding concepts. I did not have algorithms as an undergraduate, so my knowledge is acquired through reading and practice, but after reading and applying Algorithm's in a Nutshell, I felt the quality of my work improved. That said, my development work increased more after understanding Design Patterns, or after consuming books on database design.  Since many types of knowledge improve developing and architecting abilities, one has to consider how it helps and to what degree. Algorithms are coding-in-the-small, often narrowly focused solutions, but which can have a great impact at scale. For many applications, a focus on algorithms would be overkill as data sets and requirements do not require it. In this

An example of a hash-based search, although using dictionaries.  The code is designed to manage lists of Person objects, with unique Id's as the key value, with a rudimentary hash function to assign to various lists. Salient Characteristic(s) Useful for managing large unsorted lists Divides the items into smaller hash-based buckets (divide and conquer) Generally excellent performance Sensitive to the choice of hash function and data structures chosen Note The Id key is not rigorous enough to guarantee uniqueness, and a better key might need to be selected, e.g., SSN, to prevent the same person being entered twice. Code using System; using System.Collections.Generic; namespace Algorithms {     //Example object to add and find in Hash Search example     public class Person     {         private int _Id;         public int Id          {             get { return _Id; }             set { _Id = value; }          }                  private string _LastName;

This is the basic divide-and-conquer algorithm, requiring a sorted array. This repeatedly halves the remaining positions to search, until the value is found, or it determines that the value cannot be found. As mentioned, it requires a presorted array, or if unsorted, requires it is sorted. The benefits accrue in instances where the array is sorted once, but searched many times. On a hypothetical array of 100 items, a linear search has an average performances of O(n/2), or a search of half the positions, 50, to find the item. By comparison, the average performance of Binary Search is O(log n), which for 100 items translates into 4.6, a radically reduced number of iterations, but with greater requirements for logic and memory. Done in both C#, as an iterative while loop, and F#, as a recursion. C# using System; namespace Algorithms { class BinarySearch { public BinarySearch() { } public int Search(int num, int[] arrayToSearch)

Because Linear Search is so simple, I thought of doing something a bit different, so this post includes code in F# as well as C#. F# //linear search, but with error handling for 'value not found' let LinearSearch num arr =      try         arr |> List.findIndex (fun x -> x = num)     with         | :? System.Collections.Generic.KeyNotFoundException -> -1 //create array to use let baseList = [3; 1; 7; 2; 9; 4; 1; 12; 25; 10; 11; 19; 22] //two examples, one that works, and one that returns an error of -1 let resultFound = LinearSearch 12 baseList let resultMissing = LinearSearch 23 baseList C# Code using System; namespace Algorithms {     class LinearSearch     {         public LinearSearch()         {         }                  public int Search(int num, int[] arrayToSearch)         {             //creates array             //int[] arrayToSort = { 11, 7, 22, 2, 33, 3, 17, 44, 4, 55, 5, 66, 6, 1, 77 };             int posFound = -1;

The following uses the divide-and-conquer method of resolution, by dividing the problem into smaller arrays, sorting each smaller array, then reinserting the subarrays back into the original array.  This is not a pure solution, in that it uses the .NET List, rather than a linked list struct. using System; using System.Collections; using System.Collections.Generic; namespace Algorithms {     class BucketSort     {         public int[] Sort()         {                //creates arbitrary array             int[] arrayToSort = { 11, 7, 22, 2, 33, 3, 17, 44, 4, 55, 5, 66, 6, 1, 77 };             //create bucket using hash, x/10             List<int>[] bucketList = CreateHashedArray(arrayToSort, 10);             //sort the bucket list back into the original array             ReorderList(bucketList, arrayToSort);             return arrayToSort;         }         private int hashFunction(int num, int buckets)         {             return num / buckets;         }