Subject Code: ECP1026 Objective: To provide the students with the basic understanding of algorithms and data structures for more efficient program writing. Pre-Requisite: ECP1016: Computer and Program Design Credit Hours: 3 Contact Hours: 57 hours (lectures and tutorials) Assessment: Test/Quiz: 20% Tutorial:10 % Assignment: 10% Final Examination: 60% Laboratory: Supervised tutorials done in many computer labs, including Multimedia Design Lab, Multimedia Computing Lab, etc. Tutorials are mostly programming tutorials, while a few involve application of theory in paper exercises. The programming tutorials will be conducted using the GCC compiler in the LINUX operating system. References: I. Chai & J. D. White, “Structuring Data and Building Algorithms”, McGraw-Hill Education (Asia), 2009, ISBN 978-007-127188-2. (Textbook) Kruse, Tondo & Leong, “Data Structures and Program Design in C”, 2nd Edition, Prentice Hall, 1997. Kingston, “Algorithms and Data Structures: Design, Correctness, Analysis”, 2nd Edition, Addison-Wesley, 1997.

### Course Contents

• Theory of Computing
Finite state automata, Turing machines.

• Structuring Data

• Variables, pointers, arrays, records, linked lists, trees, graphs, sets. Stacks, queues. Implementation using arrays, linked lists, etc. Traversal of binary trees.

• Building Algorithms

• Basic techniques, such as recursion, mutual recursion, backtracking and look-ahead. Key concepts in qualifying algorithms in terms of asymptotic performance, such as time complexity, Big-O.

• Algorithms and Data Structures in Action

• Sequential search, binary search, hashing. Insertion sort, selection sort, merges sort, heap sort, quick sort, NP-hard problems.

### Learning Outcome of Subject (% of contribution)

At the completion of the subject, students should be able to perform the following tasks:

• LO1 - Describe the basic theories and elements of computer science, such as FSA and Turing Machines. (cognitive – understanding, Level 2) - 14%
• LO2 – Apply typical data structures learned in this course, such as arrays, pointers, records, linked. lists, trees, graphs and sets (cognitive – applying, Level 3) - 46%
• LO3 - Apply typical algorithms learned in this course, such as recursion, backtracking and look-ahead. (cognitive – applying, Level 3) - 10%
• LO4 – Analyse an algorithm in terms of asymptotic performance, such as time complexity and Big-O. (cognitive – analysing, Level 4) - 6%
• LO5 – Blend data structures and algorithms together to solve three representative types of programming problems: searching, sorting and NP-hard problem solving. (cognitive – creating, Level 6) - 24%

### Programme Outcomes (% of contribution)

• PO1 - Ability to acquire and apply fundamental principles of science and engineering - 44%
• PO2 - Capability to communicate effectively - 4%
• PO3 - Acquisition of technical competence in specialised areas of engineering discipline - 29%
• PO4 - Ability to identify, formulate and model problems and find engineering solutions based on a system approach - 9%
• PO5 - Ability to conduct investigation and research on engineering problems in a chosen field of study - 7%
• PO6 - Understanding of the importance of sustainability and cost-effectiveness in design and development of engineering solutions - 7%