Module Details
The information contained in this module specification was correct at the time of publication but may be subject to change, either during the session because of unforeseen circumstances, or following review of the module at the end of the session. Queries about the module should be directed to the member of staff with responsibility for the module.
Title ALGORITHMS AND COMPUTATION
Code CKIT532
Coordinator Dr F Grasso
Computer Science
Floriana@liverpool.ac.uk
Year CATS Level Semester CATS Value
Session 2019-20 Level 7 FHEQ Whole Session 15

Aims

1. To provide students with a comprehensive understanding of the role and importance of algorithms with respect to solutions to computational problems.

2. To enable students to design, implement and develop new algorithms where no existing suitable algorithm is available.

3. To provide students with an in-depth understanding of the formal concepts of algorithm analysis in the context of: performance, correctness and complexity, polynomial-time verification and NP-completeness.

4. To provide an in-depth, systematic and critical understanding of: selected algorithms for sorting, searching, graph operations and path finding; and network flow algorithms.

Learning Outcomes

(LO1) Critically appraise the role and importance of algorithms.

(LO2) Use the knowledge and abilities gained to identify appropriate algorithms to solve given computational problems and to design new algorithms where no suitable algorithm exists for a given purpose.

(LO3) Critically analyse the performance, correctness and complexity of a given algorithm.

(LO4) Apply systematically knowledge concerning algorithms for sorting, searching, graph operations, pathfinding and network flow and the application of such algorithms.

(LO5) Apply conceptual knowledge of computational geometry, polynomial-time verification and NP-completeness to analyse and evaluate algorithms.

(S1) Organisational skills

(S2) IT skills

(S3) Communication and collaboration online participating in digital networks for learning and research

(S4) Learning skills online studying and learning effectively in technology-rich environments, formal and informal

(S5) Problem solving/critical thinking/creativity

(S6) Team (group) working respecting others, co-operating, negotiating / persuading, awareness of interdependence with others

Syllabus
 

Week 1: Role and importance of algorithms.
Naive solutions; intelligent approaches; best, expected and worst case behaviours of algorithms; algorithm complexity, big "O" notation and complexity classes (performance families); time and space trade-offs in algorithms; and empirical measurements of performance.

Week 2: Algorithm Building blocks.
Algorithm and Pseudo code Template Format, Empirical Evaluation Format, common approaches to designing algorithms (Algorithmic Strategies).

Week 3: Analysis and comparison of sorting algorithms.
Insertion Sort, Selection Sort, Heap Sort, Quicksort, Bucket Sort, Merge Sort.

Week 4: Analysis and comparison of searching algorithms.
Sequential/Linear Search, Binary Search, Hash-Based Search, Bloom Filter, Binary Search Tree, analysis and comparison of searching algorithms.

Week 5: Analysis and comparison of graph algorithms.
Depth-First Search, Breadth-First Search, Single-Sou rce Shortest Path, All Pairs Shortest Path, Minimum Spanning Tree Algorithms .

Week 6: Analysis and comparison of tree searching algorithms.
Game Trees, Minimax, NegMax, AlphaBeta, Search Trees, A*Search, analysis and comparison of searching tree algorithms.

Week 7: Network Flow Algorithms.
Their applications in: Assignment, Bipartite Matching, Maximum Flow, Minimum Cost Flow, Transportation and Transhipment.

Week 8: Computational Geometry and NP-Completeness.
Convex Hull algorithms, finding intersecting line segments, Voronoi Diagrams, LineSweep, polynomial-time verification, NP-completeness and reducibility, NP-completeness proofs and problems, approximation algorithms.

Teaching and Learning Strategies

Teaching Method 1 - online learning
Description: Weekly seminar supported by asynchronous discussion in a virtual classroom environment facilitated by an online instructor.
Attendance Recorded: Yes
Notes: Number of hours per week that students are expected to attend the virtual classroom so as to participate in discussion, dedicated to group work and individual assessment is 7.5.

Teaching Schedule
  Lectures Seminars Tutorials Lab Practicals Fieldwork Placement Other TOTAL
Study Hours           60

 60
Timetable (if known)              
Private Study 90
TOTAL HOURS 150

Assessment
EXAM Duration Timing
(Semester)		 % of
final
mark		 Resit/resubmission
opportunity		 Penalty for late
submission		 Notes
             
CONTINUOUS Duration Timing
(Semester)		 % of
final
mark		 Resit/resubmission
opportunity		 Penalty for late
submission		 Notes
Report: Group Project on network flow algorithms Standard UoL penalty applies for late submission. This is not an anonymous assessment. Assessment Schedule (When) :Week 7  One week: 1500-2000     9       
Report: Group project on designing and evaluating complex algorithms Standard UoL penalty applies for late submission. This is not an anonymous assessment. Assessment Schedule (When) :Week 8  One week: 1500-2000     9       
Moot/debate: 8 discussion questions Standard UoL penalty applies for late submission. This is not an anonymous assessment. Assessment Schedule (When) :Whole session  Weekly Discussion Qu    40       
Report: Performance/correctness/complexity of algorithms Standard UoL penalty applies for late submission. This is not an anonymous assessment. Assessment Schedule (When) :Week 1  One week: 350-500 wo    7       
Programming: Algorithm analysis Non-standard penalty applies for late submission - This is not an anonymous assessment. Assessment Schedule (When) :Week 2  One week    7       
Programming: Sorting algorithms Standard UoL penalty applies for late submission. This is not an anonymous assessment. Assessment Schedule (When) :Week 3  One week    7       
Programming: Searching algorithms Standard UoL penalty applies for late submission. This is not an anonymous assessment. Assessment Schedule (When) :Week 4  One week    7       
Programming: Graph algorithms Standard UoL penalty applies for late submission. This is not an anonymous assessment. Assessment Schedule (When) :Week 5  One week    7       
Programming: Path finding algorithms Standard UoL penalty applies for late submission. This is not an anonymous assessment. Assessment Schedule (When) :Week 6  One week    7       

Recommended Texts
Reading lists are managed at readinglists.liverpool.ac.uk. Click here to access the reading lists for this module.