ACDT — Problem Set #4 | Group + Individual

Pattern Recognition Analysis & Pseudocode

Development
Due: Before Week 5 · Submission: Google Doc via LXP · §4.1 Group · §5.2 Individual · AI
allowed in §4.4 & §5.3 only

This component consists of 25% of your course credit. No AIs are allowed to use, except specified where
allowed. If AI use is detected, the academic integrity regulation would apply.

▌ What PS#4 builds on top of PS#3

PS#3 asked you to name patterns, sketch an algorithm, and list open questions.
PS#4 asks you to formalise, analyse, and implement.

PS#3: 'This looks like a scheduling problem.' (name it)

PS#4: 'Here is the precise structural similarity, the formal pattern category,
the abstract formulation, and the pseudocode that implements it.' (prove it)

IMPORTANT: Do NOT copy your PS#3 answers into PS#4. Every section here asks
something analytically deeper than what PS#3 asked. Reuse your PS#3 findings as
input material, but write new analytical responses.

Part 4: Pattern Recognition Analysis (40 points) — Group

Section 4.1 Pattern Evidence Table (10 points)
In PS#3 §4.1 you named 3–5 similar problems. Now prove the similarity structurally. Choose
3 of those problems and complete the mapping table below. You are not listing — you are
analysing.

Note
Do NOT just re-list your PS#3 §4.1 problems here.
Each row must show WHY the structural similarity exists — constraint type, optimization goal,
and explicit mapping to your specific problem.

▌ What 'Structural Mapping' means — example

Your 8-hr Problem: Medication Interaction Checker
Analogous Problem: University Course Scheduling
●​ Shared Constraint Type: Both have EXCLUSION constraints (drug interactions / room
conflicts) and CAPACITY constraints (step limits / seat limits)
●​ Shared Optimization Goal: Both minimise constraint violations while maximising a
quality score (patient safety / student preference)
●​ Structural Mapping: Patients → Students, Medications → Courses,
Interaction rules → Prerequisites & time conflicts,
Treatment sequence → Semester timetable
Analogous Problem Shared Constraint Shared Structural Mapping to Your
Type Optimisation Goal Problem

Section 4.2 Pattern Classification (10 points)

Classify your problem (or sub-problems) using the TWO-LEVEL taxonomy below. This is a
different and more precise framework than the category names you used in PS#3 §4.2.
Select 1–2 primary patterns at each level and justify your choice.

Level Categories
Control Flow Sequence · Selection (IF/ELSE) · Iteration (FOR/WHILE)
Problem-Solving Search · Sort · Match · Optimise · Transform · Filter

Sub-problem: XXX

Primary Control-Flow Pattern(s): _______________

Primary Problem-Solving Pattern(s): _______________

Explanation — why these patterns fit your problem (3–4 sentences):

Evidence in your 8-Hour Problem:

· Input:

· Goal:
 · Constraints:

· Why this matches the pattern:

Add (Sub)Problems if applicable: You may apply your sub-problems with Pattern
Classification.

Section 4.3 Generalised Problem Statement (20 points)

Write an abstract, domain-free version of your problem that captures only the computational
essence. Replace all domain-specific nouns with abstract terms. The generalised form
should apply equally to your problem and to the analogous problems in §4.1. This will make
you understand how your algorithm is structurally similar to other algorithm.

▌ Example
Original: 'Design a treatment sequence for 2 patients from 10 medications, satisfying
patient-specific allergy/contraindication constraints and step-count limits, while minimising side
effects and maximising coverage of all conditions.'

Generalised: 'Assign K items from a set of N candidates to M agents, subject to agent-specific

exclusion constraints E and cardinality constraints C, optimising objective function F (coverage
× safety score).'

Abstraction mapping:
●​ Patients → Agents (M) | Medications → Candidates (N) | Treatment steps →
Assignments (K)
●​ Allergy rules → Exclusion constraints E | Step limits → Cardinality constraints C

Original 8-Hour Problem Statement (copy from PS#2 or PS#3):

Generalised Problem Statement:

Abstraction Mapping:
Domain-Specific Term → Abstract Term

→
→

→
Part 5: Pseudocode Development (35 points) — Individual

Important
Parts 4.1– 4.3 were group work. Part 5 is INDIVIDUAL. You may use the outcomes from AL2 in
the Week 4 class (Your 8-hr Problem).
Each student writes their own pseudocode — even if you share the same group problem.
AI assistance is allowed in §5.3 only. §5.1 and §5.2 must be entirely your own work.

▌ Reading guide for Part 5 — what each section does

§5.1 Scaffolded Pseudocode (15 pts)
You build pseudocode in SIX guided sub-steps. Each sub-step asks one specific question.
This is the main writing section. You should spend most of your time here.

§5.2 Complete Pseudocode (15 pts)

Assemble everything from §5.1 into one clean, formatted, commented pseudocode block.
This is copy-edit work — you already have the logic from §5.1.

§5.3 Walk-Through Example (5 pts) — AI allowed

Trace your pseudocode with a tiny test case to verify the logic works.

SECTION
Scaffolded Pseudocode
5.1 Work through SIX building blocks in order.
Each block becomes part of your complete pseudocode in §5.2.
15 pts

▌ BLOCK 1 of 6 — Name your inputs (what does the algorithm receive?)

An algorithm can only work with what it is given. List every piece of information your algorithm
needs at the start — before it does any processing. Note that you may use the jargons from
Python but don’t need if you are not familiar with them.

For each input, write: variable_name : data type — what it contains

Example (Medication Interaction Checker)

patient_list : list of records — each record has {id, conditions[], allergies[], kidney_flag}
medication_list : list of records — each record has {id, treats_conditions[], interacts_with[]}
step_limit : integer — maximum treatment steps allowed per patient
supporting_meds : list — medications that boost or reduce side effects of others

Your inputs (list all — add rows as needed):

 ▌ BLOCK 2 of 6 — Name your outputs (what does the algorithm produce?)
What should exist AFTER the algorithm finishes running?
List every result your algorithm must return or display. Note that you may use the jargons from
Python but don’t need if you are not familiar with them.

Example (Medication Interaction Checker)

treatment_plan : dictionary — {patient_id → ordered list of medications}
step_count : integer — total steps used per patient
warnings : list — any soft-constraint issues (e.g., near step limit)
is_feasible : boolean — TRUE if a valid plan was found, FALSE otherwise

Your outputs (list all):

▌ BLOCK 3 of 6 — Write the validation step (what could go wrong at the start?)
Before the algorithm does any real work, it should check that its inputs are valid.
What are the two or three most important things to check?

Pattern: IF [bad condition] THEN RETURN error message and STOP.

Example (Medication Interaction Checker)

IF patient_list is empty THEN
OUTPUT 'Error: no patients provided'
RETURN
END IF

IF medication_list is empty THEN

OUTPUT 'Error: no medications available'
RETURN
END IF

IF step_limit < 1 THEN

OUTPUT 'Error: step limit must be at least 1'
RETURN
END IF

Your validation checks (2–3 IF checks using the pattern above):

 ▌ BLOCK 4 of 6 — The main loop (what does the algorithm repeat?)
Most algorithms have one big loop: for each [thing], do [process].

Answer these three questions, then write the FOR loop:

Q1: What are you looping over? (each patient? each condition? each candidate medication?)
Q2: What is the FIRST thing you do inside the loop? (decompose? filter? match?)
Q3: What is the LAST thing you do inside the loop? (store result? check conflict? update
count?)

Q1 — I am looping over: Q2 — First action inside loop: Q3 — Last action inside loop:

Example (Medication Interaction Checker)

FOR each patient IN patient_list DO
conditions_to_treat ← [Link] // decompose
safe_meds ← FILTER medication_list // filter
WHERE medication NOT IN [Link]
AND medication does not cause kidney damage IF patient.kidney_flag = TRUE
selected_meds ← MATCH safe_meds TO conditions_to_treat // match
treatment_plan[[Link]] ← ORDER(selected_meds) // sequence
step_count[[Link]] ← LENGTH(treatment_plan[[Link]])
END FOR

Your main loop (write the FOR structure using the pattern above):

▌ BLOCK 5 of 6 — Constraint checks (what rules must the result satisfy?)

After the main loop produces a result, check that it satisfies all hard constraints.
For each constraint, write: IF [constraint violated] THEN [fix or flag].

List your constraints first, then write one IF block per constraint.

Example (Medication Interaction Checker)

// Constraint 1: step count must not exceed limit
IF step_count[[Link]] > step_limit THEN
 ADD 'Warning: treatment exceeds step limit' TO warnings
// Try to optimise: replace Med 3 + Med 9 with Med 9 alone (covers both C and D)
END IF

// Constraint 2: no same medication at same step across both patients

FOR each step s IN 1 TO MAX_STEPS DO
IF treatment_plan[mulder][s] = treatment_plan[scully][s] THEN
is_feasible ← FALSE
OUTPUT 'Conflict at step ' + s
END IF
END FOR

Your constraint checks (one IF block per constraint — 2–3 constraints minimum):

▌ BLOCK 6 of 6 — Output (what does the algorithm return?)

The final step: output everything you said would be produced in Block 2.
Check: every output from Block 2 must appear here.

Example (Medication Interaction Checker)

// Output section
IF is_feasible = TRUE THEN
OUTPUT 'Treatment plan found successfully'
FOR each patient IN patient_list DO
OUTPUT [Link] + ': ' + treatment_plan[[Link]]
OUTPUT 'Steps used: ' + step_count[[Link]] + ' / ' + step_limit
END FOR
ELSE
OUTPUT 'No valid treatment plan exists for this patient combination'
END IF

IF warnings is NOT empty THEN

OUTPUT 'Warnings: ' + warnings
END IF

RETURN treatment_plan, step_count, is_feasible, warnings

Your output section:

 Tip
Check before moving to §5.2:
✓ Block 1 (inputs) and Block 2 (outputs) — do they match? Every output must come from
somewhere.
✓ Block 3 (validation) — does it catch the most dangerous bad inputs?
✓ Block 4 (main loop) — does it actually process every case?
✓ Block 5 (constraints) — does it check every hard rule from your problem?
✓ Block 6 (output) — does it return everything listed in Block 2?

SECTION
Complete Pseudocode
5.2 Assemble all six blocks into one clean, formatted pseudocode.
Add variable names, comments, and proper indentation.
15 pts

Take everything you wrote in §5.1 and combine it into a single pseudocode block below. Your
job here is formatting, commenting, and making the logic flow clearly — not rewriting the
logic from scratch.

Important
This section must be entirely your own work — no AI assistance.
Write in language-agnostic pseudocode. Do NOT use Python, Java, or C syntax.
Aim for 50–100 lines. Add // comments to explain non-obvious steps.

▌ Pseudocode Conventions Reference

BEGIN / END → marks the start and end of the algorithm
INPUT / OUTPUT → data entering or leaving the algorithm
← → assignment (result ← value)
IF condition THEN ... END IF → decision branch
IF ... THEN ... ELSE ... END IF → branch with alternative
FOR item IN list DO ... END FOR → loop over a collection
WHILE condition DO ... END WHILE → loop until condition is false
FUNCTION name(params) ... RETURN → reusable sub-procedure
// comment → explanation (not executed)

Variable naming: use_underscores (not camelCase, not singleLetters)

Indentation: 4 spaces per level (or consistent tabs)

BEGIN [YourAlgorithmName]

// ─── INPUTS ───────────────────────────────────────────────

 // (Copy from Block 1 of §5.1 — rewrite as INPUT statements)
INPUT ...
INPUT ...

// ─── VALIDATION ────────────────────────────────────────────

// (Copy from Block 3 of §5.1)
IF ... THEN
OUTPUT '...'
RETURN
END IF

// ─── INITIALISE ────────────────────────────────────────────

treatment_plan ← empty dictionary
is_feasible ← TRUE
warnings ← empty list

// ─── MAIN LOOP ─────────────────────────────────────────────

// (Expand from Block 4 of §5.1)
FOR each ... IN ... DO

// Step 1:
...

// Step 2:
...

// Step 3:
...

END FOR

// ─── CONSTRAINT CHECKS ─────────────────────────────────────

// (Copy from Block 5 of §5.1)
IF ... THEN
...
END IF

// ─── OUTPUT ────────────────────────────────────────────────

// (Copy from Block 6 of §5.1)
OUTPUT ...
RETURN ...

END [YourAlgorithmName]

§5.2 Grading Criterion Points What we look for

Correctness 15 Logic solves the problem; all conditions treated; constraints
satisfied; inputs and outputs align
Completeness 5 All 6 blocks present; edge cases handled; no unexplained gaps in logic

Clarity 5 Well-commented; consistent naming; indentation correct; easy to follow

without guessing

Convention 5 Language-agnostic; uses only the pseudocode keywords listed above; not
real code
Bonus (optional) up to Exceptional comments explaining design decisions; elegant optimisation;
+5 creative structure

SECTION
Walk-Through Example
5.3 Trace your pseudocode with a small, concrete test case.
AI may generate the test case. You must verify it is correct.
5 pts

AI USE ALLOWED — mark your section clearly

You MAY use AI to generate the test case and trace in this section.
If you do, mark the section clearly: 'AI-ASSISTED SECTION: 5.3'
Then include: (1) the exact prompt you used, and (2) any corrections you made to the AI
output.

Create a SMALL version of your problem (3–5 entities, not the full scale). Walk through your
pseudocode step by step and show what the key variables contain at each stage. Then test
one edge case.

Example (Medication Interaction Checker)

Test Case: 2 patients, 5 medications, step limit = 4

INPUT:
patient_list = [Mulder: {conditions:[A,B,C,D], allergies:[Med6,Med7], kidney:TRUE},
Scully: {conditions:[B,D,E], allergies:[], kidney:FALSE}]
medication_list = [Med1→A, Med2→B, Med4→D, Med6→E, Med8→booster, Med9→C+D]
step_limit = 4

Step-by-step trace:
Iteration 1 — Patient: Mulder
Block 4 — FILTER: remove Med6, Med7 (allergy), Med10 (kidney) → safe_meds =
[Med1,Med2,Med4,Med5,Med8,Med9]
Block 4 — MATCH: A→Med1, B→Med2, C+D→Med9 (dual coverage), booster→Med8
Block 4 — ORDER: [Med1, Med8, Med2, Med9] ← Med8 before Med2
step_count[Mulder] = 4 ✓ (≤ step_limit)

Iteration 2 — Patient: Scully

Block 4 — FILTER: no allergies → all medications available
Block 4 — MATCH: B→Med10, D→Med4, E→Med6
Block 4 — ORDER: [Med8, Med10, Med4, Med6] ← Med8 before Med10
step_count[Scully] = 4 ✓

Block 5 — No-same-step check: [Med1,Med8,Med4,Med6] vs [Med1,Med10,Med4,Med6] →

Step 2 conflict!
Adjust Mulder: swap Med1 to step 1 only → re-check → resolved

OUTPUT: treatment_plan = {Mulder:[Med1,Med8,Med2,Med9],

Scully:[Med8,Med10,Med4,Med6]}
is_feasible = TRUE · warnings = []
 Edge case: patient_list is empty → Block 3 catches → OUTPUT 'Error: no patients' ✓

Test Case Description:

INPUT (small concrete values):

Step-by-Step Trace (show key variable values at each major step):

Expected Output:

Edge Case Test (one unusual input and what your algorithm does with it):

▌ AI Use Policy
ALLOWED (mark section + include exact prompt + describe your edits):
✓ §5.3 Walk-Through Example — AI may generate the test case and trace

PROHIBITED:
✗ §4.1 Pattern Evidence Table — structural analysis must be your own
✗ §4.2 Pattern Classification — taxonomy application must be your own
✗ §4.3 Generalised Statement — abstraction must be your own
✗ §5.1 Scaffolded Pseudocode — all 6 blocks must be your own
✗ §5.2 Complete Pseudocode — AI use here is academic misconduct

If you use AI in §5.3, include: (1) the exact section marked, (2) the prompt you used,
 (3) what you corrected or added after reviewing the AI output.

TIPS FOR SUCCESS

Pattern Recognition
●​ Think about the STRUCTURE of your problem, not just the domain
●​ Look for problems in different fields that share the same pattern
●​ Use the generalized statement to search for existing solutions

Pseudocode Writing
●​ Start with the Input-Process-Output template
●​ Write in plain English first, then formalize
●​ Test your logic with a simple example BEFORE writing full pseudocode
●​ Read your pseudocode aloud - does it make sense?
●​ Have a teammate review it - can they follow the logic?

Common Mistakes to Avoid

●​ Being too vague: "Process the data" → Be specific about HOW
●​ Being too detailed: "import pandas as pd" → Stay language-agnostic
●​ Skipping edge cases: What if input is empty? Invalid? Too large?
●​ Inconsistent naming: student_age vs studentName → Pick one style
●​ No comments: Add WHY, not just WHAT

If you're stuck:
●​ Attend office hours with leaders (schedule on LXP)
●​ Post questions on course Slack (#Q&A channel)
●​ Review Week 4 lecture slides and examples
●​ Consult with your team members