Notes on Structured Programming, Arrays, and Iteration (COMP1110/1140/6710)

Structured Programming

• Topic on structured programming as part of COMP1110/1140/6710 curriculum.
• Emphasizes using loops and structured constructs instead of unbounded recursion; iteration is a primary design strategy.
• Iteration can be nested; multiple loops can follow one another to process data stepwise.
• Each loop should be accompanied by a comment explaining its termination condition (where applicable).

Arrays & null

• Non-primitive reference types can hold a special value: null, representing the absence of a value.

• Uninitialized reference example:

  • Code: $String str;$
  • str == null at this point; calling $str.length()$ would cause a $NullPointerException$.

• Demonstration with Map:

  • Code: Map
  • Code: $String str = map.get("Hello");$
  • Result: $str == null$ at this point, since the key "Hello" is not present.

• Similar concept to the Maybe type discussed previously: a value may or may not exist.

• Practical implication: always check for null before dereferencing a reference, or use safe access patterns.

• Example of null usage in a retrieval:

  • Code: $String str = map.get("Hello"); // str == null if key absent$
  • Then you would handle the null case before using $str$.

Arrays: Storing many values at once

• Declaration and initialization:
  • Code: $String[] strings = new String[3];$
  • Initially, all elements are null: $strings[0] = null, \ strings[1] = null, \ strings[2] = null$.
• Populating the array:
  • Code:
  • $strings[0] = "Hello";$
  • $strings[1] = "World";$
  • $strings[2] = "!";$
  • After population, elements are: [0] = "Hello", [1] = "World", [2] = "!".
• Before population, the array contents would be: [0] = null, [1] = null, [2] = null.
• Alternate initialization style:
  • Code: $String[] strings = new String[]{"Hello", "World", "!"};$
  • Results in: [0] = "Hello", [1] = "World", [2] = "!".
• Accessing length and elements:
  • Length: $strings.length$
  • Access: $strings[i]$ for valid i in 0 \le i < strings.length.
• Iteration examples (previews shown in later pages): iterate over arrays with for-loops or enhanced for-loops.

Loops

• Loops are presented as an alternative to recursion and are a fundamental control structure in structured programming.
• Common loop constructs in this material:
  • For-loops: with a termination condition controlled by a counter.
  • Enhanced for-loops: iterating over elements of a collection or array.
  • While loops: general-purpose looping when the number of iterations is not fixed in advance.
  • Do-while loops: ensure the body runs at least once.
• Important general rule: each loop has a termination condition that determines when the loop stops.

For-loops

• General form (counter-controlled):
  • Code: for(int\ i=0;\ i<10;\ i++){\ println(i);}\;
  • Semantics: starts with $i = 0$, checks i < 10 before each iteration, increments $i$ after each iteration.
• Enhanced for-loops (iteration over items):
  • Code (conceptual): $for(var\ str :\ strings){\ println(str);}\;$
  • Works for many different list-like data types (arrays, lists, etc.).
• Important notes:
  • The middle expression in a standard for-loop acts as the termination check.
  • In an enhanced for-loop, termination is determined by the container's size.

For-loops with arrays

• Iterating over arrays by index:
  • General form: String[] strs = \dots; for(int i = 0; i < strs.length; i++){\ println(strs[i]);}\;
• Enhanced-for form (foreach-like):
  • Code: $String[] strings = \dots; for(var str : strings){\ println(str);}\;$
• In both forms, using $strs.length$ ensures you don’t access past the end of the array.

While loops

• More general, but also more prone to non-termination if not careful.
• Classic while:
  • Code: $while(true){\ some-code;\ }\;$
  • This loop will continue indefinitely unless there is a break or other control flow altering the condition.
• Do-while:
  • Code: $do{\ some-code;\ }\ while(\text{some-Boolean-exp});$
  • Ensures the body executes at least once before evaluating the condition.

Loop termination and control flow

• Each loop has a condition (the boolean expression that controls continuation):
  • For: the middle expression, e.g., i < 10 in for(int i=0; i<10; i++).
  • Enhanced for: continuation is based on the number of elements remaining in the collection.
  • While/do-while: the boolean expression after $while(…)$.
• Execution order: loops do not execute strictly top-to-bottom; control transfers occur between iterations.
• Special statements:
  • $break;$ ends the loop immediately, ignoring the loop condition.
  • $continue;$ skips to the next iteration of the loop (for-loops: advance to the next element).
  • In for-loops, $continue;$ effectively behaves as going to the increment/next element step.

The Design Recipe with Iteration

• Iteration is a design strategy for handling repetitive tasks using loops (for/enhanced for/while/do-while).
• When iteration is used, it takes priority over case distinction in the design process.
• Iteration can be nested; multiple loops can occur in sequence to process data in stages.
• Important guidance: each loop should include a comment explaining why and how it terminates.
• New design strategy named: Iteration

Iteration examples and patterns

• Example: iterating over finite-size data structures
  • Pattern: $for(String name : names){\ldots}$
  • Use case: traverse a known collection of a fixed size.
• Example: termination upon user input
  • Pattern: $while(true){\ if(readln().equals(\"q\")) { break; } }$
  • Implements user-driven termination by breaking when a specific input is received.
• Example: converging bounds (two indices moving toward each other)
  • Pattern:
  • do{\ \ldots\ }\ while(i < j);
  • Inside: adjust $i$ or $j$ depending on some condition, until $i \ge j$.
  • Code sketch: { \dots\ if(\dots) { i++; } else { j--; } } while(i < j);
• Core takeaway: iteration allows expressing repetitive tasks cleanly and flexibly, but must guarantee termination and be documented with termination reasoning.

Quick recap: key concepts to remember

• Null and null checks are essential when dealing with reference types to avoid NullPointerException.
• Arrays are fixed-size containers; they initialize with null references by default for object types.
• For-loops provide a counting mechanism; enhanced for-loops provide a concise way to iterate over all elements in a collection.
• While-do-while offer flexible looping with explicit termination conditions.
• Break and continue are control-flow tools to alter the normal loop progression.
• The Design Recipe emphasizes Iteration as a core design strategy, with explicit termination reasons and potential nesting.
• Real-world relevance: avoiding infinite loops, preventing NPEs, and writing clear, maintainable loop-based code.

References to the slides

• Page references shown in the transcript (e.g., page 3 for null references, pages 4–10 for arrays, page 11 for Loops, pages 12–13 for For-loops, page 14 for While loops, page 15 for execution order, page 16–19 for The Design Recipe with Iteration).
• New design strategy: Iteration introduced on page 17 with examples of termination comments and nested loops.

Notation and examples in the transcript (LaTeX-formatted highlights)

• Loop condition forms:
  • ext{for}(int\ i=0;\ i<10;\ i++)
  • $ext{while}(true)$
  • $ext{do}{\dots}\ ext{while}(\text{condition});$
  • $ext{for}( ext{var}\ name : \text{names})$
• Array access and length checks:
  • $\text{strings}[i]$ and $\text{strings.length}$
• Termination mechanics:
  • \text{break}();\
  • \text{continue}();\
• Null representation and checks:
  • $\text{null}$ as absence of a value
  • NullPointerException occurs when dereferencing a null reference

End of notes