Algorithm and Data Structure
||To provide the students with the basic understanding of algorithm and error analysis, and program data structure for more efficient program writing.
||ECP1022: Program Design
||35 hours of Lectures
10 hours of Assignments/Tutorials
- 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
Faculty of Engineering
last updated: 5 July 1999