# DEGREE REGULATIONS & PROGRAMMES OF STUDY 2012/2013- ARCHIVE for reference onlyTHIS PAGE IS OUT OF DATE

 University Homepage DRPS Homepage DRPS Search DRPS Contact
DRPS : Course Catalogue : School of Informatics : Informatics

# Undergraduate Course: Algorithms and Data Structures (INFR09006)

 School School of Informatics College College of Science and Engineering Course type Standard Availability Available to all students Credit level (Normal year taken) SCQF Level 9 (Year 3 Undergraduate) Credits 10 Home subject area Informatics Other subject area None Course website http://www.inf.ed.ac.uk/teaching/courses/ads Taught in Gaelic? No Course description The course aims to provide general techniques for the design of efficient algorithms and, in parallel, develop appropriate mathematical tools for analysing their performance. In this, it broadens and deepens the study of algorithms and data structures initiated in INF2. The focus is on algorithms, more than data structures. Along the way, problem solving skills are exercised and developed.
 Pre-requisites Students MUST have passed: Informatics 2B - Algorithms, Data Structures, Learning (INFR08009) AND ( Mathematics for Informatics 3a (MATH08042) OR Foundations of Calculus (MATH08005)) AND ( Mathematics for Informatics 3b (MATH08043) OR Linear Algebra (MATH08007)) AND ( Mathematics for Informatics 4a (MATH08044) OR Methods of Applied Mathematics (MATH08035)) AND ( Mathematics for Informatics 4b (MATH08045) OR Several Variable Calculus (MATH08006)) Co-requisites Prohibited Combinations Other requirements Students who did not take Inf2B should get special permission from the course lecturer. Successful completion of Year 2 of an Informatics Single or Combined Degree, or equivalent by permission of the School. This course has the following mathematics prerequisites: 1 - Calculus: limits, sums, integration, differentiation, recurrence relations, the Master theorem. 2 - Graph theory: graphs, digraphs, components, trees, weighted graphs, DFS, BFS. 3 - Probability: random variables, expectation, variance, Markov's inequality, Chebychev's inequality 4 - Linear algebra: vectors, matrices, matrix multiplication, scalar products. 5 - Complex numbers: the imaginary unit i, addition and multiplication in C, exponentiation. 6 - Generalities: induction, O-notation, proof by contradiction. Additional Costs None
 Pre-requisites None Displayed in Visiting Students Prospectus? Yes
 Delivery period: 2012/13 Semester 1, Available to all students (SV1) Learn enabled:  No Quota:  None Location Activity Description Weeks Monday Tuesday Wednesday Thursday Friday Central Lecture 1-11 10:00 - 10:50 Central Lecture 1-11 10:00 - 10:50 First Class Week 1, Tuesday, 10:00 - 10:50, Zone: Central. D.02 Forrest Hill Exam Information Exam Diet Paper Name Hours:Minutes Main Exam Diet S2 (April/May) 2:00 Resit Exam Diet (August) 2:00 Delivery period: 2012/13 Semester 1, Part-year visiting students only (VV1) Learn enabled:  No Quota:  None Location Activity Description Weeks Monday Tuesday Wednesday Thursday Friday Central Lecture 1-11 10:00 - 10:50 Central Lecture 1-11 10:00 - 10:50 First Class Week 1, Tuesday, 10:00 - 10:50, Zone: Central. D.02 Forrest Hill Exam Information Exam Diet Paper Name Hours:Minutes Main Exam Diet S1 (December) 2:00
 1 - Should be able to describe, and implement, the major algorithms for well known combinatorial problems such as Sorting, Matrix Multiplication, Minimum Spanning Trees, and other problems listed in the syllabus. 2 - Should be able to demonstrate familiarity with algorithmic strategies such as Divide-and-Conquer, the Greedy strategy and Dynamic Programming; and should be able to test these strategies on new problems and identify whether or not they are likely to be useful for those problems. 3 - Should be able to construct clear and rigorous arguments to prove correctness/running-time bounds of algorithms, and should be able to present these arguments in writing. 4 - Should be able to explain the importance of the data structures used in a particular implementation of an algorithm, and how the data structure that is used can affect the running time. 5 - Should be able to construct simple lower bound arguments for algorithmic problems, and to understand the relationship between upper and lower bounds. Also should be able to perform simple average-case analyses of the running-time of an algorithm, as well as worst-case analyses.
 Written Examination 75 Assessed Assignments 25 Oral Presentations 0 Assessment In addition to the written exam there are two pieces of assessed coursework, which involve pen and paper exercises and programming. If delivered in semester 1, this course will have an option for semester 1 only visiting undergraduate students, providing assessment prior to the end of the calendar year.
 None
 Academic description Not entered Syllabus Introductory concepts Review of CS2. Models of computation; time and space complexity; upper and lower bounds, big-O and big-Omega notation; average and worst case analysis. Divide and conquer Matrix multiplication: Strassen's algorithm; the discrete Fourier transform (DFT), the fast Fourier transform (FFT). Expressing the runtime of a recursive algorithm as a recurrence relation; solving recurrence relations. Sorting Quicksort and its analysis; worst-case, best-case and average-case. Data structures: Disjoint sets The ``disjoint sets'' (union-find) abstract data type: specification and implementations as lists and trees. Union-by-rank, path-compression, etc., ``heuristics''. Applications to finding minimum spanning trees. Dynamic programming Introduction to the technique; examples: Matrix-chain multiplication, Longest common subsequences. Graph/Network algorithms Network flow, Max-flow/min-cut theorem, Ford-Fulkerson algorithm. Geometric algorithms Convex hull of a set of points (in 2-d). Relevant QAA Computing Curriculum Sections: Data Structures and Algorithms Transferable skills Not entered Reading list * Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (3rd Edition). MIT Press, 2002. (Course text) Study Abroad Not entered Study Pattern Lectures 20 Tutorials 8 Timetabled Laboratories 0 Non-timetabled assessed assignments 25 Private Study/Other 47 Total 100 Keywords Not entered
 Course organiser Mr Vijayanand Nagarajan Tel: (0131 6)51 3440 Email: vijay.nagarajan@ed.ac.uk Course secretary Mrs Victoria Swann Tel: (0131 6)51 7607 Email: Vicky.Swann@ed.ac.uk
 Navigation Help & Information Home Introduction Glossary Search DPTs and Courses Regulations Regulations Degree Programmes Introduction Browse DPTs Courses Introduction Humanities and Social Science Science and Engineering Medicine and Veterinary Medicine Other Information Timetab Prospectuses Important Information
© Copyright 2012 The University of Edinburgh - 14 January 2013 4:08 am