See also: the course schedule on Learning Suite.

Note: the PowerPoint slides also contain hidden slides that were not used in class.

! Date |
PowerPoint | Screencast | Title | ||
---|---|---|---|---|---|

1 | 1/5/2015 | PPTX | — | Course Introduction | |

2 | 1/7/2015 | PPTX | — | Asymptotic Notation | |

3 | 1/9/2015 | PPTX | Lecture Part 2 | Modular Arithmetic | |

4 | 1/10/2015 | PPTX | Entire Lecture | Primality Testing | |

5 | 1/14/2015 | PPTX | — | Public Key Cryptography with RSA | |

6 | 1/16/2015 | PPTX | — | Divide and Conquer | |

7 | 1/20/2015 | PPTX | Entire Lecture | Homogeneous Recurrence Relations | |

8 | 1/23/2015 | PPTX | Lecture Part 2 | Non-homogeneous Recurrence Relations | |

9 | 1/26/2015 | PPTX | — | Divide-and-conquer Recurrence Relations with Change of Variable | |

9b | 1/28/2015 | PPTX | — | Proof of the Master Theorem | |

10 | 1/29/2015 | PPTX | Entire Lecture | Analysis of Quicksort | |

16 | 2/2/2015 | PPTX | Lecture Part 2 | Connectedness in Undirected Graphs | |

19 | 2/4/2015 | PPTX | Entire Lecture | Shortest Paths | |

20 | 2/5/2015 | PPTX | Entire Lecture | Correctness and Efficiency of Dijkstra's Algorithm | |

17 | 2/9/2015 | PPTX | — | DAG Linearization | |

18 | 2/11/2015 | PPTX | Entire Lecture | Strongly Connected Components | |

22 | 2/13/2015 | PPTX | Entire Lecture | Intro. to Dynamic Programming | |

23 | 2/17/2015 | PPTX | — | Coins: Making Optimal Change with Dynamic Programming | |

24 | 2/18/2015 | PPTX | Lecture Part 2 | The Optimality Property | |

25 | 2/19/2015 | PPTX | Entire Lecture | Gene Sequence Alignment | |

26 | 2/23/2015 | PPTX | — | 0/1 Knapsack | |

27 | 3/2/2015 | PPTX | Entire Lecture | Intro. to Linear Programming | |

28 | 3/4/2015 | PPTX | — | Network Flow | |

29 | 3/6/2015 | PPTX | Entire Lecture | Ford-Fulkerson Algorithm, Minimum Cuts, Bipartite Graph Matching | |

30 | 3/9/2015 | PPTX | — | Simplex Algorithm | |

31 | 3/13/2015 | PPTX | — | Simplex Algorithm (cont.) | |

32a | 3/14/2015 | PPTX | Entire Lecture | Review: Tractability | |

32 | 3/16/2015 | PPTX | — | State-Space Search | |

33 | 3/18/2015 | PPTX | — | Branch and Bound | |

38 | 3/19/2015 | PPTX | Entire Lecture | Solution-Space Search | |

34 | 3/23/2015 | PPTX | — | Branch and Bound for the TSP | |

35 | 3/25/2015 | PPTX | — | B&B for the TSP: State Expansion | |

36 | 3/26/2015 | PPTX | Entire Lecture | A* | |

37 | 3/30/2015 | PPTX | — | Optimality of A* | |

11 | 4/1/2015 | PPTX | — | Introduction to Probability Theory | |

12 | 4/3/2015 | PPTX | — | Average Case Analysis of Quicksort | |

14 | 4/6/2015 | PPTX | — | Convolution | |

15 | 4/8/2015 | PPTX | — | Fast Fourier Transform (FFT) | |

13 | 4/10/2015 | PPTX | Entire Lecture | Strassen's Algorithm | |

If you wish direct access to the mp4 video files behind a screencast, just use the same URL for the screencast as above, but replace the “html” extension with “mp4”.

BYU CS users also have full access to the posted lecture slides via the CS department file-system. Connect to schizo, and check the following directory:

/users/home1/faculty/ringger/public_html/Winter2015-CS312/lectures