PowerPoint Presentation
Welcome
Thinking about Algorithms Abstractly
Jeff Edmonds
York University
Lecture 1
COSC 3101
Jeff Edmonds
www.cse.yorku.ca\~jeff\courses\3101
jeff@cse.yorku.ca
CSB 3044, ext. 33295
647-688-7413
‹#›
1
Welcome
Thinking about Algorithms Abstractly
Jeff Edmonds
York University
Lecture 1
COSC 3101
Attend either or both
(subject to seats)
‹#›
2
Welcome
Thinking about Algorithms Abstractly
Jeff Edmonds
York University
Lecture 1
COSC 3101
‹#›
3
Welcome
Thinking about Algorithms Abstractly
Jeff Edmonds
York University
Lecture 1
COSC 3101
‹#›
4
Welcome
Thinking about Algorithms Abstractly
Jeff Edmonds
York University
Lecture 1
COSC 3101
I am starting to panic.
I have never taught three sections before.
78+70+126 = 274 students!!!
Please help me.
For administrative questions:
Ask friends before asking me
Read, post and answer questions on the forum.
For remarking:
Ask 5 friends before asking me
Never ask me for more marks,
if the only reason is that you want/need them.
‹#›
5
Steps, Practice Tests, Unit Tests, Exam
Slides
Videos
Text
Extra Text: Cormen, Leiserson, Rivest, and Stein
“Introductin to Algorithms”,
Good to have, but not needed for this course.
Course Material
‹#›
6
Course Material
www.cse.yorku.ca\~jeff\courses\3101\syllabus
‹#›
Steps:
For each unit, I spoon feed you the key ideas from each unit
as a set of steps.
Learn them! Understand them!
With only them, you are on your way to passing.
Without them, you are on your way to failing.
Lectures consists of many examples of using these steps.
Practice Tests: Do them!
Text “How to Think about Algorithms”: If you prefer reading.
Course Material
‹#›
8
What do you think about 3101?
Was by far the hardest course ever.
I got the worst midterm mark ever.
I almost gave up.
But opened a door to such an interesting world for me.
Learned to see things abstractly and from different angles
After working a few years, I realized that 3101 was the most useful course I took.
‹#›
9
What do you think about 3101?
Hey Jeff,
Never thought I would say this but I missed you a little bit.
I was able to solve some interesting business programming problems – all by myself by just thinking back to the course.
The main thing I got out of the course is belief in higher self and the ability to relax.
If taken professionally, you weren’t kidding that the course would be helpful for us in life and not just academically.
‹#›
10
It deeply saddens me when a third of the class does not learn the material sufficiently to pass.
I will do everything in my power to help you learn this material.
I request that you do everything in your power.
A Contract to Learn
Everyone can learn it.
‹#›
11
The last few years
I threatened them every day.
They performed better than ever before!
And my course evaluations were better.
Tough Love
‹#›
12
Think about Algorithms
Abstractly
Devastated
by the midterm
Change your thinking now.
This course requires completely changing
the way you think about algorithms.
Though I keep warning people,
they tend not to get it until they are
‹#›
13
You spend 50hrs/week
on your programming courses.
Study Now!
Study the material deeply
before fail the tests.
‹#›
14
We will work you HARD:
5 practice tests
5 unit tests
Participation
An exam
Mark =
Marks
5%*4=20% 14%*4=56%
2% 10%
34% 78%
Σi=1..4 [ 0.05 Ti + 0.09 Max(Ti,E) ]
+ [ 0.02 P + 0.08 Max(P,E) ] + 0.34 E
0% (only threats)
4
Which is ever best for me!
Excess marks
go on the exam.
‹#›
15
5 unit tests:
Each unit test, half the class fails.
“Fail early, fail often”
Then almost everyone starts to listen and passes the exam.
Don’t want to people who fail the midterms to give up
Want people to work on the midterms
Marks
9% max(Ti,E)
5% Ti
5%*4=20% 14%*4=56%
‹#›
16
Class Participation:
Asking/Answering questions in class
Attending office hours
Talking to me outside of class
Submitting a photo *
Marks
Basically,
does he recognize you.
‹#›
17
Marks
Σi=1..4 [ 0.05 Ti + 0.09 Max(Ti,E) ]
+ [ 0.02 P + 0.08 Max(P,E) ] + 0.36 E
% P1 P2
T1 5% 60 25
Max(T1,E) 9% 70 95
T2 5% 80 30
Max(T2,E) 9% 80 95
…
Participation 2% 90 20
Max(P,E) 8% 90 95
Exam 36% 70 95
I get frustrated
reexplaining the marking scheme
‹#›
18
Marks
The tests will be during the tutorials.
Attend either (but not both).
It takes a lot of time to make a test
and it is very hard to make them the same difficulty
and hence the two sections will get the same test.
If you attend the first,
I wont let you pee or leave until 2:25.
And I will photograph who attends both sections.
‹#›
19
I think it is important for people
to not feel isolated
with the material.
Together
‹#›
20
You’re cool!
Are you free sometime this weekend?
Yes!
The best way to learn
is to teach each other!
Together
‹#›
21
Some students feel too intimidated to talk to the professor.
Actually, he is just a guy
who has been doing this for a while.
Together
‹#›
22
Office hours:
Before/after class tend to be the best time.
Longer or private questions, when requested,
can be taken back to my office, CSB 3044.
Together
‹#›
23
Sorry:
Given a problem
that the teacher knows a simple answer for
Determining how hard it will be for other people.
Is very HARD.
Together
Sure it is easy AFTER we see the solution!
Hindsight is 20-20!
I ALWAYS panic that I have made it too easy
and everyone will get perfect.
Then everyone fails.
‹#›
24
Pros
Don’t have to take notes.
Lower fear level that you will miss something.
Flexible to miss a class or two
if working, parenting, sick, …
Read/watch ahead to be prepared for a good discussion.
Read/watch after to review and as a reference.
Together
‹#›
25
Pros
REALLY good students might feel they don’t have to come to class (some might be right).
Cons
Cocky students will think they don’t need to come class
but are wrong.
Lazy students will use them as an excuse to skip class
and then never really get to them.
Test every other week!
Cant be delayed.
Together
‹#›
26
Please interact with me in class.
Help me know what people
are not understanding
Slow down the slides
(Though we do have
a lot of material to cover)
Together
‹#›
27
Please ask questions!
To keep the flow going
Wiggly hand:
relevant to current slide.
Stationary hand:
question about past material.
Avoid getting off topic.
Together
‹#›
28
When I ask a question
to the class.
Please don’t shout out answers.
So others can think.
Together
‹#›
29
In every class,
there is one student
I don’t like.
The key when talking in class is
Together
Are you trying to
help me and the class
or win some compitition?
‹#›
30
Winter 06, the average of one section was much higher
than the average of the other.
(I taught them both)
My theory was that it was because a student,
Gertruda, constantly asked great questions
and everyone learned from them.
Ask questions for everyone’s sake.
Please ask questions!
Together
10% of your mark is class participation!
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
‹#›
31
What:
Submit a photo on line
Add a photo to your forum account
If you would like a better rapport with your emails,
please include a photo.
Why:
I am very bad with names. (Sorry)
Emails and tests are effectively anonymous.
Needed for 10% participation mark.
You can see the class list.
How:
Submit
– cp photo.jpg Smith_John.jpg
– submit 3101Z photos Smith_John.jpg
(or line)
Submit a Photo
Together
‹#›
32
I communicate to you via the Forum.
You are also encouraged to talk to each other this way.
To be sure that you know when something has been posted,
it is important to subscribe to the course forum.
Forum
Be sure to subscribe to the course forum
and not just to one of its topics
Together
Both M&N
‹#›
33
When you email me something
– 3101 in topic
Together
‹#›
34
May I have a letter of reference for grad school?
Two years
from now:
I find it awkward to write letters for people that I don’t recognize.
Make yourself KNOWN today to SOME professor.
Together
‹#›
35
Sorry email does not help as I don’t remember names
May I have a letter of reference for grad school?
Two years
from now:
I find it awkward to write letters for people that I don’t recognize.
Make yourself KNOWN today to SOME professor.
Together
‹#›
36
HATE that doctors charge you for a doctor’s note.
And then it does not actually say that they know you were sick enough to have missed a test.
So dont tell anyone, but dont pay for a note for me.
Together
‹#›
37
So you want to be a computer scientist?
‹#›
38
Is your goal to be
a mundane programmer?
‹#›
39
Or a great leader and thinker?
‹#›
40
Original Thinking
‹#›
41
Boss assigns task:
Given today’s prices of pork, grain, sawdust, …
Given constraints on what constitutes a hotdog.
Make the cheapest hotdog.
Everyday industry asks these questions.
‹#›
42
Um? Tell me what to code.
With more sophisticated software engineering systems,
the demand for mundane programmers will diminish.
Your answer:
‹#›
43
Your answer:
I learned this great algorithm that will work.
Soon all known algorithms
will be available in libraries.
‹#›
44
Your answer:
I can develop a new algorithm for you.
Great thinkers
will always be needed.
‹#›
45
Course Content
A list of algorithms.
Learn their code.
Trace them until you are convinced that they work.
Implement them.
Worry about details.
class InsertionSortAlgorithm extends SortAlgorithm {
void sort(int a[]) throws Exception {
for (int i = 1; i < a.length; i++) {
int j = i;
int B = a[i];
while ((j > 0) && (a[j-1] > B)) {
a[j] = a[j-1];
j–; }
a[j] = B;
}}
‹#›
46
Course Content
A survey of algorithmic design techniques.
Abstract thinking.
How to develop new algorithms for any problem that may arise.
‹#›
47
Course Content
Goal: To provide a number of different notations, analogies, and abstractions within which to develop, think about, and describe algorithms.
‹#›
48
Levels of Abstraction
Given a concrete algorithm, eg. MergeSort
and a concrete input, eg. <4,2,6,1,7>
trace it and prove that it works.
Given a concrete algorithm, eg. MergeSort
and an abstract input, eg.
trace it and prove that it works.
Given a “Meta Algorithm”, eg. Iterative Algs
and an abstract input, eg.
trace it and prove that it works.
‹#›
49
Levels of Abstraction
Given a new computational problem on exam,
design a new concrete algorithm that solves it
following the “Meta Algorithm” steps.
If you do not get all the details of the new algorithm correct, it wont be a disaster.
If you do not get the steps of the “Meta Algorithm correct, it will be a disaster.
There are only a few “Meta Algorithms”
Learn them!
‹#›
50
Levels of Abstraction
“Meta Algorithms”
Iterative Algorithms
Recursive Algorithms
Greedy Algorithms
Recursive Back Tracking
Dynamic Programming.
NP-Completeness
‹#›
51
Levels of Abstraction
“Meta Math”
Existential and Universal Quantifiers
Asymptotic Growth
Adding Made Easy Approximations
Recurrence Relations
‹#›
52
Value Correctness
Don’t tack on a formal proof of correctness after coding to make the professor happy.
It need not be mathematical mumbo jumbo.
Goal: To think about algorithms in such way that their correctness is transparent.
‹#›
53
Study:
Many experienced programmers were asked to code up binary search.
‹#›
54
Study:
Many experienced programmers were asked to code up binary search.
80% got it wrong
Good thing is was not for a nuclear power plant.
‹#›
55
What did they lack?
‹#›
56
What did they lack?
Formal proof methods?
‹#›
57
What did they lack?
Formal proof methods?
Yes, likely
Industry is starting to realize that formal methods are important.
But even without formal methods …. ?
‹#›
58
What did they lack?
Fundamental understanding of the algorithmic design techniques.
Abstract thinking.
‹#›
59
Thinking Abstractly
The psychological profiling of a successful person is mostly the ability to shift levels of abstraction, from low level to high level.
To understand the detailed workings.
To understand the big picture.
Donald Kunth
‹#›
60
Thinking Abstractly
The psychological profiling of a successful person is mostly the ability to shift levels of abstraction, from low level to high level.
To understand the detailed workings.
To understand the big picture.
To understand complex things
in simple ways.
Donald Kunth
=
‹#›
61
Thinking Abstractly
Software developers view subsystems as entities with separate personalities, roles, and interactions,
not details of code.
vs
vs
It is hard to think of love
in terms of the firing of neurons.
‹#›
62
Thinking Abstractly
Better for communicating to friend
‹#›
63
Thinking Abstractly
A form that can peculate down and
dwell in your subconscious
where the miracle leaps of inspiration happen
Your subconscious
does not understand
JAVA code.
‹#›
64
Thinking Abstractly
Paradigm Shift
Is the black the form and the green the background?
Is the green the form and the black the background?
It is helpful to have different ways of looking at it.
‹#›
65
Course Content
Notations, analogies, and abstractions
for developing,
thinking about,
and describing algorithms
so correctness is transparent
‹#›
66
A survey of fundamental ideas and algorithmic design techniques
For example . . .
‹#›
67
Some Math
Recurrence Relations
T(n) = a T(n/b) + f(n)
Input Size
Time
Classifying Functions
f(i) = nQ(n)
Adding Made Easy
∑i=1 f(i).
Time Complexity
t(n) = Q(n2)
Logic Quantifiers
g “b Loves(b,g)
“b g Loves(b,g)
Logs and Exps
2a × 2b = 2a+b
2log n = n
‹#›
68
Iterative Algorithms
Loop Invariants
i-1
i
i
i
0
T+1
loop
exit when
codeB
codeC
9 km
5 km
Code
Relay Race
One step at a time
‹#›
69
Recursive Algorithms
?
?
‹#›
70
Graph Search Algorithms
‹#›
71
Network Flows
‹#›
72
Greedy Algorithms
NEED A PIC HERE
(NOT POOH)
‹#›
73
Recursive Back Tracking
‹#›
74
Dynamic Programing
‹#›
75
Reduction
=
Rudich www.discretemath.com
‹#›
76
Course Material
www.cse.yorku.ca\~jeff\courses\3101\syllabus
‹#›
Steps:
For each unit, I spoon feed you the key ideas from each unit
as a set of steps.
Learn them! Understand them!
With only them, you are on your way to passing.
Without them, you are on your way to failing.
Lectures consists of many examples of using these steps.
Practice Tests: Do them!
Text “How to Think about Algorithms”: If you prefer reading.
Course Material
‹#›
78
End
‹#›
79
Useful Learning Techniques
‹#›
80
Read Ahead
You are expected to read the lecture notes before the lecture.
This will facilitate more productive discussion during class.
Like in an
English class
Also please
proof read
assignments
& tests.
‹#›
81
Explaining
We are going to test you on your ability to explain the material.
Hence, the best way of studying is to explain the material over and over again out loud to yourself, to each other, and to your stuffed bear.
‹#›
82
Day Dream
Mathematics is not all linear thinking.
Allow the essence of the material to seep into your subconscious
Pursue ideas that percolate up and flashes of inspiration that appear.
While going along with your day
‹#›
83
Be Creative
Ask questions.
Why is it done this way and not that way?
‹#›
84
Guesses and Counter Examples
Guess at potential algorithms for solving a problem.
Look for input instances for which your algorithm gives the wrong answer.
Treat it as a game between these two players.
‹#›
85
Refinement:
The best solution comes from a process of repeatedly refining and inventing alternative solutions
Rudich www.discretemath.com
‹#›
86
This term we will provide
two hours a week of contact hours
with the TA.
Together
Ask me anything!
Class material
Help YOU solve the assignment questions.
Material missed from previous courses
Your love life
‹#›
87
This term we will provide
two hours a week of contact hours
with the TA.
Yes!
I will be sure
to attend.
Together
We can have
Practice Tests
Lectures
One-on-one time
Group discussions
‹#›
88
I will take attendance!
This will effect your
participation mark!
Yes!
I will be sure
to attend.
Together
‹#›
89
Sorry!
I will not have time
to mark the assignments.
This might be better anyway.
Together
But we can I read your solution together during the TA hours.
‹#›
90
Lets schedule the office hours now.
Together
‹#›
91
We will work you HARD:
6 assignments
5 practice tests
5 unit tests
Participation
An exam
Mark =
Marks
4%*5=20% 11%*5=55%
2% 10%
35% 78%
Σi=1..5 [ 0.04 Ti + 0.07 Max(Ti,E) ]
+ [ 0.02 P + 0.08 Max(P,E) ] + 0.35 E
0% -4%
0%
‹#›
92
5 unit tests:
Each unit test, half the class fails.
“Fail early, fail often”
Then almost everyone starts to listen and passes the exam.
Don’t want to people who fail the midterms to give up
Want people to work on the midterms
Marks
7% max(Ti,E)
4% Ti
4%*5=20% 11%*5=55%
‹#›
93
Class Participation:
Asking/Answering questions in class
Attending office hours
Talking to me outside of class
Submitting a photo *
Marks
‹#›
94
Marks
Σi=1..5 [ 0.04 Ti + 0.07 Max(Ti,E) ]
+ [ 0.02 P + 0.08 Max(P,E) ] + 0.35 E
% P1 P2
T1 4% 60 25
Max(T1,E) 7% 70 95
T2 4% 80 30
Max(T2,E) 7% 80 95
…
Participation 2% 90 20
Max(P,E) 8% 90 95
Exam 35% 70 95
‹#›
95
/docProps/thumbnail.jpeg