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

 Topics (Videos below) Slides Steps Prac Sol 0) Relevant Math 1) Loop Invariants and 2) Recursion 3) Graph Algorithms 4) Greedy Algorithms 5) Dynamic Programming 6) Reductions and NP * Review

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
students tell him that his courses were the most useful they had ever
taken.

Request:

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)

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
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
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

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
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
Take the Best of the Best
Construct Optimal Path
Table
Short Code
Excel
Code
Running Time
Graph of Life
Loop Invariants
DFA
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
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
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)
WATCH ABOVE BY Mon A05

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.