EECS3101 EECS 3101: Design and Analysis of Algorithms
                                                      Jeff Edmonds

Not Registered?: Though Jeff is eager to welcome you, enrollments are NOT managed by him.
I personally dont have the power to get you in. In the past, everyone was able to get in within a few weeks.
But you do need to be doing the work from day one.
Requests should be directed to the EECS Undergraduate office ug@eecs.yorku.ca.
If you are not enrolled yet, feel free to participate in all classes and tests.
Requests to be added our EClass should be directed to audit@eecs.yorku.ca
You don't need the eclass till the first test. And even then not if you have a partner in the class.
Just watch the videos and zoom our chats.


Jeff, Readme, * Course Info *, Times, Dates, Course Description,
Mental Health, EClass, Zoom, Forum, Partner, All.zip, Videos-Panopto, Videos-EDrive

Topics (Videos below) Slides Steps Prac Sol
1) Loop Invariants
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 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 F04

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 2 Recursive F18

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 3 Graph M04

Unit 4: Greedy Algorithms Methods (4.5 hours)
          
ppt, steps, practice, practice sol, Old_Teaching_Method
           These are the simplest possible algorithms. Proving they work,
           however, is hard.


WATCH ABOVE BY Mon F28
WATCH ABOVE BY Wed M02
WATCH ABOVE BY Mon M07
TEST 4 Greedy M18

Unit 5: New Dynamic Programming (6 hours)
          
ppt, steps, practice, practice sol, Old_Teaching_Method
           Shortest Path: A harder instance is solved by filling out a table of solutions for
           easier sub-instances.
           Other Problems: Reduce to Shortest Path

Test 5 A08

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.

WATCH ABOVE BY Mon 28
WATCH ABOVE BY Wed M30

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.