12 — Foundations Capstone: Integrating Computer Science

12 — Foundations Capstone

A foundations capstone is a complete argument about a computing solution, not merely a collection of source code. It should connect seven questions:

1. What problem is being solved?

2. How is the problem represented as data?

3. What procedure transforms inputs into outputs?

4. Which structures support that procedure?

5. How does resource use grow with input size?

6. How will correctness and reliability be assessed?

7. Who might benefit, be excluded, or be harmed?

A strong project makes its assumptions visible and explains why each major design choice is appropriate. The goal is a coherent system whose behavior, limitations, and consequences can be evaluated.

Takeaway: Treat the capstone as an evidence-backed design explanation, not only an implementation exercise.

Define the Problem and Its Success Criteria

Start by writing a precise problem statement. Identify the intended users, available inputs, required outputs, constraints, assumptions, limitations, and criteria for success.

For example, a community resource navigator might need to accept a user's location and a collection of resource records, then return available resources of a requested type ordered by distance. The specification should also state what happens when information is missing, outdated, invalid, or uncertain.

A useful specification distinguishes:

• Inputs: records, locations, categories, and availability information.

• Outputs: a ranked list, an empty result, or an explanatory warning.

• Constraints: for example, unavailable resources must not appear in an availability-only result.

• Success criteria: valid, invalid, empty, boundary, and uncertain cases behave as specified.

• Limitations: the data may be incomplete or out of date.

A precise specification prevents the implementation from silently changing the problem. It also gives later tests and correctness arguments something concrete to evaluate.

Takeaway: Define observable behavior before choosing a data structure or writing program logic.

Model Information Precisely

Representation is the choice of a data model that preserves the distinctions important to the problem. A resource record might contain an identifier, name, category, coordinates, availability status, and capacity. The representation should also distinguish a known zero from a value that is unknown.

Choose a structure according to the operations the system needs:

• A list or array supports sequential processing and position-based access.

• A set emphasizes membership and uniqueness.

• A dictionary or hash table supports retrieval by a key such as an identifier.

• A tree supports ordered or hierarchical relationships.

• A graph models connections such as roads, dependencies, or friendships.

• A queue processes items in first-in, first-out order.

• A stack processes the most recently added item first.

• A priority queue selects the next item according to priority, cost, or distance.

Data structures affect correctness as well as speed. If duplicate identifiers are invalid, that rule must be represented and checked. If capacity is unknown, storing unknown is safer than storing 0, because zero means no capacity while unknown means that the value has not been established.

Takeaway: Choose a representation that preserves meaning and supports the operations your algorithm must perform.

Design the Program in Layers

Separate the program into layers with clear responsibilities. A useful arrangement is:

1. An input layer reads and validates records.

2. A data layer stores and retrieves records.

3. An algorithm layer searches, filters, sorts, or optimizes.

4. An output layer formats results and explanations.

5. An evaluation layer runs tests and records limitations.

Each function should have a contract stating its accepted arguments, return value, assumptions, and reported errors. For a resource navigator, separate operations might load validated resources, filter by category and availability, calculate distance, and rank the remaining records.

Small functions are easier to test and reuse than one function that reads data, performs every calculation, prints results, and changes global state. Layering also makes it easier to replace one implementation without changing unrelated parts of the system.

Takeaway: Modular design turns a large problem into components whose behavior can be understood and tested independently.

Connect Algorithms and Data Structures

An algorithm is a systematic procedure, and data structures determine how its information is organized. Select them together rather than treating either choice as independent.

A simple filtering-and-ranking procedure can:

1. Scan every resource.

2. Keep only records in the requested category.

3. Exclude unavailable records when required.

4. Calculate the distance for each remaining record.

5. Sort the matches by increasing distance.

6. Return the ordered results.

This approach is often appropriate for a small dataset, infrequent queries, limited implementation time, or situations where transparency matters more than maximum speed. A larger or frequently queried system might justify an index, spatial structure, graph, or precomputed information, but added complexity should solve a demonstrated problem.

When two results have the same distance, specify a deterministic secondary rule, such as ordering by name or identifier. Deterministic behavior improves reproducibility and makes testing easier.

Takeaway: Begin with the simplest correct algorithm, then add specialized structures only when scale or requirements justify them.

Analyze Time and Space

Complexity analysis describes how resource use grows as the input grows. Suppose there are $n$ resource records and $m$ records remain after filtering, where $m \le n$.

For a straightforward filtering-and-ranking procedure:

• Scanning all records usually takes $O(n)$ time.

• Appending each retained record to a dynamic output list is typically $O(1)$ amortized time per append.

• Sorting $m$ retained records commonly takes $O(m \log m)$ time.

• Storing all records requires $O(n)$ space.

The total time is therefore approximately $O(n + m \log m)$. If every record matches, the worst-case time becomes $O(n \log n)$. This analysis assumes that a distance calculation takes constant time because each record contains a fixed number of coordinates. If calculating distance requires a database or map search, that additional cost must be included.

A capstone analysis should identify the input-size variables, dominant operations, time complexity, extra space complexity, assumptions, and reasons the approach fits the expected scale.

Takeaway: Complexity analysis compares growth, not exact elapsed time; state the assumptions that make the comparison meaningful.

Establish Correctness

Correctness means that the program meets its specification for every input in its defined domain. Testing reveals failures, but a finite test suite cannot alone prove that no untested input will fail.

One useful proof tool is an invariant: a statement that remains true during a loop. For the filtering loop, an appropriate invariant is that after processing the first $k$ records, the output contains exactly the eligible records among those first $k$ records, each paired with its calculated distance. When all records have been processed, the output therefore contains exactly the eligible records from the complete input. Sorting then establishes nondecreasing distance order.

Correctness can also be supported by case analysis, induction, comparison with a trusted reference implementation, or a precise argument linking each step to the specification. The argument should address empty inputs, invalid records, missing values, ties, and other defined boundary conditions.

Takeaway: Explain why every major step preserves the required behavior; do not treat successful examples as a complete proof.

Test Systematically

Plan tests from the specification. Useful categories include:

• Unit tests: test one function or component at a time.

• Integration tests: verify that components work together, such as loading, filtering, and ranking.

• Edge-case tests: include empty input, one record, no matches, all matches, duplicate identifiers, missing fields, invalid coordinates, tied distances, very large values, and unavailable or unknown data.

• Property-based or invariant tests: check general rules, such as every returned resource matching the requested category and the output being ordered by distance.

• Regression tests: preserve a test for every discovered defect so that later changes do not reintroduce it.

A useful test record includes the purpose, input, expected result, actual result, and interpretation of a failure. A failure may indicate a code defect, an incorrect or incomplete data record, or an ambiguity in the specification. Run the complete suite after significant changes, especially after optimization.

Takeaway: Testing is strongest when it checks both representative examples and general properties derived from the specification.

Evaluate Ethical and Social Consequences

A technically correct system can still cause harm. Ethical evaluation should influence data collection, representation, interface design, testing, and deployment rather than being added only at the end.

Ask the following questions:

• Privacy: What personal data is collected, why is each field necessary, how long is it retained, and who can access it?

• Fairness and accessibility: Could language, income, disability, location, or device access affect results? Are some communities missing or underrepresented in the data?

• Accuracy and safety: What happens when information is stale or wrong? Could an estimate be mistaken for a guarantee? Are high-risk decisions reviewed by a person?

• Security and accountability: Can unauthorized users alter records? Are important actions logged? Who is responsible when the system causes harm, and can users challenge or correct an output?

Document trade-offs rather than simply claiming that the system is ethical. For example, collecting more location data might improve ranking accuracy while increasing privacy risk. An impact table can record each risk, affected group, likelihood, severity, and mitigation. Possible mitigations include showing update times, minimizing retention, reporting coverage gaps, explaining ranking factors, and offering alternatives.

Takeaway: Evaluate consequences continuously and make uncertainty, limitations, and responsibility visible to users.

Communicate and Refine the Complete System

The final documentation should allow another person to understand the system and judge its limitations. Include:

1. The problem definition, users, assumptions, and constraints.

2. The data representation, fields, types, relationships, and missing-data rules.

3. The modular design and interfaces.

4. The algorithm, pseudocode, and a worked example.

5. The correctness argument or verification method.

6. The time and space analysis.

7. Testing categories, results, and unresolved defects.

8. Ethical risks, affected groups, trade-offs, and mitigations.

9. Limitations and realistic future work.

A demonstration should include successful and unsuccessful cases: a normal search, an empty result, malformed input, tied ranking, and a warning caused by stale information. The development process is iterative: a failed test may reveal a code error, inadequate representation, ambiguous requirement, or ethical risk. Revising the specification can be as important as revising the implementation.

A concise end-to-end sequence is: define, model, design, implement a baseline, test, analyze, improve carefully, evaluate impacts, and document the result.

Takeaway: A capstone is complete when its design decisions, evidence, limitations, and consequences are understandable and reviewable.

• Big O