Professor:Office:Phone:Office hours:Email: |
Bob Givan EE 313C 4-9068 follow this link givan@purdue.edu |

Teaching Assistant:Office: Office hours:Email: |
NONE |

Class content discussions can be found on Piazza

Course Information | txt | |

Problem mappings across editions --provided as is, no guarantees |
2nd Ed. to 3rd Ed. | |

Homework 1 Due 12 noon, Thursday, January 18, 2018 |
Hw1 | Solutions |

Homework 2 Due 12 noon, Tuesday, January 30, 2018 |
Hw2 | Solutions |

Homework 3 Due 12 noon, Tuesday, February 6, 2018 |
Hw3 | Solutions |

Homework 4 Due 12 noon, Tuesday, February 13, 2018 |
Hw4 | Solutions |

Homework 5 Due 12 noon, Tuesday, February 20, 2018 |
Hw5 | Solutions |

Homework 6 Due 12 noon, Tuesday, February 27, 2018 |
Hw6 | Solutions |

Homework 7 Due 12 noon, Tuesday, March 20, 2018 |
Hw7 | Solutions |

Homework 8 Due 12 noon, Tuesday, March 27, 2018 |
Hw8 | Solutions |

Homework 9 Due 12 noon, Tuesday, April 3, 2018 |
Hw9 | Solutions |

Homework 10 Due 12 noon, Tuesday, April 10, 2018 |
Hw10 | Solutions |

Homework 11 Due 12 noon, Tuesday, April 17, 2018 |
Hw11 | Solutions |

Homework 12 Due 5pm, Friday, April 27, 2018 |
Hw12 | Solutions |

Sample Midterm |
||

Sample Final |

Tuesday, 1/16/18 Worst-case analysis, Correctness via mathematical induction

Thursday, 1/18/18 Intro to runtime analysis, Intro to Divide and Conquer design and analysis

Tuesday, 1/23/18 Asymptotic complexity classes

Thursday, 1/25/18 Asymptotic classes of recurrences

Tuesday, 1/30/18 Master Theorem for recurrences

Thursday, 2/1/18 Master Theorem for recurrences, Randomized algorithms

Tuesday, 2/6/18 Randomized algorithms

Thursday, 2/8/18 Heaps

Tuesday, 2/13/18 Heaps and Quicksort

Thursday, 2/15/18 Quicksort

Tuesday, 2/20/18 Lower bound for comparison sorts, Counting and Radix sorts

Thursday, 2/22/18 Radix and Bucket sorts, Selection

Tuesday, 2/27/18 Hash tables with chaining

Thursday, 3/1/18 Exam preview, Hash tables with open addresssing

Tuesday, 3/6/18 Exam preview, Hash tables with open addresssing, Dynamic Programming Introduction

Thursday, 3/8/18 Dynamic Programming Introduction

Tuesday, 3/20/18 Dynamic Programming

Thursday, 3/22/18 Dynamic Programming

Tuesday, 3/27/18 Greedy Algorithms

Thursday, 3/29/18 Greedy Algorithms, Minimum-cost Spanning Trees

Tuesday, 4/3/18 Minimum-cost Spanning Trees

Thursday, 4/5/18 Shortest paths algorithms

Tuesday, 4/10/18 Breadth and Depth First Search

Thursday, 4/12/18 Topological sort and SCC's

Tuesday, 4/17/18 Floyd-Warshall, Decision Problems, Decidability

Thursday, 4/19/18 Undecidability, The Class P.

Tuesday, 4/24/18 The Class NP, Polynomial-time Reduction

Thursday, 4/26/18 NP-hardness, NP-Completeness, Cook's Theorem

Maintained by Bob Givan and course staff

*givan@purdue.edu*