Explore
For Enterprise
Join for Free
Log In

艺术与人文
商务
计算机科学
数据科学
信息技术
健康
数学和逻辑
个人发展
物理科学与工程
社会科学
语言学习
學位和證書

瀏覽 Coursera 的全部課程

瀏覽
搜索
企業版
登錄
免費加入

Counting and Sums

Loading...

计算原理（第 1 部分）

4.8（444 個評分） | 21K 名學生已註冊

課程 3（共 7 門，计算机基础專項課程）

This two-part course builds upon the programming skills that you learned in our Introduction to Interactive Programming in Python course. We will augment those skills with both important programming practices and critical mathematical problem solving skills. These skills underlie larger scale computational problem solving and programming. The main focus of the class will be programming weekly mini-projects in Python that build upon the mathematical and programming principles that are taught in the class. To keep the class fun and engaging, many of the projects will involve working with strategy-based games. In part 1 of this course, the programming aspect of the class will focus on coding standards and testing. The mathematical portion of the class will focus on probability, combinatorics, and counting with an eye towards practical applications of these concepts in Computer Science. Recommended Background - Students should be comfortable writing small (100+ line) programs in Python using constructs such as lists, dictionaries and classes and also have a high-school math background that includes algebra and pre-calculus.

查看授課大綱

您將學習的技能

Computer Programming, Algorithms, Python Programming, Combinatorics

審閱

4.8（444 個評分）

5 stars
372 ratings
4 stars
57 ratings
3 stars
12 ratings
1 star
3 ratings

IB

Jun 12, 2017

Yay, no more peer grading! This course felt easier than intro2. Less fiddling with your programs and more about concepts.

JG

May 29, 2016

Awesome course! Recommend to newcomers and intermediate alike. The instructors are great and the content is challenging.

從本節課中

Counting, growth of functions, higher-order functions

This week, we will explain the importance of counting in solving complex problems.

The Importance of Counting 4:29

Counting and Sums14:15

Functions: Finding the Max 9:50

Higher-order Functions 11:06

Plotting Statement Counts13:57

教學方

Scott Rixner
Professor
Joe Warren
Professor
Luay Nakhleh
Associate Professor

腳本

[MUSIC]

Welcome back.

In this video lecture we're going to talk about

understanding the efficiency of the Python programs that you've built.

When you click Run, Python executes your

programs and takes your input and builds answers.

Right now that's probably somewhat of a mystery to you.

We're not going to get really specific here.

We're just going to kind of learn to build a ballpark estimate of how

long it takes Python to compute the answers from the inputs that you give it.

Ideally we'd like to develop some understanding where if

we look at the inputs, we can roughly predict

how long your program will take to run, in

terms of some formula of the size of those inputs.

We're not going to get super precise in principles of computing.

In algorithmic thinking, we'll actually get much more precise in terms

of compute determining the efficiency of the programs that you're building.

In this one, we're just going to get a ballpark estimate.

I'm going to start by kind of looking at a, at a of

humorously example of learning how to count, to estimate the size of something.

Okay, let's start off by considering this giant pile of cash.

This is the money that Scott and I have

made from teaching an Introduction to Interactive Programming in Python.

Okay, that's not really true.

We can put in a good picture of this with

empty room with few dusty $20 bills sitting on the floor.

This is actually a giant pile of cash seized from a Mexican drug lord.

It was probably the, the inspiration for the giant

pile of cash that Walter White had in Breaking Bad.

So the first thing that I, thought when I actually

saw this pile of cash was, how much money is that?

That's a heck of a lot of money.

So, when we talk about counting and trying to estimate things.

I'm going to show you an example here of how we

can actually estimate how much money is here surprising accurately.

The first thing we need to figure out is

we have all these little packets of money here.

So those are hundred dollar bills.

And it turns out they're strapped together in bundles of a hundred.

So we have $10,000 in each one of these little packets.

Okay.

Well, how many packets are there?

Looks like there's a lot of them.

So, we could just observe this as kind of a big giant brick.

So we can estimate the number of packets by computing

kind of the width times the height times the depth.

So let's do that so there's kind of like five, ten,

15, 20, 25, 30, 35, 40, 45, maybe 50 packets wide.

Maybe let's see, five, ten, 15, 20, 25, 30 maybe, 30 packets high.

Then five, ten, maybe 15 packets deep.

So we can actually just go out there and let's

just go to CodeSkulptor and just print out what that is.

So it's 10,000 times 50, times 30, times 15.

Let's run that.

Well the answer is 225 million.

So I actually looked up how much money was here

and it turns out there was actually $209 million here.

So what we kind of this example points out is you can actually do a

surprisingly good job of, of estimating something that

you think you have no chance at it.

If you just follow a few simple principles.

So what we're going to do here is I'm going to talk about trying to

estimate the number of statements that are executed

when you hit Run in your Python program.

So let's get down to business.

[BLANK_AUDIO]

So let's look at the problem of trying to estimate the number of

statements that are executed in your Python

IDE whenever you click the Run button.

So I've got kind of a sample program here.

And it's sitting here in CodeSkulptor.

In fact, we're sitting inside Viz mode.

So I want to show you what I mean when I'm talking

about trying to kind of measure the, the requirements of your program.

So if I click Run here what happens

is Code Skulptor went through and executed this program,

and Viz mode made a trace that recorded each

statement that was executed when we ran the program.

So if you've used the, the Viz mode before,

we start off, we're getting ready to ex, getting

ready to execute statement seven, we click, we go

forward to eight, to nine, we go to twelve.

We skip into thirteen, we skip fourteen.

Then we go down to this loop.

And we click the loop, and we actually execute the loop ten times.

So notice what happens here is when we clicked Run, CodeSkulptor went

through and executed this Python programming

statement one statement at a time.

Now the important thing to note here is

this is somehow doesn't really exactly capture how long

it takes to run the program because, it

depends on things like how fast your computer is.

How fast your browser actually executes the

JavaScript that your Python is translated into.

How skillful the people that wrote Skulpt, the engine for CodeSkulptor, were.

So we're only trying to really kind of figure out kind of what we

can control, which is kind of, kind of how our Python program is executed.

And for now, we're going to just consider it a statement level.

That kind of gives us a ballpark estimate that will allow us to

actually form some thoughts about whether we have a good or bad program.

Okay, so now I can be more precise about what we really like to do.

What I want to develop is kind of a process that lets me

to look at the structure of my program, and derive a formula

that estimates the number of statements that will execute based on the

structure of the program, and the values that we feed to that program.

So, for this simple example here, we can actually make some headway.

For straight line code it's very easy

to estimate the number of statements we execute.

Just go bam, bam, bam right through here, we do three prints.

For conditionals we can kind of estimate how

many statements we're going to execute inside a conditional.

We can just kind of take the maximum of the statements inside each of the

two branches, or we can add them, remember we're going for a ballpark estimate here.

The critical thing is for things like

straight line coding conditionals, kind of the size

of your program kind of gives you about

how many statements you will have to execute.

However, if we get down to this loop, things get a little trickier.

Okay, we are getting execute this loop, and we jump in there

and we print one test, we print two test, we print three test.

We bang along here and we actually end up executing this loop ten times, okay.

So, could we make that trace longer?

Will we make the number of steps, statements we execute longer?

Well we could change this to 100.

And we could fire it up, and, wow.

We have 100 prints here.

And our trace is probably like more than 200 statements long.

So, somehow it's not just the size of the program it's

also some of the values that we give in to the program.

And in fact loops are kind of the,

the first place we're going to see some trickiness

and try to understand kind of, how much

computation is done when you run your program.

So what I want to do is we're going to actually look at kind of

analyzing kind of the, how many statements are executed when you run a loop.

And this will lead into some kind of simple mathematics that you will need

to know to help do the analysis we're going to need to do in this class.

Okay, let's look at some examples involving loops.

So, in the second half of the file that I've given you,

we have three functions whose bodies are either loops or pairs of loops.

And, the reason I have written these as functions is

because I want to emphasize the point that the number of

statements that are executed whenever we evaluate these loops, will

depend on the input values that we give those functions.

So we're trying to emphasize input values, give us

some way to estimate, the running time of our program.

That's what we're going to be shooting for as we move forward.

So let's look at this first function here, test1.

Its body simply consists of a, of a loop, that takes

the input value and prints out test1 that number of times.

So we see here, we gave it four.

It printed out test1 four times.

I could change this to ten and guess what?

It's going to print out test1 ten times.

So looking at this really simple loop, we can

very easily estimate the number of statements we're going to execute.

The number of times we're going to print out test1.

By just giving a little simple math here, we

give it n, it's going to print out test1 n times.

The number of statements it's going to execute, well it's kind of

twice that, maybe we execute to four, then we execute to print.

But really, the critical thing is it's growing linearly as this parameter here.

Alright, let's look at a second example.

So the second example, test2, has a pair of nested loops.

In this one we give it a value, and

this index1 ranges from there, from zero to that value.

The interloop then range, ranges from zero to index1 plus 1.

So for example if we give this the value one, it will print out test2 once.

If we give it two, it will print out test2 three times.

If we give it three, it print out test2 six times.

If we give it 4, it'll print out test2 ten times.

So, what's happening here?

Well, when we run test2, this inner loop is being executed

one time, then two times, then three times, then four times.

So, if we add up all the executions for all four times to

the outer loop, it's 1 plus 2 plus 3 plus 4, or ten.

So what you can see here is, we've built a sum that

helps us understand how many times this pair of nested loops is executed.

So we're going to do later in the lectures

is I'm going to walk through some of the simple

sums that you'll need to do, need to know to do analysis just like I've shown you.

Okay, let's look at this last example.

So in the last example, we're, outer loop is

iterating from, again, from zero to the input value.

But the inner loop is doing some exponential of this index.

So for example, when we start out, let's run this on one.

We can see is test3 actually was printed once.

That's because the initial value here is going to be zero.

We take 2 to the 0, that's 1, so we print this out exactly once.

Change this to two, and see if we can figure out what's going on.

So we change it to two, and we see test3 three times.

That's because this inner loop executes once, 2 to the 0,

then a second iteration, it executes two times, 2 to the first.

So let's see.

If we change this to three, I'm going to guess that it's

going to execute seven times, it's going to be 1 plus 2 plus 4.

So, there it is, 7 times.

So, what this is, is actually going to

be a sum of numbers that are growing exponentially.

So again, we need to look at some more sums to understand how those things grow.

So, what I want to do now is that we're going to actually go over to a

class web page where I kind of walk you

through the basic math of doing arithmetic sums.

All right, let's finish off lecture by looking at some common arithmetic sums.

So I've built a class page that contains a kind of small set of notes that you

can review and kind of parse to understand the basics of the math you will need here.

The most critical thing is that you need to understand

the common notation that mathematicians use for writing a sum.

If we have a sequence of numbers that are indexed

by some index i, maybe a0, a1, a2, and so

forth, use a subscript for that, we can express the

sum of all those numbers by using this sigma here.

Where kind of the subscript says the index from sum lower bound to sum upper bound.

So here zero is the lower bound for the sum, n is upper bound for the sum.

As opposed to Python we always include both the

lower bound and the upper bound inside the sum.

So here are some examples of some common sums that you might find in this class.

This kind of corresponds to the loop test1 here.

We do a constant amount of work inside each iteration of the loop.

And we have n plus 1 iterations of the loop.

Well, what comes out is we have n plus 1, so the sum of numbers

1 plus 1 plus 1 plus 1, n plus 1 times is exactly n plus 1.

Here's a second one.

This might come up if you had a pair of nested loops.

In this particular case we're taking the number n

and we're adding it together n plus 1 times.

So it's no surprise the answer is n plus 1 times n.

Notice this is a quadratic expression and this is a quadratic polynomial and it, so.

Much of the time, whenever we're trying to estimate the

running time of a program, we'll actually just worry about

mainly kind of a very rough expression of what the,

kind of the, the formula is for that running time.

Look at things like, is it linear, is it quadratic, is it exponential.

So we're not going to worry the, kind of the small details too much.

Here's another example.

This is the example for Test2.

In this particular case, we are adding up the numbers 1, plus 2, it's

actually 0, plus 1, plus 2, plus 3, all the way up to n.

So this is called a triangular sum, and the formula is one half n plus 1 times n.

The critical thing again is quadratic and n.

The one half again is not as important.

The main thing is, it's quadratic in n.

So for example if we double n, the fact that it's quadratic

means that the sum would actually grow by a factor of four.

Here's another example.

This is called a geometric sum down here.

We're adding up 1 plus 2 plus 4 plus 8 plus 16.

It turns out there's a very simple formula here.

1 plus 2 plus 4 plus 8 plus 16 is exactly 32 minus 1.

There's a few more formulas down here.

There's formulas for what's called a harmonic series.

You'll actually use that in the homework so my

suggestion is you read over this fairly quick, fairly carefully.

You don't have to remember the solutions for the sums, you just

have to know where they are so you can look them up.

Because you will be applying them every now and then inside the class.

Okay, I'll see you next lecture.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2019 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取

Coursera
關於
管理團隊
工作機會
目錄
證書
MasterTrack™ 證書
學位
企業版
政府版

社區
Learners
Partners
Developers
Beta Testers
Translators

連接
博客
Facebook
領英
Twitter
Instagram
YouTube
技術博客

更多
條款
隱私
幫助
內容訪問
媒體
聯繫我們
目錄
附屬公司