CS-270 Algorithms 2011/12

Messages

• See below for the solutions for the second coursework.
• See below for the script for the revision lecture.
• We have two lectures in week 11 (12/12 - 16/12), namely Monday and Tuesday (usual time and place): Both lectures serve as revision and exam preparation.
• Information on the past exam-paper for CS-242, 2010/11:
  1. CS-242 was a 20-credit module, while now we have a 15-credit module.
  2. The format of our exam (for 2011/12) is 2 hours, with two out of three questions (the standard format; the exam for CS-242 was longer).
  3. There is no multiple-choice question anymore. However contentwise all ten questions from Part A of the 2010/11 exam are relevant.
  4. Question B is in this form not of relevance (we do divide-and-conquer, but we didn't practise this specific application).
  5. Question C is not of relevance (we don't do network flow anymore).
  6. Question D is of relevance.
• See below for the learning goals for the ninth week.
• See below for links with more information on our topics.
• If you can't make a lab session:
  1. Of course, this can only be an exception.
  2. You need then to do the lab session on our own.
  3. You need also to provide some evidence that you did it.
  4. This must be presented in person either to one of the postgrads, or you can come to my office.
  5. Either the postgrads or I will then have a little chat about that lab session's content.
  6. Done that, you sign a piece of paper, and that's it.
  7. But, of course, this must be an exception.

General information

• Lectures
  1. Monday 13-14, Glyndwr C
  2. Tuesday 9-10, Glyndwr B
  3. Wednesday 10-11, Grove building, room 330
  4. Thursday 11-12, Wallace Lecture Theatre 218
  5. The first three lectures are regular lectures, while the fourth (last) lecture is a "tutorial lecture", where the material from the week is repeated and deepened. Of course, also this lecture is compulsory.
• Lab sessions (attend one of the two sessions)
  1. Thursday 12-13, Linux Lab
  2. Thursday 13-14, Linux Lab
  The postgraduate demonstrators are
  • Matthew Gwynne
  • Andrew Lawrence
• Course work
  1. First coursework: Handed out 24/10/2011, deadline 7/11/2011.
  2. Second coursework: Handed out 21/11/2011, deadline 5/12/2011.
• Exam
• The textbook

Script

1. Week 1:
   • Printing
   • Viewing
   • Slides
2. Week 2:
   • Printing
   • Viewing
   • Slides
3. Week 3:
   • Printing
   • Viewing
   • Slides
4. Week 4:
   • Printing
   • Viewing
   • Slides
5. Week 5+:
   • Printing
   • Viewing
   • Slides
6. Week 6+:
   • Printing
   • Viewing
   • Slides
7. Week 7: to be completed.
8. Week 8:
   • Printing
   • Viewing
   • Slides
9. Week 9:
   • Printing
   • Viewing
   • Slides
10. Week 10:
    • Printing
    • Viewing
    • Slides
11. Week 11:
    • Printing
    • Viewing
    • Slides

Lab sessions

• Week 1
• Week 2
• Week 3
• Week 4
• Week 5
• Week 6
• Week 7
• Week 8
• Week 9
• Week 10 .

Learning goals

• Week 1:
  1. Know and understand Insertion Sort.
     • You should be able to write pseudo-code for it.
     • Know how best-case and worst-case examples look like, and how many comparisons they need for sorting (at least in terms of Theta).
  2. Know the basic functions b^x, log_b(x), log_2(x) = lg(x), and floor and ceiling.
  3. And recall the summation symbol (big Sigma).
• Week 2:
  1. Big-Oh, Omega and Theta.
     1. Know the definitions.
     2. Know basic examples.
     3. More examples to come in the rest of the module.
  2. Divide-and-Conquer:
     1. Understand the basic principle.
     2. More examples to come in the rest of the module.
  3. Min-Max Algorithm:
     1. Understand the naive algorithms and why it takes 2n-2 comparisons.
     2. Understand the idea for the divide-and-conquer version.
     3. Understand the Min-Max recurrence.
• Week 3:
  1. Understand Merge-Sort and its analysis.
  2. Understand the basic idea for recurrences.
  3. Know the Master theorem, and how to apply it.
  4. Understand the basic idea for the faster matrix-multiplication algorithm.
• Week 4:
  1. There are various important notions and concepts to learn.
  2. This means at least that you know (can reproduce) the (precise) definition, where you understand all the terms in the definition, and that you can give examples.
  3. The notions are:
     1. "Graphs", "undirected" and "directed" ("digraphs")
     2. "Vertices" and "edges" resp. "arcs" (directed edges)
     3. "Trees" (free ones) and "rooted trees"
     4. "Spanning trees" and "rooted spanning trees"; also "spanning forests"
     5. The "root", the "leaves" and the "children" of a "node" in a rooted tree
     6. "Paths" in graphs and digraphs
     7. "Connected graphs"
     8. "Cycles" in graphs and digraphs
     9. Connected graphs without cycles are trees, digraphs without cycles are "directed acyclic graphs" ("dags").
  4. Know the two main representations of graphs and digraphs (adjacency lists and adjacency matrices).
  5. The first main algorithm is BFS:
     1. When the input is a connected graph and a vertex s, the output is is rooted spanning tree (with root s), which contains shortest paths from the root to all other vertices (shortest, of course, in the full graph), plus the distance map.
     2. One can also run it on a digraph, and one can also restart it so that it covers the whole (possibly disconnected) graph.
     3. The output then is a collection of rooted trees, containing shortest paths from the respective root to all other reachable vertices.
  6. The second main algorithm is DFS:
     1. Here the input is already assumed as a possibly disconnected graph, and the output is a DFS-forest, consisting of rooted spanning trees for the connected components, plus the assignment of discovery and finishing times for all vertices.
     2. Again, we can run it on a digraph.
     3. The application we considered is for topological sorting.
• Week 5:
  1. Know and understand the abstract data type ("API") "dynamic set":
     • What are the basic operations?
     • What are "keys"? Which operations do we assume for them?
     • What is the simplest implementation? What are the disadvantages?
     • What are "dictionaries" and "priority queues" (in this context)?
  2. Understand the chain of notions
     • tree
     • rooted tree
     • ordered rooted tree
     • binary tree
     • binary search tree.
  3. Understand the representation of binary trees.
  4. Understand the inorder traversal for binary trees.
  5. Understand how the order requirement for a binary search tree interacts with the inorder traversal.
  6. Understand how to search for a key in a binary search tree, and what the complexity of this operation is.
  7. Understand the computation of minimum and maximum in binary search trees, and the complexity of these operations.
  8. The same for the computation of predecessors and successors.
  9. Understand the idea and the algorithm for insertion.
  10. Understand the ideas for deletion.
  11. Understand the topic of "bad orders" ("they are possible, but unlikely").
• Week 6:
  1. Understand the abstract data type underlying "disjoint sets":
     • What are the basic operations?
     • What are the "representatives"?
     • When are elements given, when pointers?
  2. Computation of connected components as application:
     • Know what "connected components" are.
     • Understand how to compute connected components by the disjoint-sets data structure.
  3. Linked-list representation of disjoint sets:
     • Know what a node of this representation looks like.
     • Understand how the nodes are linked together to build the data structure.
     • Understand how the three basic operations operate on this data structure, and what their costs are.
  4. Runtime analysis:
     • Understand the two main parameters, n and m.
     • Understand the idea of "amortised analysis".
     • Understand the nasty example for the linked-list representation (without any heuristics).
  5. Weighted-union heuristics:
     1. Understand the problem and the idea.
     2. Know the theorem about the worst-case upper bound achieved by this heuristics.
     3. Know and understand the proof of the theorem.
  6. Forest representation of disjoint sets:
     • Understand the idea.
     • Understand which of the basic operations become faster, which slower.
     • Understand the two basic heuristics for improving the efficiency of the forest representation.
     • Know the runtime achieved by using both.
• Week 8:
  1. Understand the problem of making change, and how a greedy approach is invoked here.
  2. It should be not too hard for you to come up with a coin denomination where the greedy approach fails.
  3. Understand the general idea of a "greedy approach".
  4. Minimum spanning trees:
     • Know the definition of an MST.
     • You should be able to exhibit some MST for small examples yourself (just by looking at it).
     • Understand Kruskal's algorithm (as a special greedy algorithm).
     • Understand how it involves disjoint sets.
  5. Get a general idea when greedy algorithms work; try to grasp the criterions given.
  6. Huffman codes:
     • Understand the general problem of compressing a text file via a binary code.
     • Understand how binary prefix codes are presented by binary trees.
     • Understand that some codes are more efficient than others.
     • Understand the Data Compression Problem.
     • Understand the greedy algorithm for computing a "Huffman code".
     • You need to be able to apply this algorithm to examples.
• Week 9:
  1. Understand the precise (and general) algorithmic solution for Making Change via dynamic programming.
  2. Of central importance here is the recurrence relation for the two-dimensional array c, and how to compute it.
  3. Also understand how, after having determined the optimal numbers of coins, one can determine which coins actually to use.
  4. You should be able to run the algorithm on paper for examples.
  5. Understand the complexity analysis of the algorithm.
  6. Know the general characterisation of the dynamic programming strategy.
  7. Know the All-pairs Shortest Paths problem.
  8. Know the Floyd-Warshall algorithm, especially its recurrence relation.
  9. Know its time and space complexity.
• Week 10:
  1. Know what a "decision problem" is (input a binary string, output "0" or "1" (or "No" resp. "Yes")).
  2. Understand intuitively the two main complexity classes:
     • P ("polynomial time")
     • NP ("nondeterministic polynomial time" --- a guessed solution can be verified in polynomial time).
  3. Know examples for problems in NP.
  4. Understand intuitively the notion of "NP-completeness" (a (decision) problem is NP-complete iff it is in NP and every other problem in NP can be reduced to it).
  5. The central NP-completeness is the "SAT problem":
     1. Know "CNF" (conjunctive normal form).
     2. Understand how logical puzzles can be expressed as SAT problems.
     3. Know how to express graph-colouring problems as SAT problems.
  6. Regarding graph-colouring:
     1. The decision problem is called "k-colouring", for some fixed natural number k.
     2. The 3-colouring problem (decide whether a graph is 3-colourable or not) is NP-complete.
     3. While the 2-colouring problem can be decided in polynomial time.

Coursework

General rules

• The two assignments are to be done in pairs (as in the lab classes) using the following algorithm:
  1. Each one of you produces solutions to the assignment questions independently.
  2. Then, and only then, do you compare your solutions to your partner's solutions, and you try to convince each other of the correctness of your own solutions.
  3. In the process, you help each other clarify the difficulties you are having with the material.
  4. Finally, each of you writes up the solution on his/her own.
  5. You must indicate name and student number of your partner clearly on your solution.
  6. This procedure is used, as the assignments will all be paper-and-pencil exercises, typically requiring a degree of contemplation.
  7. You will not be writing any programs, so you will not get any mechanical feedback (compiler errors, erroneous output) indicating that your solutions are incorrect.
  8. Your partner will act as an independent reviewer to identify your "compile-time" and "run-time" logical errors.
• See here for information on how to submit the coursework.

First coursework

• Sheet
• Solution

Second coursework

• Sheet
• Solution

Links

• The article Analysis of algorithms gives a reasonable overview.
• You might have a look at Graph , though it contains much which goes beyond what we are doing.
• Breadth-first search fits well with our point of view.
• Depth-first search leaves out discovery and finishing time, and fits a bit less well; but you might still have a look.
• Binary search tree is a nice overview on binary search trees.
• And also Disjoint-set data structure is a nice overview.
• Amortised analysis is another readable overview.

Oliver Kullmann

Last modified: Fri Jan 20 10:36:41 GMT 2012