Homework 8, 17.12.2012
-
Review encoding of shortest path, maximal flow, and sorting problems as linear programs,
see Section 3.
-
Review formalization of maximal cardinality bipartite matching as linear program and as SAT problem.
Homework 7, 10.12.2012
-
Review the Ford–Fulkerson algorithm for computation of maximal flow, see this
article.
-
Review formalization of importance as stationary probability in Markov chains, see slides 220-230.
Homework 6, 03.12.2012
-
Review binary heaps, their insert and delete operations, as well as representation using arrays, see this
article.
- Read the article on scalability aspects of heap like datastructures, see You're doing it wrong.
-
Review the A* algorithm, see slides 182-189.
Homework 5, 26.11.2012
-
Review definitions related to graphs, see slides 107-117.
-
Review depth-first traversal strategies, see slides 118-134.
-
Review strongly connected components and their computation, see slides 135-147.
-
Review breadth-first traversal and Dijkstra's shortest path algorithm, see slides 148-179.
Homework 4, 19.11.2012
-
Review counting and radix sort, see slides 71-77.
-
Review searching in arrays, see slides 79-83.
-
Review binary trees and their implementation using pointers, see slides 84-95.
-
Review AVL trees and their implementation using pointers, see slides 96-105.
Practice insertion and rebalancing operations using examples.
-
Prove that for a positive
n the program
i = 0;
while (i < n) {
a[i] = i+1;
i++;
}
yields upon termination an array a such that at each position p between 0 and n-1
the value a[p] is greater than p.
Start with representing the program as a control-flow graph, identify a suitable induction hypothesis, and then check the hypothesis.
Homework 3, 12.11.2012
-
Revisit how programs can be represented as control-flow graphs with mathematical relations on edges.
-
Revisit how proofs by induction for programs can be decomposed using control-flow graphs.
-
Prove that the program
s = 0;
i = 0
while (i =< n) {
s = s+2*i;
i = i+1;
}
computes the value of s that is equal to n*(n+1) when n is positive.
Start with representing the program as a control-flow graph, identify a suitable induction hypothesis, and then check the hypothesis.
Homework 2, 29.10.2012
-
Review sorting algorithms Insertion Sort, Bubble Sort, and Quick Sort, as well as Landau notation, see slides 20-37, 53-63.
-
Execute each sorting algorithm on paper. Use a small array as input and write down intermediate execution steps with sufficient amount of details.
-
Represent invariantes on slide 59 as logical formulas.
-
Implement Insertion Sort, Bubble Sort, and Quick Sort following the slides. Use your favorite programming language. Test your implementations.
-
Modify your implementations such that the sorting order is reversed, and test them.
Homework 1, 22.10.2012
|
Contact
Teaching
