EECS3101 EECS 3101: Design and Analysis of Algorithms
                                                      Jeff Edmonds: Fall 2023-2024 E (Winter Z)


Jeff, Readme, Marking, Times, Dates, Description,
Mental Health, EClass, Zoom, Forum 2023 Videos, Survey, Solutions

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

Request:
     Jeff tends to talk too fast. Please help him go pole pole slowly.
     Please ask questions.

Mandate:
     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.

How to Study:
     Watch, Pause, Think, and Unpause the slides/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 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.

Readings:
[HTA]   How to Think about Algorithms:   York Bookstore   Amazon   Cambridge House Press   Reviews
Jeff's old videos
Jeff's Machine Learning Chapter
Jeff's Logic Chapter
[Problem Examples] Codingbat & Kattis
[Video] MIT Videos
Andy Mirzaian's Sample Tests, References, Links
[CLRS] Cormen, Leiserson, Rivest, and Stein
[More Notes] Umesh Vazirani's Book    Jeff Erickson's Notes
More Jeff Topics
Jeff's Fun Stuff

Symbol Meaning:
Power Point Slides
5
2020 Video (5 mins)
5 2021 Video (5 mins)
Video covers more than needed.
Video Missing
Pooh

Introduction (ppt)

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.


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.


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.


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.


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


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.


.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.