ECP1032

Algorithm and Data Structure
Subject Code:	ECP1032
Objective:	To provide the students with the basic understanding of algorithm and error analysis, and program data structure for more efficient program writing.
Pre-requisite:	ECP1022: Program Design
Credit Hours:	3
Contact Hours:	35 hours of Lectures 10 hours of Assignments/Tutorials
References:	Richard Neapolitan and Kumarss Naimipur, " Foundations of Algorithms ", D. C. Heath and Company, Toronto, 1996. Robert L. Kruse, " Data Structures and Program Design ", Prentice Hall, 1994. Kamal B. Rajiani, " Programming in C with Numerical Methods for Engineers ', Prentice Hall, 1996.

Algorithm in General (6 hours)
Algorithm design. Comparison of algorithms. Computational cost function. The concept of "big O". Worst case and average case performance of algorithms.
Algorithm Design in Various Applications (8 hours)
Sorting. Quicksort. Mergesort. Merging two sorted files. Recursive formulation. Space requirement. Memory management. Time-space trade-off. Selection. Ranking. Recurrence. Recursive algorithms. Infeasibility. models of computation. Turing machines. Complexity classes. Examples.
Data Structures (7 hours)
Records, files, pointers - Abstract Data Types (ADT) - Array based implementation of ADT list - Linked List data structures - Operations on linked lists - Circularly linked lists.
Stacks, Queues and Binary Trees (6 hours)
Array based and linked list implementation of stacks and queues - Application of stacks and queues - Binary trees - Operations on binary trees - Implementation of binary trees.
Numerical Analysis and Program Writing (8 hours)
Absolute and relative errors. Error propagation in arithmetic operations. Examples of error build up. Iteration, error estimation, order of a process, stopping criteria and examples. .Solution of simultaneous linear equations. Residuals. Jacobi's method. Gauss-Seidel method. Error estimation and iterative refinement. Least square fitting. Random number generation. Linear congruential methods.

Faculty of Engineering
Multimedia University

last updated: 5 July 1999

Algorithm and Data Structure