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


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:

Introduction (ppt)

How to Study

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.

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.

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.

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.

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.

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.

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


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.

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.

TEST 8 Dyn Prog + NP A09 8am-8am (class 1pm)

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.