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

Teaching Assistant:Office: Phone:Office hours:Email: |
Siyuan Xu EE 168 Read the following link follow this link xu1082@purdue.edu |

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, August 29, 2019 |
Hw1 | Solutions |

Homework 2 Due 12 noon, Tuesday, September 10, 2019 |
Hw2 | Solutions |

Homework 3 Due 12 noon, Tuesday, September 17, 2019 |
Hw3 | Solutions |

Homework 4 Due 12 noon, Tuesday, September 24, 2019 |
Hw4 | Solutions |

Homework 5 Due 12 noon, Tuesday, October 1, 2019 |
Hw5 | Solutions |

Homework 6 Due 12 noon, Tuesday, October 15, 2019 |
Hw6 | Solutions |

Homework 7 Due 12 noon, Tuesday, October 22, 2019 |
Hw7 | Solutions |

Homework 8&9 Due 12 noon, Tuesday, November 5, 2019 |
Hw8&9 | Solutions |

Homework 10 Due 12 noon, Tuesday, November 12, 2019 |
Hw10 | Solutions |

Homework 11 Due 12 noon, Tuesday, November 26, 2019 (Please ignore incorrect homework number in title of solution) |
Hw11 | Solutions |

Homework 12 Due 5pm, Friday, December 6, 2019 (No late submission accepted and solutions would be released at 5pm) |
Hw12 | Solutions |

Sample Midterm |
||

Sample Final |
Solutions |

Thursday 8/22/19 Scalability, Loop invariants, Correctness of recursive programs

Tuesday 8/27/19 Intro to algorithm analysis

Thursday 8/29/19 Mergesort recurrence, Asymptotic notation

Tuesday 9/03/19 More asymptotic notation, induction about asymptotic classes

Thursday 9/05/19 Mathematical induction, recurrences, master theorem

Tuesday 9/10/19 Proof of Master Theorem, Shuffle

Thursday 9/12/19 Analyzing randomized algorithms, Indicator variables

Tuesday 9/17/19 Randomized algorithms, Heaps

Thursday 9/19/19 Heapsort, Quicksort

Tuesday 9/24/19 Expected time of Quicksort, Lower bound for comparison sorts

Thursday 9/26/19 Linear-time sorts

Tuesday 10/01/19 Selection. Introduction to hash tables

Thursday 10/03/19 Hash tables: chaining, hash function design, universal hashing

Tuesday 10/15/19 Open addressing

Thursday 10/17/19 Open addressing analyzed, Intro to dynamic programming

Thursday 10/17/19 Key to midterm

Tuesday 10/22/19 Dynamic programming principles, Matrix chain parenthesization

Thursday 10/24/19 Dynamic programming concepts and issues

Tuesday 10/29/19 Longest common subsequence, Knapsack

Thursday 10/31/19 Huffman coding, introduction to minimum cost spanning trees

Tuesday 11/05/19 Prim's and Kruskal's MCST algorithms

Thursday 11/07/19 Disjoint set problems, Shortest path problems, Bellman-Ford

Tuesday 11/12/19 Dijkstra's algorithm, breadth-first search

Thursday 11/14/19 Depth-first search

Tuesday 11/19/19 Topological sort, strongly connected components

Thursday 11/21/19 All pairs shortest paths, decision problems, uncountably many undecidable problems

Tuesday 11/26/19 Undecidabioity of halting, Polynomial time

Tuesday 12/03/19 The class NP and NP-completeness

Thursday 12/05/19 Cook's Theorem, example reductions

Maintained by Bob Givan and course staff

*givan@purdue.edu*