Undergraduate Course: Algorithms and Data Structures (INFR10052)
Course Outline
School  School of Informatics 
College  College of Science and Engineering 
Credit level (Normal year taken)  SCQF Level 10 (Year 3 Undergraduate) 
Availability  Available to all students 
SCQF Credits  10 
ECTS Credits  5 
Summary  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. 
Course description 
Introductory concepts
Review of CS2. Models of computation; time and space complexity; upper and lower bounds, bigO and bigOmega 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; worstcase, bestcase and averagecase.
Data structures: Disjoint sets
The "disjoint sets'' (unionfind) abstract data type: specification and implementations as lists and trees. Unionbyrank, pathcompression, etc., "heuristics''. Applications to finding minimum spanning trees.
Dynamic programming
Introduction to the technique; examples: Matrixchain multiplication, Longest common subsequences.
Graph/Network algorithms
Network flow, Maxflow/mincut theorem, FordFulkerson algorithm.
Geometric algorithms
Convex hull of a set of points (in 2d).
Relevant QAA Computing Curriculum Sections: Data Structures and Algorithms

Entry Requirements (not applicable to Visiting Students)
Prerequisites 

Corequisites  
Prohibited Combinations  
Other requirements  Undergraduate students must have passed either Informatics 2B  Algorithms, Data Structures, Learning (INFR08009) or Informatics 2  Introduction to Algorithms and Data Structures (INFR08026), and in addition must be familiar with concepts from discrete mathematics and probability theory as described below. For single honours Informatics students the mathematics requirements are met by passing Discrete Mathematics and Probability (INFR08031) or both Probability with Applications (MATH08067) AND Discrete Mathematics and Mathematical Reasoning (INFR08023). Students who took different secondyear Maths courses should get permission of the Course organiser (lecturer).
MSc students should have taken an introductory algorithms course and mathematics covering the material below, and should get permission from the Course organiser (lecturer).
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, Onotation, proof by contradiction, confidence in proving theorems. 
Information for Visiting Students
Prerequisites  Visiting students are required to have comparable background to that assumed by the course prerequisites listed in the Degree Regulations & Programmes of Study. If in doubt, consult the Course organiser (lecturer). 
High Demand Course? 
Yes 
Course Delivery Information

Academic year 2020/21, Available to all students (SV1)

Quota: None 
Course Start 
Semester 1 
Timetable 
Timetable 
Learning and Teaching activities (Further Info) 
Total Hours:
100
(
Lecture Hours 20,
Seminar/Tutorial Hours 8,
Summative Assessment Hours 2,
Programme Level Learning and Teaching Hours 2,
Directed Learning and Independent Learning Hours
68 )

Assessment (Further Info) 
Written Exam
50 %,
Coursework
50 %,
Practical Exam
0 %

Additional Information (Assessment) 
In addition to the written exam, there is one piece of assessed coursework.
This should take about 89 hours.
There will also be one formative assessment (56 hours) earlier in the semester to allow you to submit work and obtain feedback on your submission; that earlier piece of formative work will not contribute to your overall grade.

Feedback 
Not entered 
No Exam Information 
Learning Outcomes
On completion of this course, the student will be able to:
 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.
 Should be able to demonstrate familiarity with algorithmic strategies such as DivideandConquer, 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.
 Should be able to construct clear and rigorous arguments to prove correctness/runningtime bounds of algorithms, and should be able to present these arguments in writing.
 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.
 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 averagecase analyses of the runningtime of an algorithm, as well as worstcase analyses.

Reading List
Introduction to Algorithms (3rd Edition), Cormen, Leiserson, Rivest, Stein: . MIT Press, 2002. (Course text) 
Contacts
Course organiser  Dr Richard Mayr
Tel: (0131 6)50 5130
Email: rmayr@staffmail.ed.ac.uk 
Course secretary  Mrs Michelle Bain
Tel: (0131 6)51 7607
Email: michelle.bain@ed.ac.uk 

