CS 180 Problem Solving and OO Programming Fall 2010

Report
SOPH 303 The Digital World
Term 3
Spring 2013
http://faculty.sutd.edu.sg/~aditya_mathur
Notes for January 28, 2013
Last update: January 28, 2013
Aditya Mathur
Head of Pillar
Information Systems Technology and Design
Singapore University of Technology and Design
Singapore
This is the first
lecture in
10.009 Term 3
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
2
And the last!
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
3
Today
Our instructors
Digital World: What is this class about?
What is problem solving and programming?
Our expectations of you
Reference material, grading, and tools
Design competition and 2D challenge
Digital World: Why is it a required subject?
Let us browse the course web site
Introduction to Tutor and a quiz
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
4
Digital World
1/28/2013
Physical World
The Digital World. Term 3. 2013. Week 1.
Session 1
5
Our approach to
teaching and
learning?
Play and learn
Do not be
turned off by
error!
1/28/2013
Solve lots of
problems
The Digital World. Term 3. 2013. Week 1.
Session 1
6
Digital World
Physical World
Enabling technology
Control technology
Provides flexibility
Provides variety
Provides connectivity
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
7
What is Digital World?
…It is a world of computers, embedded and otherwise
…it is a world where computers are used to perform a variety of
tasks or help us perform tasks..
…it is a world where computer hardware and software play a key role
in our lives…
…it is a world that integrates well with the physical world to add to
flexibility and quality…
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
8
Is Digital World Computer Science?
…Yes and no
…but Computer Science is one of the key drivers of the Digital
World..
…and so are Computer Engineering, Electrical Engineering, and
Mathematics
…and almost everybody is a user of the Digital World!
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
9
What will I learn?
You will learn the
basic drivers of the digital world
Problem solving and programming
and how the digital world interfaces with
the physical world
Controlling a physical device [robot] for
movement and search
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
10
Programming language used
Our “snake”
2.7
3.3
Listen to Python
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
11
Course Web Site and Other Resources
Course Web site:
http://faculty.sutd.edu.sg/~aditya_mathur
Python Resources:
A Primer on Scientific Programming with Python, Hans Petter Langtangen
Think Python, Allen B Downey
Online resources: Python tutorial
MIT notes on Python and linear systems
Technical Q&A:
www.piazza.com
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
12
Drivers (and the essential elements)
of the Digital World
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
13
Problem solving
Top down problem solving: How to break a problem into smaller
problems, find solutions to the smaller problems and combine
them to get a solution to the original problem.
Bottom up problem solving: How to combine solutions to small
problems into a solution to a large problem.
Coding: How to code the solution to a problem in Python and let
the computer solve the given problem.
Debugging: How to locate errors in your program (and correct
them).
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
14
Modularity
How to build components (modules) that can be reused.
Example: (a) A software module to solve a first order differential
equation. (b) A hardware module that gives the current location
of a mobile object.
User
User interface
Polynomial
Root finder
What are the
modules in this
diagram?
Root presenter
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
15
Abstraction
The process of reducing a real life system, or an idea, to its
“essentials.”
Example: A stick-person is an abstraction of a real person.
System stability
analyzer
Root finder
Polynomial
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
16
Modeling
Representation of one or more aspects (behavioral in our case) of a
component or a system.
Example: Diagrammatic description of the behavior of a system.
Can you complete
this state diagram for
a machine of your
choice?
System: Coke vending machine
Simple model
50c/-$1
50c
50c
Screen showing
how much money
is to be deposited
50c/dispense coke
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
17
Design and the PCAP approach
A basis set of primitive components
are combined to create complex components (or systems)
by the process of abstraction that creates new primitive components
that become new abstractions and patterns.
Can you describe your favorite device using the above approach?
[E.g. your mobile phone?]
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
18
Fun in the Digital World
There is a lot of---sometimes too much---fun in the Digital World.
The Amigobot
Follow wall oscillating:
http://www.youtube.com/watch?v=r7ux5E8SW2g
Follow wall smooth:
http://www.youtube.com/watch?v=nv6IJYBRYgg
Fun with the Amigobot:
Hey man! Follow the leader!
1/28/2013
You will learn how to program
and control the Amigobot.
The Digital World. Term 3. 2013. Week 1.
Session 1
19
Expectations
“Most of us know next to nil about programming. So
a slower pace during the course will be greatly
appreciated...if not it'll be like MATLAB.”..from one of
you posted on Piazza.
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
20
Please note….
Classes will begin on time. Please be at your seat a few minutes
before the class begins and, if you have to, then leave only after
the class ends.
All students are encouraged to ask questions and participate
during the cohort sessions. You may interrupt the instructor at
any time. No question is a stupid question.
The instructors are here to help you learn. Make full use of the
instructors.
We want you to succeed in this class. We will do all we can to
help you succeed; this is our primary responsibility as instructors
at SUTD.
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
21
Assumptions
You have little or no expertise in computer programming using Python.
You are hard working.
You will not sleep during classes, and if you do, please do not snore!
You will not use phones during class for any other purpose than
specified by the instructor. Please, no phone calls received or
sent.
You will not disturb others by talking to your neighbors except
when the instructor requests discussion during problem solving
time.
You will try to participate in the class by asking questions and
responding to questions asked by the instructor.
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
22
Impact of Assumptions
Those who know Python well may get bored during the first six weeks of this
course
but others may find the pace quite appealing.
For those with some Python experience, we recommend solving
advanced homework problems just for fun.
You should skip the class if you need to discuss important matters with your
friends. But skipping a class is not a good idea! So maybe you might consider
rescheduling the important matters with your friend.
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
23
Expectations: Academic Honesty
Unless specified otherwise, all assignments and exams are to be
completed by you without assistance from anyone other than the
course instructors.
Please read carefully the Policies page on the course
web site.
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
24
Expectations: Attendance
We expect you to attend all cohort sessions during the term.
Attendance is not mandatory but highly recommended.
If you miss a cohort session then it is your responsibility to (a) learn
on your own the material covered (b) find out if there were any
announcements that might affect your course grade.
There will be no makeup for a quiz given during the cohort session.
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
25
Reference material, grading, and tools
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
26
Textbook
There is no textbook for this course.
Please use the online and other material available in the library.
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
27
Leave
Please submit your leave application to the Cohort Section Manager (see Office
Hours page of the course web site to find your section manager).
Leave will be granted only for medical and emergency reasons.
You may miss up to two quizzes without affecting your course grade.
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
28
Grading
Component
Weight (%)
Midterm Exam
(Friday March 8, 2013. 2:30-4:30pm)
Cohort exercises
Homework
Quizzes
Final Exam
2D Designette
Class participation
15
TOTAL
100
20
10
10
25
15
5
Relative grading
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
29
Exams and quizzes
All exams (not quizzes) will be “open internet” implying that
you will be able to access and use the Internet content to
help solve problems on the exam.
All in-class exercises will be completed by teams of two or
three students.
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
30
Tools
Piazza:
Please register yourself by visiting the Piazza site
(www.piazza.com).
You may post your questions at this site. You may answer
student questions at this site.
Instructors will be regularly browsing this site and answer
your questions.
Tutor: For homework, exams, and grading
IDLE: For editing Python programs
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
31
Feedback
Weekly feedback: via Learning Catalytics
•
Tell us how are we doing?
Weekly feedback: open
•
•
1/28/2013
Tell us in an open forum what needs to improve.
Constructive criticism of the class is highly appreciated.
The Digital World. Term 3. 2013. Week 1.
Session 1
32
Why is The Digital World a required
subject?
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
33
I am interested in architecture.
I do not like programming.
I would rather get a C or a D in this class
and get outta here!
But wait a minute my friend…..
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
34
Architecture Systems Design
Do you know about Blender 3D Architect?
Well, it is a tool for 3D architectural
visualization.
Architects require knowledge in modeling, lighting,
animation...
But do they also need to know scripting?
“One of the things that I keep saying to all my
students is that if they want to work with big and
complex projects in Blender, they must learn how to
work with Python to create custom tools and scripts
to accelerate the creation process. This is a rule
for……”, Allan Brito
Python for architects.
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
35
If you have the time and are interested, read this:
Redefining the role of computers in architecture: from
drafting/modelling tools to knowledge-based design assistants
Yehuda E. Kalay
School of Architecture and Environmental Design, State University
of New York at Buffalo, Buffalo, NY 14214, USA
Computer-Aided Design
Volume 17, Issue 7, September 1985, Pages 319–328
Want to know more about Python for architecture?
http://python.rhino3d.com/content/130-RhinoPython-primer
http://wiki.mcneel.com/developer/python
http://www.plethora-project.com/2011/09/12/rhino-python-tutorials/
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
36
I am interested in Engineering Systems
Design.
I do not like programming.
I would rather get a C or a D in this class
and get outta here!
But wait a minute my friend…..
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
37
Engineering Systems Design
How does one design large
transportation systems?
How does one find the optimal
path in a complex terrain?
How does one create and
implement efficient and effective
component supply chains across
multiple countries for complex
products such as aircrafts or ships?
Nearly all systems of today use computers in their design,
implementation and maintenance.
Optimization using Python
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
38
I am interested in Engineering Product
Design.
I do not like programming.
I would rather get a C or a D in this class
and get outta here!
But wait a minute my friend…..
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
39
Engineering Products Design
How does one design the controller for your car? Or for
the MRT train? Or for….
“Fortunately Python is a great tool for those looking to apply
the tools of science to product design.
Python can help with everything from statistical analysis, to
rapid development of viable products, to the creation of
complex models that can be used to tweak the levers of
growth,
and it’s easy to combine these with off the shelf tools that help
you analyze traffic patterns and figure out what product
changes actually make a difference. …” Mark Ramm for
EuroPython 2012
Python for control systems
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
40
Engineering Products Design: Sample optimization
problem
“The problem we present here is a paraboloid that is a function of two
design variables.
The optimization goal is to find the minimum values of this function
over the design space.
For the simplest form of this problem, there are no constraints, and we
assume that the analytical derivative of the objective function is
unavailable.”
Click here for details:
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
41
Engineering Products Design: Auxiliary Power Unit
“On Tuesday, investigators will convene in Tucson, Arizona to test and
examine the charger for the battery,
and download non-volatile memory from the APU controller, with
similar tests planned at the Phoenix facility where the APUs are built.
Other components have been sent for download or examination to
Boeing's Seattle facility and manufacturer facilities in Japan..”
Yahoo News January 21, 2013
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
42
Engineering Products Design: Sample Python script
from openmdao.main.api import Component
from openmdao.lib.api import Float
class Paraboloid(Component):
""" Evaluates the equation (x-3)^2 + xy + (y+4)^2 = 3 "””
# set up interface to the framework
x = Float(0.0, iotype='in', desc='The variable y')
y = Float(0.0, iotype='in', desc='The variable x’)
f_xy = Float(0.0, iotype='out', desc='F(x,y)')
Create models of
complex systems
Find optimal solutions
to problems
def execute(self):
""" Solve (x-3)^2 + xy + (y+4)^2 = 3
Optimal solution (minimum): x = 6.6667; y = -7.3333
"””
x = self.x
y = self.y
self.f_xy = (x-3.0)**2 + x*y + (y+4.0)**2 - 3.0
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
43
Hey! I have no problems with The Digital
World!
We live in it all the time.
Hence, I better learn what it is all about!
Yippe!
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
44
Let us now browse the course Web
site
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
45
Let us learn to use Tutor
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
46
Week 1: Cohort Session 2
Self Check Quiz
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
47
Check
Q1: I have written programs that
(a) are 1000 or more lines of code.
(b) are less than 1000 but around 100’s of lines of code.
(c) are very small.
(d) do not exist (never wrote one).
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
48
Check
Q2: The binary equivalent of decimal number 9 is
(a) 0101
(b) 1101
(c) 1001
(d) 1011
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
49
Check
Q3: If your mobile phone has 4KB of memory then it has
(a) 4000 bytes
(b) 4096 bytes
(c) 4000 bits
(d) 4096 bits
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
50
Check
Q4: When talking of computer memories, 1K corresponds to
(a) 1000
(b) 1023
(c) 1024
(d) 100000
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
51
Check
Q5: The base of the decimal number system is
(a) 4
(b) 2
(c) 10
(d) 8
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
52
Check
Q6: The base of the binary number system is
(a) 4
(b) 2
(c) 10
(d) 8
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
53
Check
Q7: A dual-core processor has
(a) 4 CPUs
(b) 2 CPUs
(c) 4 CPUs each with 16MB of RAM
(d) 2 CPUs each with 16MB of RAM
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
54
Check
Q8: Which of the following is NOT a computer programming
language
(a) Python
(b) Java
(c) Scratch
(d) MIT
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
55
Check
Q9: Which of the following is NOT a computer operating system
(a) Python
(b) OS X
(c) Windows 8
(d) Unix
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
56
Check
Q10: Which one of the following numbers cannot be represented in
one word of a computer that uses 4-bits/word to represent integers
using 2s complement.
(a) 5
(b) 3
(c) 16
(d) -1
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
57
Week 1: Cohort Session 2
January 28-Feb 1, 2013
Problem Solving and OO Programming
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
58
What is “problem solving?”
“Problem solving” refers to a set of activities
performed in order to solve a given problem.
This is a generic term and applies to all
disciplines, not only to Computer Science.
Sequence of steps for solving a problem as
proposed by George Polya in the 1950’s :
Understand the problem
Devise a plan [Design]
Execute the plan [Code,
Test etc]
Review solution
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
59
What is OO programming?
OO, or Object Oriented, programming refers to a set of activities that
lead to a computer program, written in an object-oriented language,
that when executed on a computer will solve a problem.
Python is an OO language used in SOPH 303.
Other OO languages include C++, Java, C#, Delphi, Modula, Oberon,
Objective C, Simula, Smalltalk, and many more!
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
60
What is Problem solving and OO programming?
Problem solving and OO
programming refers to a set of
activities that allow the mapping of
a problem to a computer program,
written in an object-oriented
language, that when executed on a
computer will solves the problem.
Understand the problem
Design a solution using objects
Implement the design in
an OO language
Test, debug, and correct
the program
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
61
Example 1: Problem solving
Problem:
Find the maximum in a given set of N integers.
Step 1: Understand the problem
1. We know what is a set, an integer and what does
“maximum” mean.
2. Can N be zero? Can N be negative? We assume that N>0.
3. Suppose the given set is: {4, -5, 29, 4}. N=4.
4. The maximum in this set is 29.
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
62
Example 1: Problem solving: Sequential program
Pictorial representation of a sequential algorithm:
Sequential
computation
Input: Given set
Find the maximum
Output: max integer in S
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
63
Example 1: Sequential program
Step 2: Design a sequential solution
1. Let S denote the given set.
2. Let S.next() denote the next element from the set. S.next()
is empty if we have examined all elements of S.
3. Let currentMax=S.next();
4. Scan each element of S until we have scanned all. The
following two steps are performed for each element in S
starting from the second.
a) Let newElement=S.next();
b) If currentMax<newElement then reset currentMax to
newElement;
5. Display currentMax, it is the desired maximum.
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
64
Example 1: Sequential program
Step 3: Implement the design as a well documented program in an
OO language
We will write a Python program later in this course.
Step 4: Test, debug, and correct the program
We will do this after we have written the program.
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
65
Example 3: Problem Solving
Problem:
Given real numbers a, b, and c, compute the value of the following
expression:
(b * b - 4 * a * c)
Step 1: Understand the problem
This one is easy! So let us say we have understood the problem!
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
66
Example 3: Problem Solving: Sequential Solution
Step 2: Design a sequential solution
1: Get a, b, and c.
2: Compute x=b*b
3: Compute y=4*a*c
4: Compute z=x-y
5: Compute p= z
6: Output p
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
67
Discussion
What differences do you notice in the two problems?
What impact would these differences have on a concurrent solution?
We solved the problem assuming a dual core computer. Would your
solution be different of it were to for a quad-core computer?
A concurrent program consists of sequential and concurrent steps.
Why? What impact do these steps have on the total time to solve a
problem on a multi-core computer?
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
68
Week 1: January 28-Feb 1, 2013
Python program compilation
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
69
The edit, compile, execute cycle
.Python file(s)
Edit a
Python program
.py file(s)
Compile your
program
Syntax
error
No syntax
error
Program correct
Execute your
program
Run time
Error or incorrect
output
In SOPH 303 we shall use IDLE for editing, compiling and execution. IDLE is a
development environment for Python programs.
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
70
Week 1: January 28, 2013
Hope you enjoyed week!
1/28/2013
The Digital World. Term 3. 2013. Week 1.
Session 1
71

similar documents