Difference between revisions of "CS 303 final"

From Computer Science
Jump to: navigation, search
(Created page with "=Last HW assignment problems= * assignment for Graphs * assignment for Asymptotics Additional problems # Recursion tree / recurrence relation. Suppose we have a recu...")
 
(→‎Last HW assignment problems)
Line 6: Line 6:
 
# Recursion tree / recurrence relation.  Suppose we have a recursive algorithm that solves a problem by splitting the size n problem into 4 different problems of size n/2, solves the smaller problems, and takes O(n) time putting the solutions together to be a solution to the size n problem.  What is the running time of the algorithm?  Use a recursion tree to demonstrate your solution.
 
# Recursion tree / recurrence relation.  Suppose we have a recursive algorithm that solves a problem by splitting the size n problem into 4 different problems of size n/2, solves the smaller problems, and takes O(n) time putting the solutions together to be a solution to the size n problem.  What is the running time of the algorithm?  Use a recursion tree to demonstrate your solution.
 
# NP.  Show that the following problem is contained within NP.  We are given a list of n students and the courses for each that they want to take in the spring, and we are also given a list of m teachers and the list of classes that they can teach.  The goal is to determine whether there is a schedule so that all students are able to take all of the courses they want to, with the courses being taught by teachers who can teach them.  Assume that courses are scheduled from 9am-4pm MWF and 9:30am-3:30pm on TR.
 
# NP.  Show that the following problem is contained within NP.  We are given a list of n students and the courses for each that they want to take in the spring, and we are also given a list of m teachers and the list of classes that they can teach.  The goal is to determine whether there is a schedule so that all students are able to take all of the courses they want to, with the courses being taught by teachers who can teach them.  Assume that courses are scheduled from 9am-4pm MWF and 9:30am-3:30pm on TR.
−
# Complexity classes.
+
# Complexity classes. For each of the following problems, what the smallest complexity class that the decision version of the problem fits into, and why?
 +
## Sorting
 +
## Factoring an integer
 +
## Matrix multiplication
 +
## Given a graph, decide whether the graph is connected
 +
## Given a Python program, and an input to the program of length n, does the program ever halt.
 +
## Given a Python program, and an input to the program of length n, does the program complete within time 2<sup>n</sup> time.
 +
## Given a Python program, and an input to the program of length n, does the program complete within time n<sup>2</sup>.
 +
# For each of the following, give a regular expression, DFA, or NFA for the language.  Note - you should make sure to choose regular expression for at least two and DFA or NFA for at least two.
 +
## binary strings with an even # of 1s
 +
## binary strings that start and end with the same bit
 +
## binary strings that somewhere contain 00 and 11
 +
## binary strings that somewhere contain 00 or 11
 +
## binary strings that are at most 4 bits long
 +
## binary strings that are exactly 4 bits long
 +
# Which of these are countable, which are not.
 +
## integers
 +
## rationals
 +
## even integers
 +
## multiples of 100
 +
## real numbers
 +
## rational #s between 0 and 1
 +
## real #s between 0 and 1
 +
## powerset of the integers
 +
## powerset of the rationals
 +
## powerset of the even integers
 +
## powerset of the real numbers
 +
# Binomial theorem.  Something, maybe.
 +
# Undecidable problems.  Something, maybe.
  
−
What is the smallest set it is in: P, NP, EXP, none of these.
+
Things that will likely go onto a quiz.
−
* sorting
+
* Combinations, permutations, etc.
−
* factoring an integer
+
* Discrete probability
−
* matrix multiplication
 
−
* check if a given graph is connected
 
−
* given a program, and an input to the program of length n, does
 
−
  the program complete within time 2**n.
 
−
* given a program, and an input to the program of length n, does
 
−
  the program every halt.
 
−
* given a program, and an input to the program of length n, does
 
−
  the program complete within time n**2.
 
−
 
 
−
Binomial theorem -
 
−
 
 
−
Regular expression for something.
 
−
DFA or NFA for something.
 
−
* binary strings with an even # of 1s
 
−
* binary strings that start and end with the same bit
 
−
* binary strings that somewhere contain 00 and 11
 
−
* binary strings that somewhere contain 00 or 11
 
−
* binary strings that are at most 4 bits long
 
−
* binary strings that are exactly 4 bits long
 
−
 
 
−
Countability - which of these are countable, which are not.
 
−
* integers
 
−
* rationals
 
−
* even integers
 
−
* multiples of 100
 
−
* real numbers
 
−
* rational #s between 0 and 1
 
−
* real #s between 0 and 1
 
−
* powerset of the integers
 
−
* powerset of the rationals
 
−
* powerset of the even integers
 
−
 
 
−
 
 
−
Undecidability - halting problem, others.
 
−
 
 
−
 
 
−
Combinations, permutations - quiz
 
−
 
 
−
Discrete probability
 

Revision as of 17:20, 17 November 2022

Last HW assignment problems

Additional problems

  1. Recursion tree / recurrence relation. Suppose we have a recursive algorithm that solves a problem by splitting the size n problem into 4 different problems of size n/2, solves the smaller problems, and takes O(n) time putting the solutions together to be a solution to the size n problem. What is the running time of the algorithm? Use a recursion tree to demonstrate your solution.
  2. NP. Show that the following problem is contained within NP. We are given a list of n students and the courses for each that they want to take in the spring, and we are also given a list of m teachers and the list of classes that they can teach. The goal is to determine whether there is a schedule so that all students are able to take all of the courses they want to, with the courses being taught by teachers who can teach them. Assume that courses are scheduled from 9am-4pm MWF and 9:30am-3:30pm on TR.
  3. Complexity classes. For each of the following problems, what the smallest complexity class that the decision version of the problem fits into, and why?
    1. Sorting
    2. Factoring an integer
    3. Matrix multiplication
    4. Given a graph, decide whether the graph is connected
    5. Given a Python program, and an input to the program of length n, does the program ever halt.
    6. Given a Python program, and an input to the program of length n, does the program complete within time 2n time.
    7. Given a Python program, and an input to the program of length n, does the program complete within time n2.
  4. For each of the following, give a regular expression, DFA, or NFA for the language. Note - you should make sure to choose regular expression for at least two and DFA or NFA for at least two.
    1. binary strings with an even # of 1s
    2. binary strings that start and end with the same bit
    3. binary strings that somewhere contain 00 and 11
    4. binary strings that somewhere contain 00 or 11
    5. binary strings that are at most 4 bits long
    6. binary strings that are exactly 4 bits long
  5. Which of these are countable, which are not.
    1. integers
    2. rationals
    3. even integers
    4. multiples of 100
    5. real numbers
    6. rational #s between 0 and 1
    7. real #s between 0 and 1
    8. powerset of the integers
    9. powerset of the rationals
    10. powerset of the even integers
    11. powerset of the real numbers
  6. Binomial theorem. Something, maybe.
  7. Undecidable problems. Something, maybe.

Things that will likely go onto a quiz.

  • Combinations, permutations, etc.
  • Discrete probability
Retrieved from "https://cs.indstate.edu/wiki/index.php?title=CS_303_final&oldid=3431"