Lectures

• Lecture 1: Intro (pdf)
• Lecture 2: String Algs (intro) (pdf)
• Lecture 3: String search (pdf)
• Lecture 4: Pattern Matching (pdf)
• Lecture 5: Compression (pdf)
• Lecture 7: Parsing (intro) (pdf)
• Lecture 8: Recursive Descent Parsing (pdf)
• Lecture 9: Graphs (pdf)
• Lecture 10: Graph search (pdf)
• Lecture 11: Pointers (revision) (pdf)
• Lecture 12: Shortest path (pdf)
• Lecture 13: Inheritance (revision) (pdf)
• Lecture 14: Critical path (pdf)
• Lecture 15: Geometric Algs (pdf)
• Lecture 16: C++ + Geometric Algs (pdf)

Assignments/labs

• Ex1 string search/compression (pdf)

  If you are interested in the Biological background, and more advanced algorithms for molecular biology, you may like to look here (see "intro concepts" lecture, and "pairwise alignment" lecture. Latter is relevant to second part of assignment).

Tutorials

• String search etc (a word doc).
• Tutorial 2:
  • Given the following frequency data, calculate the codes for each character based on Huffman encoding (ie, contruct the tree and read off the codes) A:30, B:15, C:50, D:40, E:100
  • For substitutional compression, a dictionary may be constructed. Frequently occuring words end up in the dictionary. Show how it is constructed given this string: "that this and that hat has that"
• Parsing: Tutorial based on exam Qs.

Textbooks and resources

A useful introduction to the C++ libraries is here .

If you want a quick revision of C++, covering roughly the material you've had so far, then these two parts: basics , and classes and templates seem useful.

There's a good C tutorial here; It might be of interest even if you're writing in C++, as much of its the same.

There's also a C++ site written by a student , for students. Its a bit rude about lecturers, but I can take it.. It actually looks quite useful.

Mail Alison Cawsey if you have problems.