Difference between revisions of "CS 303 midterm"

From Computer Science
Jump to: navigation, search
(Exam part 1)
(Exam part 1)
Line 14: Line 14:
 
** Number theory - congruence notation, divisibility statements, lcm and gcd. (5-10 minute). [https://indstate.instructure.com/courses/12565/quizzes/230166 practice]
 
** Number theory - congruence notation, divisibility statements, lcm and gcd. (5-10 minute). [https://indstate.instructure.com/courses/12565/quizzes/230166 practice]
 
** Sets - terminology, operations (few minutes).  [https://indstate.instructure.com/courses/12565/quizzes/230164 practice]
 
** Sets - terminology, operations (few minutes).  [https://indstate.instructure.com/courses/12565/quizzes/230164 practice]
** Functions/Relations - terminology/definitions (few minutes) ''practice coming soon''
+
** Functions/Relations - terminology/definitions (few minutes) ''practice coming soon'' - identify whether given functions are onto/one-to-one/bijective; identify whether given relations are transitive, symmetric, anti-symmetric, reflexive, anti-reflexive, equivalence relation, partial order; identify what the following are for given functions - domain, codomain/range.  practice questions will be available before I post the exam late this evening.
 
** Other math - factorial, combinations, exponents/logs (few minutes). [https://indstate.instructure.com/courses/12565/quizzes/230165 practice]
 
** Other math - factorial, combinations, exponents/logs (few minutes). [https://indstate.instructure.com/courses/12565/quizzes/230165 practice]
 
* Short answer / essay, that will be looked at manually
 
* Short answer / essay, that will be looked at manually

Revision as of 16:24, 26 October 2022

This page contains an outline of the midterm exam for CS 303. This covers the first chapters in Building Blocks for Theoretical Computer Science up through Induction.

Goals

The goal of the midterm is to evaluate you on the most important topics from the first half of the term.

Exam part 1

For the "regular exam" portion of the midterm, you will have at most 90 minutes, with the goal that more than half of the class has enough time to finish. it will have the following...

  • Quizzes in Canvas, auto-graded and with practices available (at some point)
    • Math notation, updated with new notation (5-10 min). practice
    • Math bases, same as before (5-10+ min). practice
    • Logic - given a logical formula and true/false values for the variables, evaluate the formula. Given a logical formula, identify whether a formula is unsatisfiable, valid, satisfiable (10 minutes). practice
    • Identify the logical rule or theorem - De Morgan's, distributing union over intersection (and vice versa), definition of implication, pigeon hole principle, contrapositive, inclusion-exclusion, rules of exponents/logs. (5-10 minute). Included within the other practice quizzes.
    • Number theory - congruence notation, divisibility statements, lcm and gcd. (5-10 minute). practice
    • Sets - terminology, operations (few minutes). practice
    • Functions/Relations - terminology/definitions (few minutes) practice coming soon - identify whether given functions are onto/one-to-one/bijective; identify whether given relations are transitive, symmetric, anti-symmetric, reflexive, anti-reflexive, equivalence relation, partial order; identify what the following are for given functions - domain, codomain/range. practice questions will be available before I post the exam late this evening.
    • Other math - factorial, combinations, exponents/logs (few minutes). practice
  • Short answer / essay, that will be looked at manually
    • Truth table - able to write one out correctly (few minutes short answer / essay).
      • Example: Give a truth table that includes both of the following logical formulas. Make sure to include enough steps in your table to make it easy to verify. P1: (A ∨ B) → ((B ∨ C) → (A ∧ C)). P2: ((A ∨ B) → (B ∨ C)) → (A ∧ C). Make sure to include enough text and explanation so that this is a complete and correct proof.
      • Warning - I will probably come up with some more interesting examples than this for the mid-term.
    • Proof that a number is irrational - able to write out the proof correctly (few minutes short answer / essay)
      • Example: Write a correct proof that 51/4 is irrational. Make sure your proof is well written, complete, and correct.
    • Euclid's GCD algorithm - able to show the steps of the algorithm on a given example (few minutes short answer / essay)
      • Example: Use the Euclidean algorithm and show the steps for computing gcd(45,55). Be very clear in your explanation.

The following will not be on this exam.

  • Graphs - terms, basic properties
  • Induction and big O asymptotics - maybe some basic

Exam part 2

The second part of the exam is a 30 minute interview slot with the instructor. You will be asked to explain solutions from the regular exam, from the hw assignments, or questions that are similar to these. The goal is to (a) verify that the work you are submitting is your own (you demonstrate the skills live that you have been turning in work for), (b) have an adaptive portion of the exam where you can be given hints if needed and see if you can get some partial credit.

First draft of the outline for this part is as follows.

  1. HW problem a: I pick a HW problem that you got full credit for, pull up your submission, and ask you to explain how to do it.
  2. HW problem b: I pick a HW problem that you did not get full credit for, pull up your submission, and ask you how to finish it or fix any problems.
  3. Exam part 1 short answer: I pull up your submissions for the part 1 short answer and ask you to explain at least one.
  4. Exam part 1 auto-graded: I make up a new question or two from each of the auto-graded quizzes and ask you to solve them or how to solve them.