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.
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, Forum.txt, 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: 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)

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.