CS 303 final

For CS 303.

Final Exam Outline

• 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 will work these out ahead of time and turn in your work. You will use your notes to explain the proof to me (like you are teaching the material). You can consult what is required for each letter grade level for what you should work on. If you still have some problems from the D and C levels to demonstrate, then pick some of those to demonstrate as part of the final. Beyond that, pick the ones that are required for the grade level you hope to reach. You will schedule times to show these to me using the same link as normal - https://cs.indstate.edu/scheduler - but note that the slots are 15 minutes each so that you can also schedule multiple ones of these as you finish problems that you are ready to demonstrate. You can keep scheduling these slots up through Dec 11.
  1. Problems from previous assignments or midterm - if you still need to "pass" problem types that will not be graded any more (proof that a number is irrational, truth tables) then you should fix these problems and plan to present them. I may ask follow up questions in addition to the question as it was originally on your HW or midterm. Note - once the induction, graphs, asymptotics, and additional HW problems are past due, if you still need to "pass" any of those, then you can ask about presenting those as well if you still need them.
  2. There are infinitely many primes - only required for those shooting for at least a B.
  3. Running time of: binary search (required for getting a B or higher in the course), merge sort (required for getting an A or higher in the course).
  4. The real numbers are not countable - only required for those shooting for an A
  5. An NP problem is in NP (only required for those shooting for an A) - pick one of these to write up (explanation of why the problem is in NP - for a "yes" instance, what is the certificate and roughly what is the running time to check it), be prepared to talk about the others as well - Clique, Traveling Salesperson, Longest Path, Set Cover, Subset Sum.

Last HW assignment problems

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

• assignment for Graphs
• assignment for Asymptotics

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 (2ⁿ¹⁰).
   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 2ⁿ time.
   7. Given a Python program, and an input to the program of length n, does the program complete within time n².
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

Final Letter Grades

CS 303 final letter grade

• canvas quiz: stand-alone quiz, mid-term part, or final part
• essays need a pass rating (2/2 for HW, 80%+ for midterm/final problem)
• +/- on letter grade will be determined within each level based on how close to the next level you are

D- level: finish the course, you must have at least attempted and submitted all of the HW assignments and quizzes, and take the final exam

D level:

• canvas quizzes: math notation, math and bases, logic, number theory
• quiz minimum score: 80%
• essays: truth table (at least 1), induction proof (at least 1)

C level: can move on to the next course(s)

• canvas quizzes: misc math, functions/relations, sets, big O asymptotics, regular expressions / languages
• quiz minimum score: 80%
• essays: truth table (at least 2), induction proof (at least 3), graphs (at least 1), irrational number

B level: you are "ok" to move on

• canvas quizzes: graphs, algorithm running times / recursion tree, complexity classes
• quiz minimum score: 80%
• essays: truth table (at least 3), induction proof (at least 5), graphs (at least 2), asymptotics (at least 1), there are infinitely many primes

A level:

• canvas quizzes: probability
• quiz minimum score: 90% (also for all D, C, B level quizzes)
• essays: induction proof (at least 8), graphs (at least 4), asymptotics (at least 3), the real #s are not countable, NP problem is in NP