module0

CS350 – SISO Model and Decision Problems

Purpose

  • Examining models of computation to understand the limits of what can be computed.

  • Starting with a familiar model: Python programs.

  • Precision is required for programs and outputs to study computational processes.

  • Notable concept: A program can process itself.

Knowledge Goals

  • Understand the precise definition of the Python program model of computation.

  • Understand the precise definition of the output of a Python program.

Activities

  • Work in groups to complete tasks and answer related questions, with a report due in 45 minutes.

Tasks

  1. Define P(I) (the output of program P on input I as strings):

    • Examples:


      • (a) P = "def f(inString): return inString[3:7]"I = "abcdefghij"


      • (b) P = "def f(inString): return inString[3]"I = "ab"

Decision Problems

  • Decision problems produce outputs of either "yes" or "no".

  • Consider the program file containsGAGA.py:

    • (a) What is the value of containsGAGA("CTGAGAT")?

    • (b) What is the value of containsGAGA(rf('containsGAGA.py')), where rf reads contents of files?

Additional Program Files

  • Consider the program file yes.py:

    • (c) What is the value of yes(rf('containsGAGA.py'))?

    • (d) What is the value of yes(rf('yes.py'))?

  • Consider the program file longerThan1K.py:

    • (e) What is the value of longerThan1K(rf('containsGAGA.py'))?

    • (f) What is the value of longerThan1K(rf('longerThan1K.py'))?

More Decision Problem Analysis

  • Consider the program file maybeLoop.py:

    • (g) What is the value of maybeLoop("CTGAGAT")?

    • (h) What is the value of maybeLoop("some secret sauce")?

    • (i) What is the value of maybeLoop(rf('containsGAGA.py'))?

    • (j) What is the value of maybeLoop(rf('maybeLoop.py'))?

Assignments for Grading

  • Assignments to be completed individually, consultation permitted for strategy discussions.

Assignment Details

  1. Assignment 1:

    • Try the Python function hmmmm and respond to questions in exercise 2.7 on p28 of your text.

    • Criteria for Success: Clear and concise written answers for all four questions, clearly describing the sets of strings involved.

  2. Assignment 2:

    • Use the Python function oooops and respond to questions in exercise 2.9 on p29 of your text.

    • Criteria for Success: Clear answers for all seven questions, clearly defining the string sets involved.

  3. Assignment 3:

    • Discuss how a task (mouse click input for graphics output) can be achieved within the SISO model. Explain how inputs and outputs can be viewed as strings.

    • Criteria for Success: Clear explanation of the string representation of input and output.

  4. Assignment 4:

    • Complete exercise 3.2 on p42 to deepen understanding of self-analyzing programs.

    • Criteria for Success: Submit two Python programs countChars.py and countCharsB.py, plus written explanations of their behavior on themselves and differences in execution.

    • Submission through Canvas.