CS-270 Algorithms 2016/17

Messages

• Now in Week 10 (beginning 5/12/2016).
• Stewart Powell gives a tutorial Monday 16-17 (Faraday Lecture Theatre, as usual).
• Second coursework: available below.
• Marks for first coursework are sent the night from Wednesday to Thursday; Thursday morning everybody should have obtained an e-mail to his/her official student e-mail-address.
• For the lab sessions this Friday 9/12/2016 and the following Monday 12/12/2016 (the last lab sessions) you have the choice between working on Week 09 (hashing) or Week 10 (binary heaps), or both, if you wish.
• Everybody who attended at least one lab session will get the one mark for Week 10 for free.
• The plan for the final week, Week 11, is as follows:
  1. Monday 12/12/2016: 16-17 final tutorial with Stewart.
  2. Tuesday 13/12/2016: 11-12 discussion of solution to Coursework I.
  3. Tuesday 13/12/2016: 13-14 revision lecture, and end of module.
  4. No labs Friday 16/12/2016 or thereafter.

General information

• The url of this page is http://cs.swan.ac.uk/~csoliver/Algorithms201617_p0ESG2hWo1/index.html .
• Lectures
  1. Monday 16-17, Faraday Lecture Theatre
  2. Tuesday 11-12, Faraday K
  3. Tuesday 13-14, Faraday Lecture Theatre
  4. Wednesday 11-12, Faraday M
  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 four sessions)
  1. A: Monday 13-14, Linux Lab
  2. B: Monday 15-16, Linux Lab
  3. C: Friday 10-11, Linux Lab
  4. D: Friday 12-13, Linux Lab
  5. From Week 05 (commencing 31/10/2016) the rhythm is no longer Monday+Friday (in the same week), but Friday+Monday (separated by the weekend).
  The postgraduate demonstrators are
  • Hoda Abbasizanjani 881550@Swansea.ac.uk
  • Naif Alharbi naif.alharbi@gmail.com
• The lab session practice the material of previous week (so they run Week 02 -- Week 11).
• If you can't make a lab session:
  1. You need then to do the lab session on our own.
  2. Write down your solutions on the labsheet.
  3. This must be presented in person to one of the postgrads.
  4. Finally, you need to e-mail me, with CC to the postgrads, stating why you missed which week, and that you did it now.
  5. But, of course, this must be an exception.
• Course work
  1. First coursework: Handed out 2/11/2016, deadline 17/11/2016.
  2. Second coursework: Handed out 24/11/2016, deadline 9/12/2016.
• The textbook: Introduction to Algorithms

Script

Dates from last year mean that the script has not been updated (but you might have a look already, if you wish, at last-year's script).

1. Week 1 (3.10. - 7.10.2016):
   • Printing
   • Viewing
   • Slides
2. Week 2 (10.10. - 14.10.2016):
   • Printing
   • Viewing
   • Slides
3. Week 3 (17.10. - 21.10.2016):
   • Printing
   • Viewing
   • Slides
4. Week 4 (19.10. - 23.10.2015):
   • Printing
   • Viewing
   • Slides
5. Week 5 (26.10 - 30.10.2015):
   • Printing
   • Viewing
   • Slides
6. Week 6 (2.11. - 6.11.2015):
   • Printing
   • Viewing
   • Slides
7. Week 7 (9.11.2014 - 13.11.2015):
   • Printing
   • Viewing
   • Slides
8. Week 8 (16.11. - 20.11.2015):
   • Printing
   • Viewing
   • Slides
9. Week 9 (23.11.2014 - 27.11.2014):
   • Printing
   • Viewing
   • Slides
10. Week 10 (30.11. - 4.12.2015):
    • Printing
    • Viewing
    • Slides
11. Week 11 (7.12. - 11.12.2015):
    • Printing
    • Viewing
    • Slides

Lab sessions

(Recall that the lab for week x takes place in week x+1.)

• 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 the basic framework for algorithm analysis.
     • Counting "basic operations".
     • Measuring input size.
     • Analysing the worst-case.
  2. 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).
  3. Know the basic functions x^e, b^x, log_b(x), log_2(x) = lg(x), and floor and ceiling.
  4. 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.
• Week 4+5:
  1. There are various important notions and concepts to learn.
  2. To start, know (be able to reproduce) the (precise) definitions, where you understand all the terms in the definition, so 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 6:
  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 "buffers", "priority queues" and "dictionaries", (in this context)? (Such notions are defined by the operations!)
  2. Know and understand "stacks": What are the four stack operations, and what is their meaning?
  3. Know and understand "queues": What are the four queue operations, and what is their meaning?
• Week 7:
  1. Know how to perform "binary search", and what its complexity is.
  2. Linked lists: Know their implementation, and how insertion and deletion works.
  3. Understand "pointers".
  4. Understand the chain of notions
     • tree
     • rooted tree
     • ordered rooted tree
     • binary tree
     What is the height of a rooted tree?
  5. Understand the representation of binary trees.
• Week 8:
  1. Understand the notion of a "binary search tree".
  2. Understand the inorder traversal for binary trees.
  3. Understand how the order requirement for a binary search tree interacts with the inorder traversal.
  4. Understand how to search for a key in a binary search tree, and what the complexity of this operation is.
  5. Understand the computation of minimum and maximum in binary search trees, and the complexity of these operations.
  6. The same for the computation of predecessors and successors.
  7. Understand the idea and the algorithm for insertion.
  8. Understand the idea and the algorithm for deletion.
  9. Understand the topic of "bad orders" ("they are possible, but unlikely").
• Week 9:
  1. Recall "dictionaries".
  2. Understand the concept of a "hash function".
  3. Know what a "collision" is, and what "perfec hash functions" are.
  4. Understand "direct addressing".
  5. Understand how collision resolution by "chaining" works.
  6. Know the formula for the expected time for searching, and understand the ideas underlying the discussion of general hash functions.
• Week 10:
  • Heaps:
    1. Know the notion of a "complete binary tree", and how to efficiently implement it via arrays.
    2. "Binary heaps" are complete binary trees with the "heap property".
    3. Understand "heapification".
    4. Understand how we can use heapification to efficiently build a binary heap.
    5. Another application of heapification is "Heap Sort".
    6. And for priority queues we just need an insertion-operation.
  • Quick-Sort:
    1. This algorithm has a simple idea.
    2. The only little complication is in the in-place partitioning.
    3. Know some key points about the analysis.

Coursework

General rules

• See here for information on how to submit the coursework.

First coursework

Deadline is 17/11/2016.

• Sheet

Second coursework

Deadline is 9/12/2016.

• Sheet

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.

Oliver Kullmann

Last modified: Wed Dec 7 23:58:44 GMT 2016