ECE 608

Computational Models and Methods

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

Exams

  • Midterm: Thursday, October 10, in class
  • Final Exam: Tuesday, December 10, 01:00p - 03:00p, MSEE B012

  • Class content discussions can be found on Piazza

    Handouts and Homeworks

    Accessing the following handouts and homeworks will result in being prompted for your Purdue user ID and password. Access is limited to the Purdue community.

    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
    pdf
    Sample Final
    pdf Solutions

    Caveat: The sample exams above are not practice exams but are provided as examples of the style of problem you are likely to encounter. Course coverage may vary semester to semester.

    Lecture Slides

    * Tuesday 8/20/19   Computational models and problems
    * 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