Kuwait University
College of Engineering and Petroleum

Department of Electrical and Computer Engineering




ECE 207: Data Structures (3-0-3)



Syllabus




Catalog Description

This is a second programming course that introduces algorithmic problem solving - Basic data structures: Arrays, Stacks, Queues, Linked-lists, Trees, and graphs - Examples involving searching, sorting, and hashing techniques utilizing different data structures - Two hours laboratory-sized recitation per week.

Prerequisite: 0600-200, 0612-203.

Text Book:

Horowitz and Sahni, "Fundamentals of Data Structures", Freeman and Company, 1993.

Goals:

(1) To teach students the basics of algorithmic problem solving.

(2) To introduce students to some fundamental data structures.

(3) To introduce students to some sorting, searching and hashing techniques.


Topics:

1.
Introductiont & Basic Concepts. (2 hr.)
Quick review of C programming language, System Life Cycle, Abstract Data types & Data Structures, Recursion, Mathematical Proof techniques, Algorithm Analysis.

2.
Lists. (6 hr.)
Array-based list implementation, Linked lists, Doubly lists, Circular linked lists.

3.
Stacks. (4 hr.)
Arra-based stacks, Linked stacks, Array-based versus linked stacks, implementing recursion.

4.
Queues. (5 hr.)
Arra-based Queues, Linked Queues, Array-based versus linked queues.

5.
Trees. (3 hr.)
Binary Trees: Definition & properties, Taversals, Implementations, Binary search trees, Heaps & Pripority queues; General Trees: Definiton & Terminology, Partent pointer implementation.

6.
Graphs. (5 hr.)
Graph terminology & representations, Implemetations, Traversals, Shortest-path problems, Minimum-cost spanning trees.

7.
Sorting Techniques. (12 hr.)
Terminology & Notation, Tree-based Sorting Algorithms: Insertion Sort, Bubble Sort, Selection Sort, Cost of Exchange Sorting; Other Sorting Algorithms: Shell-sort, Quik-sort, Merge-sort, Heap-sort, Radix-sort; Empirical comparison of sorting algorithms, Lower bounds for sorting.

8.
Searching Techniques. (5 hr.)
Searching ordered lists, searching sets, Hashing techniques.

Computer Usage:

Students will use PCs running tools for programming using the C language.

Laboratory Experiments:

There are two hours laboratory-sized recitation per week.

Grading Policy:

20% Quizzes and Homeworks
15% Major Exam I (Tentatively scheduled during week 5)
15% Major Exam II (Tentatively scheduled during week 11)
10% Laboratory Work
40% Final Exam (As scheduled by the Registrar)

ABET Category content:


Engineering Design: 1 credits or 33 %
Engineering Science: 2 credits or 67 %


Prepared by: Prof. Mostafa Abd-El-Barr. Date: January 1999.