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:
- Monday 12/12/2016: 16-17 final tutorial with Stewart.
- Tuesday 13/12/2016: 11-12 discussion of solution to Coursework I.
- Tuesday 13/12/2016: 13-14 revision lecture, and end of module.
- 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
- Monday 16-17, Faraday Lecture Theatre
- Tuesday 11-12, Faraday K
- Tuesday 13-14, Faraday Lecture Theatre
- Wednesday 11-12, Faraday M
- 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)
- A: Monday 13-14, Linux Lab
- B: Monday 15-16, Linux Lab
- C: Friday 10-11, Linux Lab
- D: Friday 12-13, Linux Lab
- 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:
- You need then to do the lab session on our own.
- Write down your solutions on the labsheet.
- This must be presented in person to one of the postgrads.
- Finally, you need to e-mail me, with CC to the postgrads,
stating why you missed which week, and that you did it now.
- But, of course, this must be an exception.
- Course work
- First coursework: Handed out 2/11/2016, deadline 17/11/2016.
- 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).
- Week 1 (3.10. - 7.10.2016):
- Week 2 (10.10. - 14.10.2016):
- Week 3 (17.10. - 21.10.2016):
- Week 4 (19.10. - 23.10.2015):
- Week 5 (26.10 - 30.10.2015):
- Week 6 (2.11. - 6.11.2015):
- Week 7 (9.11.2014 - 13.11.2015):
- Week 8 (16.11. - 20.11.2015):
- Week 9 (23.11.2014 - 27.11.2014):
- Week 10 (30.11. - 4.12.2015):
- Week 11 (7.12. - 11.12.2015):
Lab sessions
(Recall that the lab for week x takes place in week x+1.)
Learning goals
- Week 1:
- Know and understand the basic framework for algorithm analysis.
- Counting "basic operations".
- Measuring input size.
- Analysing the worst-case.
- 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).
- Know the basic functions x^e, b^x, log_b(x), log_2(x) = lg(x), and
floor and ceiling.
- And recall the summation symbol (big Sigma).
- Week 2:
- Big-Oh, Omega and Theta.
- Know the definitions.
- Know basic examples.
- More examples to come in the rest of the module.
- Divide-and-Conquer:
- Understand the basic principle.
- More examples to come in the rest of the module.
- Min-Max Algorithm:
- Understand the naive algorithms and why it takes 2n-2 comparisons.
- Understand the idea for the divide-and-conquer version.
- Understand the Min-Max recurrence.
- Week 3:
- Understand Merge-Sort and its analysis.
- Understand the basic idea for recurrences.
- Know the Master theorem, and how to apply it.
- Week 4+5:
- There are various important notions and concepts
to learn.
- 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.
- The notions are:
- "Graphs", "undirected" and "directed" ("digraphs")
- "Vertices" and "edges" resp. "arcs" (directed edges)
- "Trees" (free ones) and "rooted trees"
- "Spanning trees" and "rooted spanning trees"; also "spanning
forests"
- The "root", the "leaves" and the "children" of a "node" in a
rooted tree
- "Paths" in graphs and digraphs
- "Connected graphs"
- "Cycles" in graphs and digraphs
- Connected graphs without cycles are trees, digraphs without cycles
are "directed acyclic graphs" ("dags").
- Know the two main representations of graphs and digraphs (adjacency
lists and adjacency matrices).
- The first main algorithm is BFS:
- 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.
- One can also run it on a digraph, and one can also restart it
so that it covers the whole (possibly disconnected) graph.
- The output then is a collection of rooted trees, containing
shortest paths from the respective root to all other reachable
vertices.
- The second main algorithm is DFS:
- 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.
- Again, we can run it on a digraph.
- The application we considered is for topological sorting.
- Week 6:
- 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!)
- Know and understand "stacks": What are the four stack operations,
and what is their meaning?
- Know and understand "queues": What are the four queue operations,
and what is their meaning?
- Week 7:
- Know how to perform "binary search", and what its complexity is.
- Linked lists: Know their implementation, and how insertion and
deletion works.
- Understand "pointers".
- Understand the chain of notions
- tree
- rooted tree
- ordered rooted tree
- binary tree
What is the height of a rooted tree?
- Understand the representation of binary trees.
- Week 8:
- Understand the notion of a "binary search tree".
- Understand the inorder traversal for binary trees.
- Understand how the order requirement for a binary search tree
interacts with the inorder traversal.
- Understand how to search for a key in a binary search tree, and
what the complexity of this operation is.
- Understand the computation of minimum and maximum in binary search
trees, and the complexity of these operations.
- The same for the computation of predecessors and successors.
- Understand the idea and the algorithm for insertion.
- Understand the idea and the algorithm for deletion.
- Understand the topic of "bad orders" ("they are possible, but
unlikely").
- Week 9:
- Recall "dictionaries".
- Understand the concept of a "hash function".
- Know what a "collision" is, and what "perfec hash functions" are.
- Understand "direct addressing".
- Understand how collision resolution by "chaining" works.
- Know the formula for the expected time for searching, and
understand the ideas underlying the discussion of general hash
functions.
- Week 10:
- Heaps:
- Know the notion of a "complete binary tree", and how to efficiently
implement it via arrays.
- "Binary heaps" are complete binary trees with the "heap property".
- Understand "heapification".
- Understand how we can use heapification to efficiently build a
binary heap.
- Another application of heapification is "Heap Sort".
- And for priority queues we just need an insertion-operation.
- Quick-Sort:
- This algorithm has a simple idea.
- The only little complication is in the in-place partitioning.
- 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.
Second coursework
Deadline is 9/12/2016.
Links