Algorithms and Python in Computer Science
undefined
undefined
THE ONLINE BOOK
CHAPTER I
GENERAL
INTRODUCTION
Problem solving
Given a problem, find a solution
Should be
Correct
Accurate
Complete
We want an algorithm
Why?
Once we have an algorithmic solution for a
problem, we can convert it into a program
Let a computer solves many instances of the
problem
Algorithms existed before computers existed
Euclid’s algorithm, …
Computers made them more important
What defines an algorithm
Must always produce the right result
Under all circumstances
Instructions should be well-defined
Anybody using the algorithm should obtain
the same answer
Should have a finite number of steps
Cannot run forever
These are not algorithms
On a shampoo bottle:
L
a
t
h
e
r
R
i
n
s
e
R
e
p
e
a
t
These are not algorithms
On a shampoo bottle:
L
a
t
h
e
r
R
i
n
s
e
R
e
p
e
a
t
H
o
w
m
a
n
y
t
i
m
e
s
?
These are not algorithms
On fuel tank cap:
T
u
r
n
u
n
t
i
l
t
h
r
e
e
o
'
c
l
o
c
k
These are not algorithms
On fuel tank cap:
T
u
r
n
u
n
t
i
l
t
h
r
e
e
o
'
c
l
o
c
k
A
m
b
i
g
u
o
u
s
!
Python
High-level interpreted language
Created by Guido Van Rossum
N
a
m
e
d
a
f
t
e
r
M
o
n
t
y
P
y
t
h
o
n
'
s
F
l
y
i
n
g
C
i
r
c
u
s
BBC comedy series of early 70’s
High-level languages
Have replaced assembler
Increase programmer’s productivity
Can run on multiple architectures
Intel/AMD and ARM
M
u
s
t
b
e
t
r
a
n
s
l
a
t
e
d
i
n
t
o
m
a
c
h
i
n
e
l
a
n
g
u
a
g
e
b
e
f
o
r
e
b
e
i
n
g
e
x
e
c
u
t
e
d
Two approaches
Compiled languages
Interpreted languages
Compiled languages
Programs written in old Fortran, C, C++ and so
go through a program that translates them into
directly executable code
T
h
e
c
o
m
p
i
l
e
r
D
o
i
n
g
g
+
+
m
y
p
r
o
g
r
a
m
.
c
p
p
–
o
m
y
p
r
o
g
r
a
m
p
r
o
d
u
c
e
s
a
n
e
x
e
c
u
t
a
b
l
e
f
i
l
e
c
a
l
l
e
d
m
y
p
r
o
g
r
a
m
t
h
a
t
c
a
n
r
u
n
a
n
y
t
i
m
e
No need to recompile
O
n
c
e
E
v
e
r
y
t
i
m
e
Advantages
The executable can run on any computer with
Same CPU instruction set
Same—or compatible—operating system
We can sell copies of the executable without
revealing the secrets of our program
Reverse engineering is possible but very
time-consuming
Interpreted languages
Languages like Python and Ruby are not
compiled
Translated again and again into bytecode
each time we execute them
Bytecode is interpreted by the language
interpreter
Python Interpreter:
translates and executes
the program
Source code
Results
E
v
e
r
y
t
i
m
e
Advantages
P
l
a
t
f
o
r
m
i
n
d
e
p
e
n
d
e
n
c
e
:
Bytecode can run on any platform for which
there is an interpreter
D
y
n
a
m
i
c
t
y
p
i
n
g
:
Same variable can refer to a string then an
integer then …
S
m
a
l
l
e
r
e
x
e
c
u
t
a
b
l
e
s
i
z
e
s
Disadvantages
P
o
r
t
a
b
i
l
i
t
y
l
i
m
i
t
a
t
i
o
n
s
:
Bytecode will not run on any machine on
which the interpreter was not installed.
S
p
e
e
d
:
Bytecode is not optimized for a specific
architecture
Just-in-time compilation introduces delays
C
a
n
n
o
t
s
e
l
l
c
o
p
i
e
s
o
f
a
p
r
o
g
r
a
m
w
i
t
h
o
u
t
r
e
v
e
a
l
i
n
g
i
t
s
s
o
u
r
c
e
c
o
d
e
A partial solution
In many cases, speed is not an issue outside of
loops than get executed thousand and
thousands of times
Loops inside other loops
C
a
n
r
e
w
r
i
t
e
c
o
d
e
f
o
r
t
h
e
s
e
i
n
n
e
r
l
o
o
p
s
i
n
C
a
n
d
i
n
c
l
u
d
e
t
h
i
s
c
o
d
e
i
n
t
o
a
P
y
t
h
o
n
p
r
o
g
r
a
m
U
s
e
P
y
t
h
o
n
C
A
P
I
Neither fish nor fowl
Java is compiled
Like C
into bytecode
Like Python
B
y
t
e
c
o
d
e
i
s
e
x
e
c
u
t
e
d
b
y
J
a
v
a
V
i
r
t
u
a
l
M
a
c
h
i
n
e
A comparison
C
o
m
p
i
l
e
d
l
a
n
g
u
a
g
e
s
T
r
a
n
s
l
a
t
e
o
n
c
e
t
h
e
w
h
o
l
e
p
r
o
g
r
a
m
i
n
t
o
a
n
e
x
e
c
u
t
a
b
l
e
F
a
s
t
Can run on any
machine having
same architecture
and same OS
I
n
t
e
r
p
r
e
t
e
d
l
a
n
g
u
a
g
e
s
T
r
a
n
s
l
a
t
e
p
r
o
g
r
a
m
s
l
i
n
e
b
y
l
i
n
e
e
a
c
h
t
i
m
e
t
h
e
y
a
r
e
e
x
e
c
u
t
e
d
M
u
c
h
s
l
o
w
e
r
Can run on any
machine having
the interpreter
installed
Programs
Specify a sequence of instructions to be
executed by a computer
The order of the instructions specify their order
of execution
Example
I
n
f
o
r
m
a
l
s
a
l
e
s
_
t
a
x
=
t
o
t
a
l
_
t
a
x
a
b
l
e
×
t
a
x
_
r
a
t
e
w
i
t
h
t
a
x
_
r
a
t
e
=
0
.
0
8
2
5
P
y
t
h
o
n
taxRate = 0.0825
salesTax = totalTaxable*taxRate
My first Python program
print("I add two numbers, 2 and 3")print(2 + 3)
It’s “print” and not “Print”
Cannot use smart quotes
Semicolons are optional and nobody uses them
Types of instructions
Input & output
name = input("Enter your name: ")
print("Hello! ")
Math and logic
celsius = (fahrenheit - 32)*5/9
Conditional execution
if celsius > 100 :
Repetition
for all lines in myfile:
Debugging
Finding what’s wrong in your program
F
i
n
d
i
n
g
t
h
e
p
r
o
b
l
e
m
Hardest
F
i
x
i
n
g
t
h
e
e
r
r
o
r
Types of errors
S
y
n
t
a
x
e
r
r
o
r
s
print("Hello!)# missing closing quotes
print("Hello!")# correct
A
b
i
g
a
n
n
o
y
a
n
c
e
Especially for beginners
Everyone ends better at it
Types of errors
R
u
n
-
t
i
m
e
e
r
r
o
r
s
/
E
x
c
e
p
t
i
o
n
s
Division by zero
A forgotten special case
Types of errors
S
e
m
a
n
t
i
c
e
r
r
o
r
s
Your solution is wrong
You expressed it poorly
taxRate = 8.25 # in percent!
salesTax = totalTaxable*taxRate
Experimental debugging (I)
Modify your program until it works?
Experimental debugging (II)
Look at your program
T
r
y
t
o
e
x
p
l
a
i
n
i
t
t
o
y
o
u
r
s
e
l
f
,
t
o
f
r
i
e
n
d
s
D
o
n
o
t
l
e
t
t
h
e
m
c
o
p
y
y
o
u
r
c
o
d
e
!
A
d
d
p
r
i
n
t
s
t
a
t
e
m
e
n
t
s
a
f
t
e
r
e
a
c
h
s
t
e
p
Remove them or better comment them out
when they are not needed anymore.
Experimental debugging (III)
Act as if you are investigating
a mystery
Natural and formal languages
Natural languages are complex, tolerate
ambiguities, often have to be taken figuratively
I am literally dying of thirst
Could you bring me a glass of water?
Formal languages are simpler, have much more
strict syntax rules, and want to be unambiguous
What they say will be taken literally
Natural language ambiguities
KIDS MAKE NUTRITIOUS SNACKS
STOLEN PAINTING FOUND BY TREE
QUEEN MARY HAVING BOTTOM SCRAPED
MILK DRINKERS ARE TURNING TO POWDER
SQUAD HELPS DOG BITE VICTIM
My first program
print("I add two numbers, 2 and 3")print(2 + 3)
It’s “print” and not “Print”
Cannot use smart quotes
Semicolons are optional and nobody uses them
Interactive Python
R
e
q
u
i
r
e
s
J
a
v
a
s
c
r
i
p
t
t
o
b
e
a
u
t
h
o
r
i
z
e
d
f
o
r
a
t
l
e
a
s
t
i
n
t
e
r
a
c
t
i
v
e
p
y
t
h
o
n
.
o
r
g
Commenting
Main purpose
To help human readers understand your
programs
Becomes more important as program sizes
grow
To record who wrote the program, when it
happened and so on
In-line comments
A
n
y
t
h
i
n
g
f
o
l
l
o
w
i
n
g
a
p
o
u
n
d
s
i
g
n
(
“
#
”
)
i
s
i
g
n
o
r
e
d
b
y
t
h
e
P
y
t
h
o
n
i
n
t
e
r
p
r
e
t
e
r
print ("Hello World!")
print ("Hello World!") # what to say?
r = d/2 # compute radius of circle
#Begin main loop
Multi-line comments
Anything between three double quotes—
"""
—is
ignored by the Python interpreter
""" Tell what the program does
Jehan-Francois Paris
Assignment # 1
COSC 1306 MW 2:30-4:00
Fall 2017
"""
At the beginning of each program
Introduction to algorithms and problem-solving in computer science, highlighting the importance of definitions and characteristics of algorithms. Exploring the significance of Python as a high-level interpreted language and its role in modern programming. Discussing high-level languages, their impact on productivity, and the need for translation into machine language for execution.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
COSC 1306 COMPUTER SCIENCE AND PROGRAMMING Jehan-Fran ois P ris jfparis@uh.edu Fall 2017
THE ONLINE BOOK CHAPTER I GENERAL INTRODUCTION
Problem solving Given a problem, find a solution Should be Correct Accurate Complete We want an algorithm
Why? Once we have an algorithmic solution for a problem, we can convert it into a program Let a computer solves many instances of the problem Algorithms existed before computers existed Euclid s algorithm, Computers made them more important
What defines an algorithm Must always produce the right result Under all circumstances Instructions should be well-defined Anybody using the algorithm should obtain the same answer Should have a finite number of steps Cannot run forever
These are not algorithms On a shampoo bottle: Lather Rinse Repeat
These are not algorithms On a shampoo bottle: Lather Rinse Repeat How many times?
These are not algorithms On fuel tank cap: Turn until three o'clock
These are not algorithms On fuel tank cap: Turn until three o'clock Ambiguous!
Python High-level interpreted language Created by Guido Van Rossum Named after Monty Python's Flying Circus BBC comedy series of early 70 s
High-level languages Have replaced assembler Increase programmer s productivity Can run on multiple architectures Intel/AMD and ARM Must be translated into machine language before being executed Two approaches Compiled languages Interpreted languages
Compiled languages Programs written in old Fortran, C, C++ and so go through a program that translates them into directly executable code The compiler Doing g++ myprogram.cpp o myprogram produces an executable file called myprogram that can run anytime No need to recompile
C program Once C compiler Executable Every time Computer Results
Advantages The executable can run on any computer with Same CPU instruction set Same or compatible operating system We can sell copies of the executable without revealing the secrets of our program Reverse engineering is possible but very time-consuming
Interpreted languages Languages like Python and Ruby are not compiled Translated again and again into bytecode each time we execute them Bytecode is interpreted by the language interpreter
Source code Python Interpreter: translates and executes the program Every time Results
Advantages Platform independence: Bytecode can run on any platform for which there is an interpreter Dynamic typing: Same variable can refer to a string then an integer then Smaller executable sizes
Disadvantages Portability limitations : Bytecode will not run on any machine on which the interpreter was not installed. Speed: Bytecode is not optimized for a specific architecture Just-in-time compilation introduces delays Cannot sell copies of a program without revealing its source code
A partial solution In many cases, speed is not an issue outside of loops than get executed thousand and thousands of times Loops inside other loops Can rewrite code for these inner loops in C and include this code into a Python program Use Python C API
Neither fish nor fowl Java is compiled Like C into bytecode Like Python Bytecode is executed by Java Virtual Machine
A comparison Compiled languages Translate once the whole program into an executable Interpreted languages Translate programs line by line each time they are executed Much slower Can run on any machine having the interpreter installed Fast Can run on any machine having same architecture and same OS
Programs Specify a sequence of instructions to be executed by a computer The order of the instructions specify their order of execution
Example Informal sales_tax = total_taxable tax_rate with tax_rate = 0.0825 Python taxRate = 0.0825 salesTax = totalTaxable*taxRate
My first Python program print("I add two numbers, 2 and 3") print(2 + 3) It s print and not Print Cannot use smart quotes Semicolons are optional and nobody uses them
Types of instructions Input & output name = input("Enter your name: ") print("Hello! ") Math and logic celsius = (fahrenheit - 32)*5/9 Conditional execution if celsius > 100 : Repetition for all lines in myfile:
Debugging Finding what s wrong in your program Finding the problem Hardest Fixing the error
Types of errors Syntax errors print("Hello!) # missing closing quotes print("Hello!") # correct A bigannoyance Especially for beginners Everyone ends better at it
Types of errors Run-time errors/Exceptions Division by zero A forgotten special case
Types of errors Semantic errors Your solution is wrong You expressed it poorly taxRate = 8.25 # in percent! salesTax = totalTaxable*taxRate
Experimental debugging (I) Modify your program until it works?
Experimental debugging (II) Look at your program Try to explain it to yourself, to friends Do not let them copy your code! Add print statements after each step Remove them or better comment them out when they are not needed anymore.
Experimental debugging (III) Act as if you are investigating a mystery
Natural and formal languages Natural languages are complex, tolerate ambiguities, often have to be taken figuratively I am literally dying of thirst Could you bring me a glass of water? Formal languages are simpler, have much more strict syntax rules, and want to be unambiguous What they say will be taken literally
Natural language ambiguities KIDS MAKE NUTRITIOUS SNACKS STOLEN PAINTING FOUND BY TREE QUEEN MARY HAVING BOTTOM SCRAPED MILK DRINKERS ARE TURNING TO POWDER SQUAD HELPS DOG BITE VICTIM
My first program print("I add two numbers, 2 and 3") print(2 + 3) It s print and not Print Cannot use smart quotes Semicolons are optional and nobody uses them
Interactive Python Requires Javascript to be authorized for at least interactivepython.org
Commenting Main purpose To help human readers understand your programs Becomes more important as program sizes grow To record who wrote the program, when it happened and so on
In-line comments Anything following a pound sign ( # ) is ignored by the Python interpreter print ("Hello World!") print ("Hello World!") # what to say? r = d/2 # compute radius of circle #Begin main loop
Multi-line comments Anything between three double quotes """ is ignored by the Python interpreter """ Tell what the program does Jehan-Francois Paris Assignment # 1 COSC 1306 MW 2:30-4:00 Fall 2017 """ At the beginning of each program
