EE 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:
Office hours:

Email:
NONE



Exams

  • Midterm: March 7, 8pm-9:30pm, in GRIS 103 for on-campus students
  • Final Exam: May 4, 8am-10am, in WANG 2599 for on-campus students

  • Class content discussions can be found on Piazza

    Note: Accessing Course Contents

    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.

    Handouts and Homeworks

    Caveat: The exams below 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.
    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
    pdf
    Sample Final
    pdf

    Lecture Slides

    * Thursday, 1/11/18   Computational models and problems
    * 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