CS 303 final

From Computer Science
Revision as of 14:35, 22 November 2022 by Jkinne (talk | contribs) (→‎Last HW assignment problems)
Jump to: navigation, search

Final Exam Outline

Working on this, will email the class when it's ready.

  • Canvas quizzes - all taken during our 2 hour final exam slot (in the classroom if possible, if you need to take these at another time you can ask), Wednesday Dec 7 from 1-3pm. If you are in the face to face section and want to take it remotely, you need to ask for permission. If you are in either section and want to take it at a different time, you need to ask for permission.
    • From midterm: math notation, math and bases, logic, number theory, miscellaneous math, functions and relations, sets.
    • New since then: graphs, big O asymptotics, algorithm running times / recursion tree, complexity classes, regular expressions / languages, probability. And there will be practice versions of these.
  • Interview - will be just doing proofs for some of the main things we have looked at. You have notes written up on these so that you'll be able to demonstrate any of them I ask. You will turn in your notes, but I may not look at them - the grade will be mostly based on the interview. Include references/citations for what you use to make your notes. I will let you know the problems once I have made them up. Interview times - any time after I post more details on the final (probably by Nov 28 or 29) and up through Dec 9 at noon. Those in the face to face section are required to do this in person (unless you get approval from me). You will schedule a time, the same as last time with https://cs.indstate.edu/scheduler
    • Root of a number is irrational - like on the midterm
    • Truth tables - like on the midterm
    • Euclidean algorithm - proof that it is correct
    • An induction proof - arithmetic or geomteric sum, or something similar
    • Running time of: binary search, merge sort, others we looked at in class
    • The real numbers are not countable (and similar)
    • The rational numbers are countable (and similar)
    • There are infinitely many primes
    • An NP problem is in NP - one we did in class

Last HW assignment problems

Jeff will write up solutions and decide which ones actually get looked at.

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 x courses, and 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 - given the right certificate you can check that the answer is "yes" efficiently.
  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? Complexity classes are: P, NP, EXP, none of these. P - polynomial time, NP - nondeterministic polynomial time, EXP - exponential time (2n10).
    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

Things that will likely go onto a quiz or on the final.

  • Combinations, permutations, etc.
  • Binomial theorem. Something, maybe.
  • Undecidable problems. Something, maybe.
  • Discrete probability
Retrieved from "https://cs.indstate.edu/wiki/index.php?title=CS_303_final&oldid=3484"