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:
[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)
More Recent Video
Video covers more than needed.
Video Missing

Introduction (ppt)

? Administrative Details
52 General course description (HTA 0; LN 0,1; CLRS1)

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.

51 Actions vs Assertions
32 15 Proof Using Loop Invariants
42 44 Induction
05 Code vs Math Assertions
05 Physics and Life
19 Physics Spring
13 Home to School Story
19 Recap of Proof of Meta Algorithm
28 Code from LI
24 Pointers
03 Views of Algorithms
23 Insertion Sort
43 Code from LI - Sorting
11 Selection Sort
11 Don't Redo Work
09 Designing an Algorithm
12 Finding Errors
59 Fairy God Mother (Lake)
100 Infinite Line Game
11 More of Input (Insertion and DFA)
21 More of Output (Selection, Blocks, Konig)
24 Narrowing the Search Space
07 The Partition Problem
5 28 Time Complexity Models
33 Shrinking Instance (GCD)
51 Multiplying
19 Data Structure (System) Invariants
13 Bucket (Quick) Sort for Humans
24 Radix/Counting Sort
06 Lower Bound for Sort
Practice Solutions
- 3 20 Cake Cutting
- 5 20 Sorted Matrix Search
- 7 36 Connected Components
- 8 12 Tournaments
- 9 20 Euler Tour

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.

07 Merge Sort
06 Check List
11 Multiplying (mp3,HTA 92; CLRS 282,30,31)
44 Recurrence Relations (HTA 27; LN 2;CLRS 4)
06 Stack Frames
07 Friends and Strong Induction (HTA 8;CLRS 23, 334)
21 Input Size
09 Exponential Growth
19 Towers of Hanoi
14 Merge & Quick Sort
26 (Probabilistic Algorithms)
12 Power
56 Simple Recursion on Trees (HTA 31,10)
07 Generalizing the Problem
13 Things not to do
03 Heap Sort & Priority Queues (HTA 91; LN 2,4; CLRS 7,9)
09 Trees Representing Equations
03 Pretty Print
02 Depth First Search
21 Parsing with Context Free Grammars (HTA 12)
09 Recursive Images (HTA 11)
07 Ackermann's Function (HTA 11)

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.

02 Review definitions and graph terminology (HTA 31;CLRS B)
26 Generic Search
08 Breadth-First-Search (BFS) and shortest paths (HTA 141, 142; CLRS 222)
40 Dijkstra's Shortest Paths (HTA 143; CLRS 24)
25 Depth-First-Search (DFS) (HTA 144, 145; CLRS 223)
15 Linear Order (Dags and topological sorting) (HTA 146; CLRS224)

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.

04 Optimization Problems Definition (HTA 13)
09 Network Flow Defn (HTA 15;CLRS 26)
05 Simple Example
08 Application: Matching
05 Flow Strategy
03 Hill Climbing
23 Augmenting Flow
14 Primal-Dual Hill Climbing
04 Min Cut
10 Max Flow = Min Cut
03 Running Time
18 Linear Programming

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.

12 Greedy Algorithm for Optimization Problems
4 Proving with Loop Invariants
11 Greedy Proof Game
20 Making Change Example
19 Proof from Game
58 Event Scheduling
28 0 Chatting About Proof
0 Math 1090 Logic Proof
33 Minimum Spanning Tree
12 Adaptive Greedy
19 Interval Point Cover
61 Communication and Entropy
10 Forced Horn Clauses
Practice Solutions
- 1 23 Fractional Knapsack Problem
- 3 17 River problem

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

(Skip This) Key Concepts:
40 Bird & Friend
Recursive Backtracking
Dynamic Programming
Bird Friend Algorithm
Life Story Graph
Shortest Path:
18 7 Dynamic Prog vs Dijkstra
Bird & Friend Algorithm
Loop Invariant
Try all Bird Answers
Take the Best of the Best
Construct Optimal Path
Table
8 Short Code
30 Code
3 Running Time
29 (Skip this) Excel
Game of Life Examples
? Game of Life to Graph
57 25 Printing Neatly
13 Printing Neatly + (#lines)^2
14 Longest Common Subsequence
17 15 Knapsack Problem
28 Event Scheduling
22 Buying Stocks
Non-Game of Life Examples
25 All Pairs Shortest Paths
10 Parsing
13 Satisfiability
Review and More Thoughts
5 12 Review
Question for Little Bird
Set of Sub-Instances
Optimal Substructure
Failed Algorithm
8 Failed Algorithm

100 Tutorial
(Skip This) More Graph of Life
25 Loop Invariants
DFA
Your Story
Keep # of States Small
Table
Actions/Edges
Path Through Life
Cost of Solution/Path
Weight of Edge
Optimal Substructure
Little Bird Specifies Action
Solutions = Path
Reduction to Shortest Path
Running Time

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.

00 84 NP-Reductions (Quick)
00 56 50 Card Reduction (Logic)
01 31 History & Overview
02 7 Course vs Schedule
03 14 More about Reductions
04 10 Circuit vs Airplane
05 24 Circuit vs 3-Colouring
06 31 Definition Review

86 Review (ppt)
01 Congradulations

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.