Data Structures and Algorithms Test Review and Software Testing Guide

Upcoming Test Structure and Format

• Summary of Sections: The test on Friday is divided into four primary sections:

  • Multi-choice questions.

  • Heaps.

  • Graphs.

  • Sorting.

• Coding Question Format: Rather than a single large section requiring code to be written from scratch, coding-related questions are distributed across the thematic sections (heaps, graphs, sorting).

  • Snippet Analysis: Students may be presented with a code snippet (e.g., selection sort) with a missing line and asked to fill it in.

  • Code Explanation: Questions may ask for an explanation of what a specific block of code does.

  • Function Twists: The lecturer may provide familiar code from lectures or labs but with "small twists," such as changed variable names or slight logic alterations, to ensure students are reading the code rather than relying on memorization.

  • Partial Credit: Students are encouraged to write pseudo-code if they are unsure of the exact syntax, as this can still earn partial marks.

  • Parameter Identification: Questions may ask for the identification of function parameters (e.g., merging two arrays of integers).

Software Testing Principles and Definitions

• Primary Goals of Testing:

  • To find bugs and errors in the code.

  • To gain a deeper understanding of how the code functions.

  • To check for usability and accessibility.

• Inherent Limitation: Testing cannot prove that code is 100% bug-free; it can only demonstrate the presence of bugs, not their absolute absence.

• Formal Specifications: Later in the curriculum, students may learn mathematical proofs used to verify specific code properties, which are more reliable than random input/output testing.

• Decision Making in Testing: Because exhaustive testing is impossible (especially with loops, which create infinite paths), practical techniques include:

  • Testing using specification documents to determine expected outputs.

  • Testing high-risk areas of the system.

  • Testing both valid and invalid inputs.

  • Testing every statement (statement coverage), though 100% coverage may not always find all bugs.

Types of Faults and Testing Strategies

• Specification Fault: This occurs when the code works perfectly in a logical or syntactic sense (compiles without error and uses correct data structures) but performs the wrong task based on the requirements.

• Black Box Testing: A strategy where the tester has no access to the internal structure or source code of the application.

• White Box Testing: A strategy where the internal structure of the code is known. Examples include:

  • Statement Coverage: Ensuring every line of code is executed.

  • Branch Testing: Testing different branches in the code, specifically ensuring both the true and false paths of an "if-else" statement are executed.

• All Pairs Testing: A combinatorial testing technique where every possible pair of input parameters is tested. This significantly reduces the total number of tests needed compared to testing every single combination of all variables.

• Integration Testing: Testing the interactions and data transfer between different modules (input/output passed from one module to another).

• Regression Testing: Testing to ensure that recent changes or updates have not broken existing functionality.

Hazard Analysis and Risk Assessment

• Failure Modes and Effects Analysis (FMEA): A technique used to identify potential failure modes within a system, determine their causes, and analyze the resulting effects on the system.

• Hazop (Hazard and Operability Study):

  • A structured brainstorming activity involving clients and developers.

  • Uses "guide words" (e.g., "no," "more," "less") to identify potential hazards.

  • Example: Using "no" to discuss what happens if a method expected to return an object (like a plane to be landed) returns nothing.

• Event Tree Analysis (ETA): This starts with a specific event and follows its potential effects chronologically through the system to determine success or failure outcomes.

• Fault Tree Analysis (FTA): Operates in the opposite direction of ETA, starting with a fault and working backward to identify the combination of events that caused it.

• IEC 61508: An international standard for functional safety; severity and frequency categories from this standard are relevant for risk assessment.

JUnit and Unit Testing Best Practices

• Annotations:

  • @AfterEach: Runs a method after every single test in the class, often used for "tidying up" to ensure tests do not affect one another.

  • @BeforeEach: Used for setup tasks before each test.

  • @Test: Marks a method as a test case.

• The AAA Rule:

  • Arrange: Set up the conditions for the test.

  • Act: Execute the function being tested.

  • Assert: Check if the result matches the expectation.

• Isolation: Unit tests should be simple and isolated to make them easier to write, understand, and maintain. This also makes it easier to track the cause of failure and reduces the risk of the test itself being buggy.

• Test Oracle: A mechanism (specification documents, human experts, or past experience) that determines whether a test case has passed or failed by providing the expected result.

Heaps and Priority Queues

• Heap Order: A property where every node has a higher priority than all of its descendants. In a min-heap, the parent is smaller than its children; in a max-heap, the parent is larger.

• Heapify Operation: A process that swaps elements to restore the heap order property within an array.

• Indexing in a Zero-Indexed Heap: If the root is at index $i = 0$:

  • The right child of a node at index $i$ is found at $2 \times i + 2$.

  • (Note: The transcript discussion identifies $i \times 2 + 1$ as the answer in the specific quiz context, but standard zero-indexing is $2i + 1$ for left and $2i + 2$ for right).

• Delete Operation:

  • The root node is removed and swapped with the last element in the heap.

  • A downheap (or sink) operation is performed to restore the heap property by moving the new root down to its correct position.

• Stability: Priority queues are generally not stable; items with the same priority may not exit in the same order they entered.

Graph Theory and Algorithms

• Applications: Graphs represent social networks, location/distance data, and task dependencies (modeling which courses are prerequisites for others).

• Database Storage: Graphs are generally not used for standard relational database storage; B-trees (a type of search tree where nodes have many children) are used to maximize data retrieval from RAM.

• Components: Graphs consist of nodes (vertices), edges, paths, and weights.

• Cyclic vs. Acyclic: A cyclic graph contains at least one cycle (a path that starts and ends at the same node). An acyclic graph has no cycles.

• Dijkstra's Algorithm:

  • Finds the shortest path from a starting node to other nodes.

  • Uses a priority queue to select the next node with the smallest cost to visit.

  • Works on weighted and unweighted graphs but requires that there are no negative edge weights.

  • It is classified as a greedy algorithm because it makes the locally optimal choice at each step.

Sorting Algorithms and Complexity

• Selection Sort: Worst-case complexity is $O(n^2)$.

• Bubble Sort: Worst-case complexity is $O(n^2)$, occurring when the list is in reverse order.

• Tree Sort: Worst-case complexity is $O(n^2)$ (specifically when the tree becomes an unbalanced linked list).

• Merge Sort:

  • Complexity is $O(n \tan(n))$ for best, average, and worst cases.

  • It is more space-intensive than other sorts because it often requires copies of the array halves.

• Quick Sort:

  • Average-case complexity is $O(n \tan(n))$.

  • Worst-case complexity is $O(n^2)$, occurring with poor pivot selection (e.g., repeatedly splitting at the extreme ends).

• Heapsort: Consistent complexity of $O(n \tan(n))$ across all cases.

Questions & Discussion

• Question: Will the true or false questions be replaced with blanks?

  • Response: There won't be standard true/false sections. The test will instead feature diagram-based questions (stepping through traversals) and more writing.

• Question: How many sections are there?

  • Response: There are four sections: Multi-choice, Heaps, Graphs, and Sorting.

• Question: Do we need to memorize all the Big O values?

  • Response: While specific memorization isn't the primary goal, knowing Big O helps explain algorithm efficiency. The lecturer will focus on special cases (e.g., why one algorithm has a specific worst case while another does not).

• Question: Is there a section on testing?

  • Response: There is no dedicated section for testing; testing questions will be integrated into the multi-choice section or other areas if space permits.