ITCS2175 Logic and Algorithms
 Home    Contact    Syllabus    Notes    Outline  

Spring 2008 Outline

Note: some of these dates may change. WebAssign due dates override those listed here.

Due Date Lecture Topics Reading Assignment
1/11/08 Homework 0 Intro to WebAssign
1/15/08 Lecture 1    Introduction, Logic

Note: The first lecture cites an INCORRECT textbook. Your textbook is the Rosen text listed on the syllabus.		 Packet 1 (pdf) - Logic & Proof
Rosen ed 3/4: 1.1, 1.2, 3.1, 9.1, 9.2, 9.3
Rosen ed 5: 1.1, 1.2, 1.5, 10.1, 10.2, 10.3
Rosen ed 6: 1.1, 1.2, 15, 1.6, 11.1, 11.2, 11.3
Lecture 2    Logical Equivalences & Implications
Lecture 3 Formal Logic Proofs, Circuits (example)
Lecture 4 Formal Proofs, Circuits, Disjunctive Normal Form
1/17/08 Homework 1 Practice HW1-2, Logic, proofs, & circuits
1/22/08 Homework 2 Practice HW1-2, Logic, proofs, & circuits
1/26/08 Lecture 5 Predicate Calculus, Circuits, Multiplexers Packet 2 (pdf), - Pred Calc & Set Theory,
circuits, & pred. calc. examples
Rosen ed 3/4: 1.3, 1.4, 1.5, 9.3
Rosen ed 5: 1.3, 1.6, 1.7, 10.3
Rosen ed 6: 1.3, 2.1, 2.2, 11.3
Lecture 6    Pred. Calc, Set Theory, HW3 help
Lecture 7    Set Theory & Proofs, HW3 help
1/28/08 Homework 3 Practice HW3, Circuits & Predicate Calculus
2/5/08 Proofs Tutorials NovaNET Proofs Tutorial Instructions
Justified Thought Tutorial
Deep Thought Proof Tutorial
2/12/08 Lecture 8    Test 1 Review, Induction
2/14/08 Test 1
2/16/08 Homework 4 Practice HW4, Sets & Predicate Calculus
2/19/08 Lecture 9    Induction,Arithmetic Proofs Packet 3 (pdf) - Induction
Rosen ed 3/4: 1.7, 3.1, 3.2
Rosen ed 5: 1.5, 3.1, 3.2, 3.3
Rosen ed 6: 2.4, 4.1
Lecture 10   Ind, Sets, Recursion (HW5 help)
2/21/08 Homework 5 Practice HW5, Sets, Arithmetic Proofs, Induction
2/26/08 Lecture 11   Recursion, Induction Packet 4 (pdf) - Recursion & Big O
Rosen ed 3/4: 3.3, 5.1, 5.2
Rosen ed 5: 3.4, 6.1, 6.2
Rosen ed 6: 4.3, 7.1, 7.2
Lecture 12   Recursion (Towers), Induction, Intro to Growth of Functions
Lecture 13    HW6 help, Big O, Induction Pfs with Ineq.
2/28/08 Homework 6 Practice HW6, Induction, Recursion
3/14/08 Lecture 14    Big O, Omega, Theta, Ind, Test 2 rev. Rosen ed 3/4: 1.8
Rosen ed 5: 2.2
Rosen ed 6: 3.2
Lecture 15    Test 2 Review
3/16/08 Test 2
  • Study HW 4-6, Test 2 Review, & Special Tests 3,4, and 5. You are NOT responsible for the 1st column in Special Test 3, problem 2.
  • Set Theory defns & proofs using predicates
  • Pred Calc P(x,y) table
  • Arithmetic proofs (irrational #s, divisibility)
  • Induction
  • Recursion - finding recursive and closed forms
  • You will NOT have to prove the closed form of a recursion on this test, but you will on the next one.
3/18/08 Lecture 16    Big-O help, Binary Relations Packet 5 (pdf) - Binary Relations Rosen ed 3/4: 6.1, 6.3, 6.4, 6.5, 6.6
Rosen ed 5: 7.1, 7.3, 7.4, 7.5, 7.6
Rosen ed 6: 8.1, 8.3, 8.4, 8.5, 8.6
Lecture 17    HW7 help, Binary Relations

Binary Relations notes:

  • In Lecture 17, I mistakenly read R1 o R2 as "R2 composed with R1". This should be read "R1 composed with R2".
  • In packet 5, I use Rf for reflexive closure of R, Rs for symmetric closure of R, and Rt for transitive closure of R. In lecture I refered to them as Rrc, Rsc, and Rtc. Either notation is acceptable (others as well, there is not a mathematical standard for this, you will have to denote it as a particular closure in English).
3/20/08 Homework 7 Practice HW7, Big O, Ind, Recursion
3/25/08 Lecture 18    Binary Relations, HW8 help, Intro to Counting
3/28/08 Binary Relations Tutorial Survey Binary Relations Tutorial Instructions
3/27/08 Homework 8 Practice HW8, Binary Relations
4/03/08 Test 3
4/08/08 Lecture 19   Counting Packet 6 (pdf) - Counting & Graphs
Hasse Diagrams: Packet 5, pages 14-16.
Rosen ed 3: 4.1, 4.2, 4.3, 4.6, 4.7, 5.4
Rosen ed 4: 4.1, 4.2, 4.3, 4.6, 4.7, 5.5
Rosen ed 5: 4.1, 4.2, 4.3, 4.5, 4.6, 6.5
Rosen ed 6: 5.1, 5.2 5.3, 5.5, 5.6, 7.5
Lecture 20   Counting
Lecture 21 Counting, Graph Theory, Pascal's Triangle, HW9 help
4/10/08 Counting Tutorial Survey Counting Tutorial Instructions
4/10/08 Homework 9 Practice HW9, Counting
4/15/08 Lecture 22 Graph Theory, Review of Big-O & Binary Relations FSM packet (pdf);
Rosen ed 3/4: 6.6, 7.2, 7.3, 7.5, 8.6, 10.3
Rosen ed 5: 7.6, 8.2, 8.3, 8.5, 9.5, 11.5
Rosen ed 6: 9.2, 9.3, 9.5, 10.5, 12.5
Lecture 23 Finite State Machines
Lecture 24 Finite State Machines
4/17/08 Homework 10 Practice HW10, Graphs, Hasse Diagrams
Optional Lecture 25 Grey Codes, The Universal Problem
Lecture 26 Grey Codes, The Universal Problem
4/20/08 Lecture 27 Test 4 Review (Counting, Graphs, FSMs)
4/22/08 Test 4
  • Study Practice HW 9-10, Test 4 Review, Special Tests 8-10, Packet 6 examples.
  • Counting - draw picture, combinations, permutations, Addition Rule, Mult Rule, Inclusion-Exclusion, Formulas, Rearranging letters in word, Pigeonhole Principle - find # of pigeons, holes, or the # of pigeons you can guarantee are in one hole, Divider problems.
  • Graphs - Euler circuits & paths & nec. conditions for both, Hamilton circuits, Kruskal's algorithm for Minimum Spanning Trees,
  • Binary relations - Draw Hasse diagrams, find minimal, maximal, minimum, and maximum elements. Find least upper bounds and greatest lower bounds.
  • Finite State Machines - Create a finite state machine given a regular expression. Label start and end states. Create a regular expression given a finite state machine.
5/06/08 Final Exam Covering all four tests.