Skip to content

Midterm Review

General information

  • Read all notes and given assignments
  • Focus on the following topics/techniques: know what they are, why we want to use them, their complexities (if applicable), trade-offs, how to apply them on small program examples

Genetic Algorithm

  • what kind of problems does it solve ? how to represent the solutions to the problem ? individual (chromosome), fitness evaluation, mutation and crossover, stopping criteria.
  • What is the goal of crossover ? of mutation ? (in other words, when do you want to use these more often?)
  • What’s local optimum ?

  • Given a problem, know how to use GA to solve it (pay attention to the representation of the solution and fitness eval).

  • Practice: PA1

  • Practice 2: How would you design a GA to achieve the goal of evolving a list of 100 integers whose elements are all the same (e.g., [-2,-2,-2 ....., -2 ] ? What is the fitness function?
  • Chromesome : list of 100 ints , [2,6,1,-2,100, ... , ] , [..... ]
  • [3,4,-3,-4]

Mutation Testing

  • How to create mutants?

  • How to compute mutation scores? (the formula is mutation score = number of mutants killed (detected) / total number of mutants)

  • Practice:

  • Consider the median program we often used
  • Construct a test suite A with 5 test cases (inputs and expected outputs)
  • Construct another small test suite B (~6 tests) that covers all statements
  • Manually mutate median to inject bugs (e.g., delete statement, mutate operations and variable names, replace, etc)
  • For each mutant, compute the mutation score for testsuite A and B
    • Compare which testsuite is better for the mutant

Frequency-based Debugging

  • What is the hypothesis of this technique?
  • When does it work well ? When does it not work well ? Give examples to illustrate
  • Practice: Examples shown in class and in-class assignment 1

Delta Debugging

  • What's the goal of DD ? Give examples/scenarios where it is useful. What is its complexity ?
  • Given an oracle and an input, able to apply delta debugging to find smallest part of the input that raises an error form the oracle _ Practice: Examples shown in class, in-class assignment 1, and PA3

Symbolic Execution

  • know why Symbolic Exe is useful. come up with a small example showing when SE is very useful (while other techniques would fail)
  • Know symbolic execution trees, how to compute feasible/infeasible paths
  • What are the three main problems with SE ? Explain and give concrete examples for each
  • Practice: Examples given in class and in-class assignment 2

Program Specification, Assertion, Invariants

  • Know defs of program invariants, precondition, postcondition, loop invariants, assertions

Miscs

  • Testing vs verification
  • Static vs dynamic analysis
  • Decidable/undecidable problems (gives example of problems that are NP-Complete, undecidable, explain)