|Module Name||Algorithms and Data Structures|
|Module Short Title||CS2010|
|Semester Taught||Michaelmas & Hillary Term|
|Contact Hours||Lecture & Tutorial hours: 33|
Lab hours with lecturer and demonstrators per lab group: 11
Total hours: 44
|Module Personnel||Dr Vasileios Koutavas (Michelmas Term)|
Dr Ivana Dusparic (Hillary Term)
Having successfully completed this module students will:
- Have gained significant knowledge on algorithms and data structures, and the mathematical theory and techniques to evaluate their efficiency and effectiveness.
- Have the ability to evaluate algorithms in terms of their running time and memory space requirements and classify those algorithms in the major complexity classes using appropriate performance models.
- Be able to efficiently implement the operations of the main data structures used in most programming.
- Gain experience through experiments in implementing effective new and existing algorithms.
- Be able to identify the most suitable data structures and algorithms for each programming problem based on the parameters of the problem, the advantages and limitations of each data structura and algorithm, the resources avaliable, the desired performance criteria etc.
- Be able to design and implement robust, effective and well-structured Java programs using industry standards such as Abstract Data Types and the approaches of unit testing, test coverage, Design by Contract, and pre-/post-conditions. Students will be able to use the last two approaches to avoid defensive programming.
The aim of the module is threefold:
- To teach effective programming and problem solving, using a core toolset of classical algorithms and data structures.
- To introduce the methods for evaluating the performance and requirements of programs written by the students
- To promote effective software engineering by using well-established techniques for code modularity, structuring, debugging and readablity, such as Design by Contract, and unit testing.
- Asymptotic growth functions and analysis of source code to derive running time and space requirements
- Amortised running time analysis of algorithms
- Permutations, Combinations and Sets
- Array and linked list implementations of stacks and queues.
- Doubly linked lists
- Binary trees, binary search trees, balanced search trees, B-trees
- Hash tables
- Undirected, directed and weighted graph implementations using adjacency lists
- Special topics
- Recursion vs iteration; tree traversals
- Greedy algorithms
- Divide and conquer
- Graph algorithms
- Searching and Sorting algorithms
- Special topics
- Java generics
- JUnit testing
- Design by Contract
|Recommended Reading List|
Algorithms (4th Edition)
Robert Sedgewick and Kevin Wayne
Pearson Education 2011
Other recommended textbooks:
Introduction to Programming Using Java (6th Edition)
David J. Eck
Introduction to Algorithms (3rd Edition)
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
MIT Press 2009
Algorithms and Data Structures
Data Structures and Algorithms
John E. Hopcroft and Jeffrey D. Ullman.
|Module Prerequisites||An introductory course on programming with Java. CS1011 and CS1012|
35% Coursework, 65% Exam
Assessment in the annual examinations is by written exam’ (65%) and coursework (35%). Assessment in the supplementals is by 100% written examination only.
|Academic Year of Data|