Home Page for CSCI 538 (Fall 2015)



Instructor: Dr. Binhai Zhu

Syllabus by lecture

Tests (40%)

Assignments (40%)

Project (20%)

  • You will need to participate in a course project. Choose a topic in computability/complexity theory and conduct an independent study. The evaluation is based on the project report as well as the presentation. The following five days for presentations are arranged (note that I am gone the week of Nov 30---Dec 4).
  • Nov 12, Jici Huang: --- MIS on 2-interval and 2-track interval graphs.
  • Nov 12, Peng Zou: --- Independent DS has no FPT approximation.
  • Nov 17, Letu Qingge: --- DS on 2-interval and 2-track interval graphs.
  • Nov 17, Rollie Goodman: --- Using cell phone keyboards in NP-hard.
  • Nov 17, Killian Smith: --- AC unification is NP-complete.
  • Nov 17, Sam Mirka: --- Maximum-lifetime data gathering tree in sensor networks: NP-completeness and approximation algorithm.
  • Nov 17, Manasa Boosa: --- NP-completeness of list coloring and precoloring extension on the edges of planar graphs.
  • Nov 19, John McIntosh: --- Energy-aware routing in data center network.
  • Nov 19, Tao Huang: --- Searching the k-change neighborhood for TSP is W[1]-hard.
  • Nov 19, Aidan Bickford: --- Edit distance cannot be computed in strongly subquadratic time.
  • Nov 19, Monica Thornton: --- Inference complexity in continuous time Bayesian networks.
  • Nov 24, Kathryn Manning and Leah Thompson: --- Scrabble is PSPACE-complete.
  • Nov 24, Janet Rounds: --- Quell.
  • Nov 24, Yi Xu: --- The critical-square-grid coverage problem in wireless sensor networks is NP-complete.
  • Nov 24, Asha Nalluri: --- Using DNA to solve NP-complete problems.
  • Nov 24, Vasudev Ravula: --- "Clouding computing is NP-complete".
  • Dec 7 (in CS Conference Room), Faisal Khan: --- Capacity of wireless networks.
  • Class Averages for Each Assignment/Test

    Dr. Binhai Zhu
    Department of Computer Science
    Montana State University
    Bozeman, MT 59717
    Email: bhz@cs.montana.edu
    Office: EPS 355
    Phone: 406-994-4836
    Fax: 406-994-4376