COMSM1402 Advanced Algorithms

To register on this unit if you are not in the Computer Science department, please email Caroline Higgins, caroline@compsci.bristol.ac.uk .

Instructors	Office	Hours
Raphaël Clifford	MVB 3.15	Thursday 3-5pm
TA: Alex Popa	MVB 3.46	Wed 1-2pm

Lecture times

Thursday, 10:00-11:00, Phys 3.34
Friday, 10:00-11:00, Phys 3.34

Forum: The forum can provide a useful way for you to help each other and to get questions answered by the lecturers.

COMSM1402 Forum

Feel free to post questions and so on; we'll try to answer them as soon as possible.

Muhammad ibn Musa-al-Khwarizmi
(c. 780-850)

Lectures

1-20 topic scribe notes readings
1 8 Oct Mathematical preliminaries Aram Harrow pdf, ps, tex probability lectures 10 - 13 (section 2)
2 9 Oct Hash functions CLRS 11.3.3, MU p. 90--93, 314--328
3 15 Oct Static perfect hashing pdf, tex Hashing, FKS, cuckoo hashing
4 16 Oct Cuckoo hashing pdf, tex See previous
5 22 Oct Bloom filters MU p. 109--111, 329, MIT notes, Bloom filter survey
6 23 Oct van Emde Boas trees Notes 1,2
7 29 Oct Suffix trees External notes, External notes II, Gusfield Section II.
8 30 Oct Suffix arrays Gusfield p.149--156.
Section 3 of linear time construction paper.
This comparison of 3 methods.
9 5 Nov Approx matching + Constant time LCA Simplified LCA paper
10 6 Nov Pattern matching under Hamming norm Internal notes below
11 12 Nov Pattern matching under Hamming norm contd. Original paper, Simplified internal notes
12 13 Nov As above
13 19 Nov As above
14 20 Nov As above
15 26 Nov Maximum Flow CLRS ch. 26, DPV ch 7, notes, video lecture
16 27 Nov Max flow/min-cut + Linear Programming As above
17 3 Dec Linear Programming and Game Theory CLRS ch. 26, DPV ch 7
18 4 Dec Intro. to Approximation Algorithms CLRS ch. 35, DPV ch 8 2007 scribed notes one, two
19 10 Dec Approximation Algorithms (contd.) CLRS ch. 35, DPV ch 9
20 11 Dec Counting perfect matchings Ashley Montanaro slides

1-20		topic	scribe	notes	readings
1	8 Oct	Mathematical preliminaries	Aram Harrow	pdf, ps, tex	probability lectures 10 - 13 (section 2)
2	9 Oct	Hash functions	CLRS 11.3.3, MU p. 90--93, 314--328
3	15 Oct	Static perfect hashing		pdf, tex	Hashing, FKS, cuckoo hashing
4	16 Oct	Cuckoo hashing		pdf, tex	See previous
5	22 Oct	Bloom filters	MU p. 109--111, 329, MIT notes, Bloom filter survey
6	23 Oct	van Emde Boas trees	Notes 1,2
7	29 Oct	Suffix trees	External notes, External notes II, Gusfield Section II.
8	30 Oct	Suffix arrays	Gusfield p.149--156. Section 3 of linear time construction paper. This comparison of 3 methods.
9	5 Nov	Approx matching + Constant time LCA	Simplified LCA paper
10	6 Nov	Pattern matching under Hamming norm	Internal notes below
11	12 Nov	Pattern matching under Hamming norm contd.	Original paper, Simplified internal notes
12	13 Nov	As above
13	19 Nov	As above
14	20 Nov	As above
15	26 Nov	Maximum Flow	CLRS ch. 26, DPV ch 7, notes, video lecture
16	27 Nov	Max flow/min-cut + Linear Programming	As above
17	3 Dec	Linear Programming and Game Theory	CLRS ch. 26, DPV ch 7
18	4 Dec	Intro. to Approximation Algorithms	CLRS ch. 35, DPV ch 8	2007 scribed notes one, two
19	10 Dec	Approximation Algorithms (contd.)	CLRS ch. 35, DPV ch 9
20	11 Dec	Counting perfect matchings	Ashley Montanaro	slides

Coursework

The coursework can is now available. Deadline start of lecture on Friday 11th December or up until midnight through the electronic submission system on that day.