Description: In this lecture, Dr. Bell introduces the theory of computation and explains some aspects of computational thinking. Programming languages are discussed, with an emphasis on basic Python syntax and data structures.
Take good notes.
This is a fast-paced course.
Position yourself to succeed!!
- Read psets when they come out and come back to them later.
New to something? PRACTICE. Try things out. PRACTICE.
(Since I already have worked with Python and coding before, I will probably have an easier time with this course than if I were an absolute beginner at programming.)
- Knowledge of Concepts
- Programming Skill
- Problem-Solving
- Represent knowledge w. data structs.
- iteration and recursion as computational metaphors
- abstraction of procedures and data types
- organize and modularize systems using object classes and methods
- different classes of algorithms, searching and sorting
- completity of algos.
Write code that is easy for others to understand. You YOURSELF will be wondering about what exactly you were thinking. LOL.
What does a computer do?
- Fundamentally:
- performs calculations (like a billion calcs per sec)
- remembers results (like 100s of gigabytes of storage)
- What kinds of calculations?
- built-in to the lang
- Ones that you define as the programmer
- Computers only know/do what you tell them.
Computers don't inherently know anything.
- Declarative knowledge is statements of fact.
- Imperative knowledge is a recipe or a "how to"
The IDE that the instructor is using in this class in Anaconda. However, I may use something else, like this Linux VM on my laptop:
In this example, I am generating random nums using Python in my terminal. This would be useful if I need a random number.
When you are faced with a problem in your everyday life, consider whether using a computer would enhance your ability to solve it.
When it comes to building a recipe (imperative knowledge) you need
- A sequence of simple steps
- Flow of control process that specifies when each step is executed.
- A means of determining when to stop.
1+2+3 = an algo!
Back in the day, there were fixed-program computers, like calculators (add, subtract, mult, divide, etc.)
Now, we also have stored program computers, where the machine stores and executes instructions. This is the modern computer.
Basic Machine Architecture
- Memory (holds data and sequence of instructions)
- Arithmetic Logic Unit (do primitive ops)
- I/O
- Control Unit.
With control flow a program may or may not progress linearly, but it may "jump" around from one part of the instructions to another and back, etc. Skip a line. Repeat a line, etc.
When the last instruction is finished, you might output something.
That is the basic way a computer works.
- Secuence of instructions stored inside computer
- Build from predefined set of primitive instructions
- Arithmetic & logic
- Simple tests
- Moving data
- Build from predefined set of primitive instructions
- Special program (interpreter) executes each instruction in order
- Use tests to change flow of control through the sequence
- Stop when done.
Alan Turing said that you can compute anything using 6 Primitives
- Move left
- Move right
- Read
- Write
- Scan
- Do nothing
Using those 6 and a piece of tape, he showed you can compute anything.
Programming langs derived/descended from these basic building block steps.
If you can compute x in one programming lang, you can also do it in another lang.
- A programming lang provides a set of primitive ops
- Expressions are complex but legal combinations of primitives in a programming lang
- Expressions and computations have values and meanings in a programming lang.
https://www.techtarget.com/whatis/definition/primitive#:~:text=1)%20In%20computer%20programming%2C%20a,sophisticated%20program%20elements%20or%20interfaces.
Definition of primitive.
Let's use the English language as a parallel to computer languages.
Primitive constructs
- English:words
- Programming language: numbers, strings, simple operators.
Your expressions need to be syntactically valid.
Think about the MEANING of the phrase.
For computers, there is only 1 meaning. It might be something you did not intend. But there is really only one meaning to a programming expression.
ERROR CODES ARE YOUR FRIEND. They help you identify bugs and learn.
Programs manipulate data objects.
Objects can have a type that defines the kinds of things programs can do with them.
Objects are
-
Scalar (cannot be subdivided)
- e.g. INT like
5.
- e.g. INT like
-
Non-Scalar (have internal structures that can be accessed)
- e.g. LIST like
[5, 6, 7, 8]
- e.g. LIST like
All py objects have a type.
Everything is an object in Python.
You can cast objects from one type to another
print()
The print() function is one of the most basic. It shows the user what is passed through it.
Operators
To assign a value, use the =
x = 2 + 45
We give names to values of expressions in order to reuse the NAMES instead of the VALUES. It enables our code to look a lot nicer.
If you want the computer to solve for x, then you need to tell the computer exactly how to do it.
radius = radius + 1
...and radius is no longer bound to 2.2. So watch out!!
How to add control flow to our programs
NOTE: Slides and code files up before each lecture
- Highly encouraged to download them b4 lecure
- Take notes and run code files when instructor does.
- Use computer to answer in-class practice exercises.