Exam Sun, 8 Dec 2024 19:00 Keele LAS C
Jeff,
Readme,
Marking,
Times,
Dates,
Description,
Enrolling,
Mental Health,
EClass,
Zoom,
2023 Videos,
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.
When you email me something put 3101 in the subject.
- A photos helps if you want me to know who you are.
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:
Symbol Meaning:
[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
Power Point Slides
5
5 2021 Video (5 mins)
More Recent Video
Video covers more than needed.
Video Missing
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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.