ITEC 122 2008fall ibarland

home—info—lectures—exams—archive

exam02-study-guide
exam02 info

Instructions: You can have one single-side 8.5″x11″ piece of paper which has nothing but your handwriting/drawing on it. (No mechanical reproduction.)

Exam questions will, for the most part, be very similar to homework questions. While the focus will be on hw06 onward, there might be questions directly similar to hw04,hw05 and exam01. The most effective way to study would be to re-do hw problems from scratch (perhaps making minor tweaks), and make sure you understand every step. You are encouraged to post and discuss problems on Blackboard's discussion boards.

The only algorithms which you need to know are converting between numbers and numerals(strings) between bases 2,10,16, as well as converting directly between binary and hex numerals. Any other algorithms will be provided, if they are needed (e.g. gcd).

The only formulas you need to know are: Σ_i=1ⁿ(i) and Σ_i=1ⁿ(2ⁱ). Any other formulas will be provided.

• Logic: converse vs. contrapositive of a statement; ∀ and ∃ statements and nested quantifiers; (going from English to logic formulas and vice-versa); pushing negation over quantifiers; pushing negation over and/or (DeMorgan's laws). Proof techniques: direct proof; proof-by-cases; proof-by-contradiction; iff.

  Although the exam won't focus on logic, the above are fundamental concepts which are needed for all sorts of work.

• Sets and set notation; ∈ vs. ⊆; unions, intersection, cross products, power sets.
• Functions: def'n of function, 1-1, onto;
• Numbers: converting numerals(strings) to numbers; concepts such as prime numbers, modular arithmetic (e.g. what are the multiples of 7, mod 10? (that was hw09, #7, row 7)) and greatest-common-divisor.
• Big-Oh notation: definition; how to show a function is big-Oh of another.
• Running time of algorithms (e.g. what is the running time of 'insert', which inserts one number into an already-sorted list with n elements? What is the running time of insert-sort, which works by calling insert on a list of length 1, then a list of length 2, then a list of length 3, … then a list of length n).
  Have a feeling for the feasability of algorithms whose running time is O(2ⁿ) vs. O(n) vs. O(log(n)).
• Induction (regular and/or strong), even if the problem doesn't explicitly break the work down into the parts (a)-(f) as on the homeworks.
• counting: product rule; permutations; combinations.
• basic probability
• Understanding notation (such as the definition of a graph, or a finite state machine; how to capture a notion in terms of sets, functions, etc.)

home—info—lectures—exams—archive

©2008, Ian Barland, Radford University Last modified 2008.Dec.15 (Mon)

Please mail any suggestions (incl. typos, broken links) to iba�rlandrad�ford.edu