Advanced Topics in OODSA

Welcome to the capstone lesson

You have moved from Introduction to OODSA through algorithmic thinking, data structures, sorting/searching, dynamic programming, graph algorithms, and greedy algorithms.

Now we are ready for the final shift: advanced OODSA is not a brand-new bag of tricks. It is the ability to combine the tools you already know into designs that are:

• correct under pressure
• adaptable when requirements change
• measurable in performance
• readable by other programmers

In this lesson, we will look at how experienced C# developers connect algorithms, objects, contracts, and tradeoffs into production-quality thinking.

The advanced move

Earlier lessons focused on individual tools:

• Data Structures taught you that shape drives behavior.
• Sorting and Searching Algorithms taught you that order creates leverage.
• Dynamic Programming taught you to reuse repeated subproblems.
• Graph Algorithms taught you to reason about reachability and dependency.
• Greedy Algorithms taught you to make local choices only when they are safe.

Advanced OODSA begins when these stop being separate topics.

A real system might use:

object model -> data structure -> algorithm -> invariant -> performance check

For example, a route planner may model Location objects, store connections in an adjacency list, use a priority queue, rely on a shortest-path invariant, and expose the result through a clean service class.

The algorithm is only one part of the design.

Beyond one-operation cost

By now, you can compare common Big-O costs. Advanced thinking asks a sharper question:

What happens across a long sequence of operations?

That is where amortized analysis appears. A single operation may occasionally be expensive, but the average cost over many operations can still be excellent.

A classic example is a dynamic array. Most appends are cheap. Occasionally, the internal array must resize and copy existing items. But because capacity usually grows geometrically, those expensive moments are rare.

This matters in C# because types like List<T> feel simple, but they are powered by this idea.

```csharp
using System;

class TinyDynamicArray
{
    private int[] items = new int[2];
    public int Count { get; private set; }
    public int Capacity => items.Length;
    public int ResizeCount { get; private set; }

    public void Add(int value)
    {
        if (Count == items.Length)
        {
            int[] bigger = new int[items.Length * 2];
            Array.Copy(items, bigger, items.Length);
            items = bigger;
            ResizeCount++;
            Console.WriteLine($"Resize happened. New capacity: {Capacity}");
        }

        items[Count] = value;
        Count++;
    }
}

class Program
{
    static void Main()
    {
        var array = new TinyDynamicArray();

        for (int i = 1; i <= 10; i++)
        {
            array.Add(i);
            Console.WriteLine($"Added {i}, Count={array.Count}, Capacity={array.Capacity}");
        }

        Console.WriteLine($"Total resizes: {array.ResizeCount}");
    }
}
```

A dynamic array append can occasionally require copying many existing elements. Why can appending still be described as amortized O(1)?

Object-oriented design meets algorithm choice

In beginner code, algorithm choice often appears as a pile of if statements.

In stronger OODSA design, the choice becomes a contract.

That means the object model says:

“I need something that can compare or prioritize these items.”

The specific algorithmic rule can be swapped without rewriting the surrounding system. This is useful when requirements change, such as sorting support tickets by urgency today and by age tomorrow.

```csharp
using System;
using System.Collections.Generic;

record Ticket(string Title, int Urgency, int AgeInHours);

class UrgencyFirst : IComparer<Ticket>
{
    public int Compare(Ticket? a, Ticket? b)
    {
        return b!.Urgency.CompareTo(a!.Urgency); // higher urgency first
    }
}

class OldestFirst : IComparer<Ticket>
{
    public int Compare(Ticket? a, Ticket? b)
    {
        return b!.AgeInHours.CompareTo(a!.AgeInHours); // older first
    }
}

class Program
{
    static void Print(string label, List<Ticket> tickets)
    {
        Console.WriteLine(label);
        foreach (var t in tickets)
            Console.WriteLine($"- {t.Title} | urgency={t.Urgency}, age={t.AgeInHours}h");
    }

    static void Main()
    {
        var tickets = new List<Ticket>
        {
            new("Login bug", 5, 2),
            new("Billing issue", 9, 1),
            new("Export request", 3, 20)
        };

        tickets.Sort(new UrgencyFirst());
        Print("Urgency-first plan:", tickets);

        tickets.Sort(new OldestFirst());
        Print("\nOldest-first plan:", tickets);
    }
}
```

True or false: In advanced OODSA, wrapping an algorithmic rule behind an interface or comparer can make the system easier to change without rewriting the whole workflow.

Not every solution needs the same promise

In earlier lessons, we cared a lot about correctness: binary search invariants, DP transitions, graph traversal rules, and greedy proof ideas.

Advanced work still cares about correctness, but it also asks what kind of promise the problem needs.

Common categories:

• Exact algorithm: finds the true optimal answer.
• Approximation algorithm: gives a result with a known quality bound.
• Heuristic: often works well, but may not guarantee optimality.
• Randomized algorithm: uses randomness to improve expected behavior or simplicity.

This is especially important in programming work where input size, latency, memory, and product needs compete.

A game AI, route suggestion, search ranking, or scheduler may prefer a fast good answer over a slow perfect answer.

A* as a synthesis example

A* search is a good final example because it combines ideas from across the course:

• from Graph Algorithms: explore neighboring states
• from Greedy Algorithms: prefer promising candidates
• from Data Structures: use a priority queue
• from Algorithmic Thinking: preserve a clear meaning for each score

A* ranks candidates with:

estimated total cost = cost so far + heuristic estimate

If the heuristic is well-behaved, A* can find an optimal path while exploring fewer states than a blind search.

```csharp
using System;
using System.Collections.Generic;

class Program
{
    static readonly int Rows = 5;
    static readonly int Cols = 5;
    static readonly HashSet<(int r, int c)> Walls = new()
    {
        (1, 1), (1, 2), (2, 2), (3, 1)
    };

    static int Heuristic((int r, int c) a, (int r, int c) b)
    {
        return Math.Abs(a.r - b.r) + Math.Abs(a.c - b.c); // Manhattan distance
    }

    static IEnumerable<(int r, int c)> Neighbors((int r, int c) cell)
    {
        int[] dr = { -1, 1, 0, 0 };
        int[] dc = { 0, 0, -1, 1 };

        for (int i = 0; i < 4; i++)
        {
            int nr = cell.r + dr[i];
            int nc = cell.c + dc[i];
            var next = (nr, nc);

            if (nr >= 0 && nr < Rows && nc >= 0 && nc < Cols && !Walls.Contains(next))
                yield return next;
        }
    }

    static void Main()
    {
        var start = (r: 0, c: 0);
        var goal = (r: 4, c: 4);

        var frontier = new PriorityQueue<(int r, int c), int>();
        var costSoFar = new Dictionary<(int r, int c), int>();
        var cameFrom = new Dictionary<(int r, int c), (int r, int c)>();

        frontier.Enqueue(start, 0);
        costSoFar[start] = 0;

        while (frontier.Count > 0)
        {
            var current = frontier.Dequeue();
            if (current == goal) break;

            foreach (var next in Neighbors(current))
            {
                int newCost = costSoFar[current] + 1;
                if (!costSoFar.ContainsKey(next) || newCost < costSoFar[next])
                {
                    costSoFar[next] = newCost;
                    int priority = newCost + Heuristic(next, goal);
                    frontier.Enqueue(next, priority);
                    cameFrom[next] = current;
                }
            }
        }

        Console.WriteLine($"Shortest path cost: {costSoFar[goal]}");
        Console.WriteLine("Path found from start to goal.");
    }
}
```

In A* search, the priority is commonly calculated as cost so far + heuristic estimate. The heuristic estimates the remaining cost from the current state to the ____.

Your OODSA checklist going forward

You have now completed the full OODSA algorithmic thinking path.

When you face a new programming problem, use this final checklist:

1. Model the domain. What are the objects, responsibilities, and boundaries?
2. Choose the shape. Which data structure makes the important operations natural?
3. State the invariant. What must remain true while the algorithm runs?
4. Pick the algorithm family. Search, sort, DP, graph traversal, greedy, heuristic, or a combination?
5. Measure tradeoffs. Time, memory, clarity, latency, and changeability all matter.
6. Hide variation behind contracts. Let interfaces, comparers, and small classes contain change.
7. Trace before trust. Even advanced designs should survive a small hand-worked example.

The big lesson: advanced programmers do not just memorize algorithms. They learn to connect models, methods, data, and proof ideas into systems that can evolve.

That is the heart of OODSA.