EECS3101
EECS 3101: Design and Analysis of Algorithms
Jeff Edmonds
Passion:
Often, I want to share my excitement about something like
Angular Momentum and few people have interest.
They might want to share their excitement about astrology
and I try to show interest.
I find it much
easier to find people who want to teach then to find people who want
to learn.
I always figure that I should have to pay my York students
to listen to me - not the other way around.
But for wanting me to deal with you wanting a higher mark - for
that the students need to pay.
Jeff,
Readme,
*
Course Info
*,
Times,
Dates,
Course Description,
Mental Health,
EClass,
Zoom,
Forum,
Partner,
All.zip,
New
Videos
About Course:
This course teaches how to think about algorithms in an abstract way
so that one can talk about them, design new ones, and know that they
are correct. Though Jeff will cover various algorithm as examples,
the goal really is to teach the students to think abstractly about the
key meta-algorithm techniques that everyone should know. These
techniques are abstract enough to apply to most any problem that you
will face in your job and in your life. Jeff has had many graduated
students tell him that his courses were the most useful they had ever
taken.
Request:
Jeff tends to talk too fast. Please help him go
pole pole slowly.
Readings:
Power Point Slides
5
Video from previous year (5 mins)
5 Video from this year (5 mins)
Video covers more than needed.
Video Missing
Pooh
Introduction
(ppt)
?
Administrative Details
52
General course description
(HTA 0; LN 0,1; CLRS1)
How to Study
Watch, Pause, Think, and Unpause the videos.
Watch in the video the pre and post conditions for the next problem.
Pause the video and try to solve it yourself.
If you get stuck, watch the slide for another slide or two.
Repause it. Was that enought of hint so that you can now solve it?
After watching the entire solution, ask yourself what you were missing.
How did Jeff complete the steps?
Maybe set all notes aside and see if you can now write up the solution on your own.
Unit 0:
Relevant Mathematics
(0 hours: blended with in)
logic.pptx,
math.pptx,
steps,
practice,
practice sol,
fun
Before a student can understand or prove anything in mathematics, it
is essential to first be able to represent it in first order
logic. Hence, Jeff reviews it in each of his courses. We also look at
asymptotic of running times, solving recurrence relations, and
summations.
lots
Existential and Universal Quantifier (HTA 22)
13
Time Complexity of Algorithms (HTA 23; LN 1; CLRS 2)
Logarithms and Exponentials (HTA 24
Asymptotic Notations (HTA 25; LN1; CLRS 3)
27
Summations: arithmetic, geometric,
harmonic (HTA 26; CLRS A)
Recurrence Relations (HTA 27; LN 2;CLRS 4)
WATCH ABOVE BY Mon J11
Unit 1:
Loop Invariants for Iterative Algorithms
(6 hours)
ppt,
steps,
practice,
practice sol
Jeff strongly believes that this is the most important topic in
Algorithms. Instead of worrying about the entire computation, only
worry about one step at a time - make progress while maintaining the
loop invariant.
32
Actions vs Invariants
16
Proof Using Loop Invariants
5
Code vs Math Assertions
5
Physics and Life
19
Physics Spring
WATCH ABOVE BY Wed J13
13
Home to School Story
19
Recap of Proof of Meta Algorithm
13
Define Assertions and Measures
20
Code from LI
20
Pointers
3
Views of Algorithms
WATCH ABOVE BY Mon J18
23
Insertion Sort
11
Selection Sort
11
Don't Redo Work
9
Designing an Algorithm
12
Finding Errors
59
Fairy God Mother (Lake)
11
More of Input (Insertion and DFA)
WATCH ABOVE BY Wed J20
21
More of Output (Selection, Blocks, Konig)
24
Narrowing the Search Space
7
The Partition Problem
33
Shrinking Instance (GCD) (Running Time)
WATCH ABOVE BY Mon J25
51
Multiplying
19
Data Structure (System) Invariants
13
Bucket (Quick) Sort for Humans
24
Radix/Counting Sort
6
Lower Bound for Sort
Practice Solutions
- 3
75
Cake Cutting
- 5
46
Sorted Matrix Search
- 7
36
Connected Components
- 8
12
Tornament
- 9
41
Euler Tour
WATCH ABOVE BY Wed J27
TEST 1 Loop Inv 1 J29 8am-8am (class 4pm)
TEST 2 Loop Inv 2 F05 8am-8am (class 1pm)
Unit 2:
Recursive Algorithms
(6 hours)
(ppt,
steps,
practice,
practice sol)
Again do not try to understand the entire computation. Trust your
friends to solve a smaller instances of your problem and use these to
the solve your own instance.
7
Merge Sort
11
Multiplying (mp3,HTA 92; CLRS 282,30,31)
44
Recurrence Relations (HTA 27; LN 2;CLRS 4)
6
Stack Frames
7
Friends and Strong Induction (HTA 8;CLRS 23, 334)
21
Input Size
WATCH ABOVE BY Mon F01
9
Exponential Growth
19
Towers of Hanoi
6
Check List
14
Merge & Quick Sort
26
(Probabilistic Algorithms)
12
Power
WATCH ABOVE BY Wed F03
56
Simple Recursion on Trees (HTA 31,10)
7
Generalizing the Problem
13
Things not to do
3
Heap Sort & Priority Queues (HTA 91; LN 2,4; CLRS 7,9)
9
Trees Representing Equations
3
Pretty Print
2
Depth First Search
21
Parsing with Context Free Grammars (HTA 12)
9
Recursive Images (HTA 11)
7
Ackermann's Function (HTA 11)
WATCH ABOVE BY Mon F08
TEST 3 Recursive 1 F12 8am-8am (class 4pm)
TEST 4 Recursive 2 F26 8am-8am (class 1pm)
Unit 3:
Graph Search Algorithms
(4.5 hours)
ppt,
practice,
practice sol,
Lots
of Videos about Graphs
Graphs, ie nodes and edges, are very useful for representing
data. The first task on them is to search through the nodes.
2
Review definitions and graph terminology (HTA 31;CLRS B)
26
Generic Search
8
Breadth-First-Search (BFS) and shortest paths (HTA 141, 142; CLRS 222)
WATCH ABOVE BY Wed F10
40
Dijkstra's Shortest Paths (HTA 143; CLRS 24)
25
Depth-First-Search (DFS) (HTA 144, 145; CLRS 223)
15
Linear Order (Dags and topological sorting) (HTA 146; CLRS224)
Network Flow
(3 hours)
ppt
This is how to best transport goods from factories to stores. We
briefly mention Linear Programing which is extremely useful in
industry, eg What ingredients put in your hamburger today to minimize
its cost.
4
Optimization Problems Definition (HTA 13)
9
Network Flow Defn (HTA 15;CLRS 26)
5
Simple Example
8
Application: Matching
WATCH ABOVE BY Mon F22
5
Flow Strategy
3
Hill Climbing
23
Augmenting Flow
14
Primal-Dual Hill Climbing
4
Min Cut
10
Max Flow = Min Cut
3
Running Time
18
Linear Programming
WATCH ABOVE BY Wed F24
TEST 5 Graph M05 8am-8am (class 4pm)
Unit 4:
Greedy Algorithms Methods
(4.5 hours)
ppt,
steps,
practice,
practice sol
These are the simplest possible algorithms. Proving they work,
however, is hard.
2
Formal vs Informal
23
Greedy Algorithms
29
Proving with Loop Invariants
22
Three Players making Change
WATCH ABOVE BY Mon M01
30
Maintaining the Loop Invariant
45
Event Scheduling (HTA 162)
1
Review and Don'ts
41
Minimum Spanning Tree (HTA 1623; CLRS 23)
WATCH ABOVE BY Wed M03
15
Adaptive Greedy
19
Interval Point Cover
60
Communication and Entropy
8
Forced Horn Clauses
Practice Solutions
- 1
23
Fractional-Knapsack
- 3
105
49
River Stone Jumping
- 4
34
Event Multiple Room
WATCH ABOVE BY Mon M08
TEST 6 Greedy M19 8am-8am (class 1pm)
Unit 5:
New Dynamic Programming
(6 hours)
So far I only have slides ppt
Shortest Path: A harder instance is solved by filling out a table of solutions for
easier sub-instances.
Other Problems: Reduce to Shortest Path
Key Concepts:
Bird & Friend
Recursive Backtracking
Dynamic Programming
Bird Friend Algorithm
Life Story Graph
Shortest Path:
Dynamic Prog vs Dijkstra
Bird & Friend Algorithm
Loop Invariant
Try all Bird Answers
Take the Best of the Best
Construct Optimal Path
Table
Short Code
Excel
Code
Running Time
Graph of Life
Loop Invariants
DFA
Your Story
Keep # of States Small
Table
Actions/Edges
Path Through Life
Cost of Solution/Path
Weight of Edge
Optimal Substructure
Little Bird Specifies Action
Solutions = Path
Reduction to Shortest Path
Running Time
Game of Life Examples
Printing Neatly
+ (#lines)^2
Longest Common Subsequence
Knapsack Problem
Event Scheduling
Buying Stocks
Failed Algorithm
Non-Game of Life Examples
All Pairs Shortest Paths
Review
Question for Little Bird
Set of Sub-Instances
Optimal Substructure
Failed Algorithm
Parsing
Satisfiability
Unit 5':
OLD Dynamic Programming
(6 hours)
ppt,
steps,
practice,
practice sol
A harder instance is solved by filling out a table of solutions for
easier sub-instances.
42
All Pairs Shortest Paths (HTA 196; CLRS 25)
9
Best Path
Steps:
3
A Sequence of Decisions
WATCH ABOVE BY Wed M10
13
The Little Bird & Friend
8
Recursive Backtracking
13
Memoization
8
Set of Sub-Instances
2
Tracing Dyn. Prog. Alg
15
Communication
14
Code
WATCH ABOVE BY Mon M15
12
Reversing
12
Speeding Up Running Time
1
Multiple Opt Solutions
3
Review
15
Question for Little Bird
WATCH ABOVE BY Wed M17
6
23
Optimal Substructure
38
Printing Neatly
39
Longest Common Subsequence (HTA 191)
WATCH ABOVE BY Mon M22
50
Knapsack Problem
15
The Event Scheduling Problem (HTA 193)
23
Parsing (HTA 198)
Satisfiability
Practice Solutions
- 4
87
Stock Market
WATCH ABOVE BY Wed M24
TEST 7 Dyn Prog 1 A02 8am-8am (class 4pm)
Unit 6:
Reductions and NP-Completeness
(HTA 20; CLRS 34) (3 hours)
ppt,
practice,
practice sol
Reductions involve writing an algorithm for one problem from that for
another. NP-Completeness give strong evidence that most search
problems that industry cares about are believed to not have poly-time
algorithms.
84
NP-Reductions (Quick)
WATCH ABOVE BY Mon 29
31
History & Overview
7
Course vs Schedule
14
More about Reductions
10
Circuit vs Airplane
24
Circuit vs 3-Colouring
31
Definition Review
WATCH ABOVE BY Wed M31
TEST 8 Dyn Prog + NP A09 8am-8am (class 1pm)
86
Review
(ppt)
1
Congradulations
WATCH ABOVE BY Mon A05
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.