Home
About the School
Contact and People
Future Undergraduate Students
Prospective Postgraduates
Current Students
Current Postgraduates
Research
IT News
Awards
Industry Links and Prizes
School and IT Information
Other
Internal Information
|
Lectures
|
Note that the lecture notes are written using LaTeX and are available as PDF files. In order to view the lecture notes, you will need the viewer called acroread, which is available on the lab machines. Alternatively, to view the files on your home computer, you can download and install the PDF Reader software, available free from Adobe Systems. Recordings of the lectures will be available shortly after each lecture. Not all the links below are currently enabled, but they will be as we progress through the semester.
Lecture Topics and Download Materials
The topics to be covered include: | PDF Downloads | | 1. Introduction: a brief introduction to the basic concepts of an algorithm, computational problems and the time complexity of an algorithm. We examine basic sorting algorithms. | Notes: intro4.pdf | | 2. Graph algorithms: an introduction to a standard collection of fundamental algorithms on graphs, including the following subtopics: Definition of a graph and basic graph theoretic terminology, breadth-first and depth-first searching, topological sort, minimum spanning tree and efficient data structures for the Kruskal and Prim algorithms, priority-first search and Dijkstra's algorithm, all-pairs shortest paths algorithms and the A* algorithm. | Notes: graphs4.pdf Appendix: AStarProof.pdf | 3. String and File processing: including pattern-matching, the Rabin-Karp algorithm, the Knuth-Morris-Pratt algorithm and the Boyer-Moore algorithm. We also examine a dynamic programming solution for the longest common subsequence problem, and some data compression algorithms. | Notes: strings4.pdf
| | 4. Network flow: including flow networks and flows, maximising flow by the Ford-Fulkerson method, cuts and the max-flow, min-cut theorem, heuristics for network flow (Edmonds-Karp). | Notes: flow4.pdf | | 5. Optimization Algorithms: Optimization problems including the travelling salesman problem, the graph domination problem, the knapsack problem, and linear programming problems. For these problems we consider dynamic and linear programing solutions, heuristic search methods including hill-climbing, simulated annealing and genetic algorithms. | Notes: optimization4.pdf
|
|
|
