CSCI 385 Spring 2023
Advanced Data Structures and Algorithms
Archived Class
Charles Cusack
Computer Science
Hope College
Main
Schedule
Grading
Gradebook
Homework

Policies
College
    Policies
Advice

Notes
Programs
Tutorials

CSCI 112
CSCI 125
Others

Admin

Homework 7

Details

  1. (12, 3 pts per part) IDAA 11.1.3 (page 393)
    Part (b) is determining whether or not a graph is the complete graph (the wording is a little strange). Breifly justify your answers. Also, to show that the bound is tight, you need to give an algorithm that solves the problem in that much time.
  2. (6 points) IDAA 11.1.7 (page 394)
    Make sure your argument is very clear and complete.
  3. (8 points) IDAA 11.3.7 (page 410)
    Don't forget to (1) clearly state the decision version, (2) clearly outline the verification algorithm, and (3), justify that the verification algorithm is polynomial-time.