Computational Intelligence, SS08
2 VO 442.070 + 1 RU 708.070 last updated:
Course Notes (Skriptum)
Online Tutorials
Practical Course Slides
Animated Algorithms
Interactive Tests
Key Definitions
Literature and Links

Homework 5: VC-Dimension and Proofs

[Points: 12.5; Issued: 2008/05/09; Deadline: 2008/05/30; Tutor: Gerhard Neumann; Infohour: 2008/05/23, 15:30-16:30, HS i11; Einsichtnahme: 2008/06/13, 15:30-16:30, HS i11; Download: pdf; ps.gz]

Threshold circuits [8.5 points]

Prove that each Boolean function can be computed by a threshold circuit (Schwellenschaltkreis) of depth 2.


  • You can use the fact (without proving it) that there exists for each Boolean function $ f:\{0,1\}^n \rightarrow \{0,1\}$ a Boolean formula in disjunctive normal form (DNF); see definition 1.1.5 of ``Grundbegriffe der Aussagenlogik'' for the precise definition of the DNF.
  • Hence you just have to prove that there exists for each Boolean formula in DNF a circuit of threshold gates (of depth 2) which outputs for each binary input vector 1 if the DNF formula is true and outputs 0 if the DNF formulae is false for the corresponding truth assignment.

VC-dimension [4 points]

  • Consider the case of the hypothesis class of axis parallel rectangles. The VC-dimension of a single rectangle is 4. Find the best lower bound if you can use 2 rectangles instead of one !
  • Consider the case of the hypothesis class of a single, axis parallel rectangle, where you can additionally choose wether to classify class 1 inside or outside the rectangle. Whats the best lower bound for the VC-dimension you can proof ?