King
Fahd University of Petroleum and Minerals
Department
of Information and Computer Science
ICS
202 Data Structures – Spring Semester 1999-2000 (992)
Instructor: Bashir Mohammed Ghandi Office Location: 22/124-9, Tel: 4016.
E-mail:
bmghandi@ccse.kfupm.edu.sa
Course Page : http://www.ccse.kfupm.edu.sa/~bmghandi
or :
http://icswww.ccse.kfupm.edu.sa/bmghandi
Office Hours: Saturdays & Mondays: 9-11a.m ; Wednesday: 9-10a.m.
Textbook:
Data
Structures and Program Design in C
by R Kruse, CL Tondo and B Leung, Prentice Hall, 1997.
Grading
Policy:
|
Assignments & Quizzes |
20% |
|
Major Exam I – Monday 21 February 2000, 6 p.m-7:30p.m, Build#6,Room#125 |
20% |
|
Major Exam II – Sunday 23 April 2000, 6:30p.m-8:30p.m, Build#6,Room125 |
25% |
|
Final Exam: As scheduled by the registrar |
35% |
Important
Notes:
·
Programming
assignments are to be submitted in class on the due date; otherwise, they will
not be accepted.
·
Attendance will
be taken at the beginning of each class.
·
Every unexcused
absence leads to a loss of 0.5% mark.
·
A total of 9
unexcused absences qualify you for a
DN grade.
Course contents
Elementary Concepts
Concepts of data structures (data types) and algorithms. Elementary data types, Abstraction and Abstract Data Types (Ch. 4.8). Principles of good algorithm and program design (Ch. 2.6.2).
Algorithm Analysis and Sorting (chap 6 and chap 7)
Algorithm analysis, space/time trade-offs, the Big-O notation (Ch. 6.7). Application to simple, familiar algorithms on searching (Sequential and binary search) (Ch. 6.2 & 6.4) and sorting (selection sort, bubble sort, and insertion sort) (Ch. 7.2 & 7.3). Merge sort, quick sort (Ch. 7.6 & 7.7).
Tables and Information retrieval (chap 8)
Table Abstract Data Type. Hashing, and Conflict resolution. Radix Sort. Proxmap sort (chapter 8).
Stacks and Recursion (chap 3)
Review and applications of Stacks, Recursion. (chapter 3)
Queues and Linked Lists (chap 4 & 5)
Review and applications of queues. Linked lists, Doubly and circularly linked list (chap 5).
Trees (Ch. 9)
Binary trees. Heap trees, Ordered binary trees, B-trees. Implementation of binary trees using linear and linked lists. Tree traversals. Binary tree insertion and deletion. Heapsort (7.9).
Graphs (Ch. 11)
Directed and undirected graphs. Depth-first search, breadth-first search. Topological sorting. Minimum Spanning Tress. Shortest path (Dijkstra algorithm).