Class notes
Python notes unit 1 to 5
- Course
- Institution
In this document there is python notes of unit 1 to 5 theorys.
[Show more]
Seller
Follow
laacheeeducation
Content preview
CHAPTER - 11.Introduction
Computer Science
Solving problems by use of computation is known as computer science.
Python
Python supports both procedural and object-orientedProgramming.
1.1 Essence of computational problem solving
To solve a problem computationally, two things are needed: i) a representation that captures all
the relevant aspects of the problem, ii) an algorithm that solves the problem by use of the
representation.Let’s consider a problem known as Man, Cabbage, Goat, Wolf problem (Figure
1.1).
Figure –1.1 Man, Cabbage, Goat, Wolf Problem
A man lives on eastern side of a river wishes to bring a cabbage, a goat, and a wolf to avillage on
west side of the river to sell. His boat is only big enough to hold himself,and either the cabbage,
goat, or wolf. Man cannot leave the goat alone with cabbage because goat will eat cabbage, and
he cannot leave the wolf alone with goat because the wolf will eat the goat. To solve this
gamethere is a simple algorithmic approach. Try all possible combinations of items that may be
rowed back and forth across the river. Trying all possible solutions to a given problem is referred
to as a bruteforce approach. A representation that leaves out details of what is being represented
is a form of abstraction.
Start state of the problem can be represented as follows.
man cabbage goat wolf
[W, E, W, E]
in which the symbol W indicates that the corresponding object is on the west side of the
river—inthis case, the man and goat. (The locations of the cabbage and wolf are left unchanged).
Second state is
man cabbage goat wolf
, [W, W, E, E]
Third state is
man cabbage goat wolf
[W, W, E, W]
and the final state is
man cabbage goat wolf
[W, W, W, W]
A solutionto this problem is a sequence of steps that converts the initial state,[E, E, E, E]in
which all objects are on the east side of the river, to the goal state ,[W, W, W, W]in which all
objects are on the west side of the river. Each step corresponds to the man rowing aparticular
object across the river (or the man rowing alone). Python programminglanguage provides an
easy means of representing sequences of values. Main task isto develop or find an existing
algorithm for computationally solving the problem.
1.2 Limits of Computational Problem Solving
Once an algorithm for solving a given problem is developed or found check “Cana solution to
the problem be found in a reasonable amount of time?”.If not, then the particular algorithm is of
limited practical use.
Figure-1.2 Traveling Salesman Problem.
The Traveling Salesman problem (Figure 1.2) is a classic computational problem in computer
science.The problem is to find the shortest route of travel for a salesman needing to visit a given
set of cities. In abrute force approach, the lengths of all possible routes would be calculated and
compared to find theshortest one. For ten cities, the number of possibleroutes is 10! (10
factorial), or over three and ahalf million (3,628,800). For twenty cities, thenumber of possible
routes is 20!, or over two anda half quintillion (2,432,902,008,176,640,000).
If we assume that a computer could compute thelengths of one million routes per second, it
wouldtake over 77,000 years to find the shortest routefor twenty cities by this approach. For 50
cities,the number of possible routes is over 10 64. In thiscase, it would take more time to solve
,than theage of the universe!For problems such as this and the Traveling Salesman problem in
which a brute-force approach is impractical to use, more efficient problem-solving methods must
be discovered that find either an exact or an approximate solution to the problem.
1.3 Computer Algorithms
1.3.1 What Is an Algorithm?
Analgorithmisdefinedasastepbystepprocedureto solveaproblem.
“An algorithmcanalsobe definedas a finite number of clearly described, unambiguous “doable”
steps.It can besystematically followed to produce a desired result for given input in a finite
amount of time (that is, it eventually terminates)”.
For eg,
Algorithms solve generalproblems (determining whether any given number is a prime number),
and not specific ones (determiningwhether 30753 is a prime number).
The word “algorithm” is derived from theninth-century Arab mathematician, Al-Khwarizmi,
who worked on “written processes toachieve some goal.” (The term “algebra” also derivesfrom
the term “al-jabr,” which he introduced.)
Computer algorithms are central to computerscience. They provide step-by-step methods of
computationthat a machine can carry out. Having high-speedmachines (computers) that can
consistently follow andexecute a given set of instructions provides a reliableand effective means
of realizing computation. However,the computation that a given computer performsis only as
good as the underlying algorithm used. Understanding what can be effectively programmedand
executed by computers, therefore, relies on theunderstanding of computer algorithms.
1.3.2 Algorithms and Computers: A Perfect Match
Most algorithms are not as simple or practical to apply manually. Most require the use of
computers either because they would require too much time for a person to apply, or involve so
much detail as to make human error likely. Because computers can execute instructions very
quickly and reliably without error, algorithms and computers are a perfect match!
1.3.3 Method for Developing anAlgorithm
(1) Define the problem: State the problem to be solved in clear and concisemanner.
(2) List the inputs and outputs
(3) Describe the steps needed to convert input tooutput
(4) Test the algorithm: Choose input data and verify that the algorithmworks.
1.4 Computer Hardware
, Computer hardware comprises the physical part of a computer system. It includes the
all-importantcomponents of the central processing unit (CPU) and main memory. It also includes
peripheralcomponents such as a keyboard, monitor, mouse, and printer.
1.4.1 Digital Computing: It’s All about Switches
Computer hardware must be reliable and error free. If the hardware gives incorrect results,then
any program run on that hardware is unreliable. A rare occurrence of a hardware error
wasdiscovered in 1994. ie.,Intel processor was found to give incorrect results only whencertain
numbers were divided, estimated as likely to occur once every 9 billion divisions. Still,
thediscovery of the error was very big news, and Intel promised to replace the processor for any
onethat requested it.The key to developing reliable systems is to keep the design as simple as
possible. In digitalcomputing, all information is represented as a series of digits. We are used to
representing numbersusing base 10 with digits 0–9. Consider if information were represented
within a computer systemthis way, as shown in Figure 1.3
Figure –1.3 Decimal Digitalization.
In current electronic computing, each digit is represented by a different voltage level. The more
voltagelevels (digits) that the hardware must utilize and distinguish, the more complex the
hardwaredesign becomes. This results in greater chance of hardware design errors. It is a fact of
informationtheory, however, that any information can be represented using only two symbols.
Because of this,all information within a computer system is represented by the use of only two
digits, 0 and 1, calledbinary representation as shown in figure 1.4.
Figure –1.4 Binary Digitalization
In this representation, each digit can be one of only two possible values, similar to a light
switchthat can be either on or off. Computer hardware, therefore, is based on the use of simple
electronic“on/off” switches called transistors that switch at very high speed. Integrated
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller laacheeeducation. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $8.59. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
78075 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now