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
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')), whererfreads 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
Assignment 1:
Try the Python function
hmmmmand 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.
Assignment 2:
Use the Python function
oooopsand 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.
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.
Assignment 4:
Complete exercise 3.2 on p42 to deepen understanding of self-analyzing programs.
Criteria for Success: Submit two Python programs
countChars.pyandcountCharsB.py, plus written explanations of their behavior on themselves and differences in execution.Submission through Canvas.