CS270 Algorithms 2016/17
Messages
 Now in Week 10 (beginning 5/12/2016).
 Stewart Powell gives a tutorial Monday 1617 (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 email to
his/her official student emailaddress.
 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: 1617 final tutorial with Stewart.
 Tuesday 13/12/2016: 1112 discussion of solution to Coursework I.
 Tuesday 13/12/2016: 1314 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 1617, Faraday Lecture Theatre
 Tuesday 1112, Faraday K
 Tuesday 1314, Faraday Lecture Theatre
 Wednesday 1112, 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 1314, Linux Lab
 B: Monday 1516, Linux Lab
 C: Friday 1011, Linux Lab
 D: Friday 1213, 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 email 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 lastyear'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 worstcase.
 Know and understand Insertion Sort.
 You should be able to write pseudocode for it.
 Know how bestcase and worstcase 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:
 BigOh, Omega and Theta.
 Know the definitions.
 Know basic examples.
 More examples to come in the rest of the module.
 DivideandConquer:
 Understand the basic principle.
 More examples to come in the rest of the module.
 MinMax Algorithm:
 Understand the naive algorithms and why it takes 2n2 comparisons.
 Understand the idea for the divideandconquer version.
 Understand the MinMax recurrence.
 Week 3:
 Understand MergeSort 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 DFSforest, 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 insertionoperation.
 QuickSort:
 This algorithm has a simple idea.
 The only little complication is in the inplace 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