King Fahd University of Petroleum & Minerals
College of Computer Sciences and Engineering
ICS 202: Data Structures (3-3-4)
Summer Semester 2007-2008 (073)
<< Syllabus >>
N.B. All course material and related resources are made available
through WebCT and will be added here soon.
Instructor: Dr. EL-SAYED EL-ALFY
Office: 22-108
Phone: 03-860-1930,
E-mail: alfy@kfupm.edu.sa,
URL: http://faculty.kfupm.edu.sa/ics/alfy/
Office Hours: UT @ 10:20am-11:00am or by appointment
Class Time & Venue:
| Day | Time | Room | |
| Lecture | SUMTW | 9:20am-10:20am | 24-141 |
| Lab | UT | 2:10pm-5:10pm | 22-416 |
Course Catalog Description:
Introduction to Design Patterns. Introduction to Algorithm Analysis. Review and Analysis of Linear Data Structures. Recursion, Trees and Graphs. Implementations of Tree and Graph Traversals. BST, AVL, Heaps and B-Trees. Hashing Techniques. Data Compression. Memory Management. Practice in Developing Medium Scale Programs.
Pre-requisites: ICS 201.
Objectives
Introduce students to fundamental data structures; their algorithms, implementations and applications.
Teach students how to analyze the efficiency of the fundamental data structures in terms of both time and space so that they are able to decide what data structure is suitable for a given problem.
Learning Outcomes
Upon completion of the course, you should be able to:
- Apply object oriented concepts (inheritance, polymorphism, design patterns, etc.) in software design.
- Implement various data structures and their algorithms, and apply them in implementing simple applications.
- Analyze simple algorithms and determine their efficiency using big-O notation.
- Apply the knowledge of data structures to other application domains like data compression and memory management.
Required Material
Data
Structures and Algorithms in Java, 2nd Edition,
Thomson Course Learning, 2005. ISBN 0-534-49252-5.
Data Structures and Algorithms with Object Oriented Design Patterns in Java, [Online]
Bruno R. Preiss,
John Wiley & Sons, 2000.
Grading Policy
|
Activity |
Weight |
|
Laboratory [Participation = 0.5% * 12, Open Book Programming Quizzes = 14%] |
20% |
|
Practice Assignments |
0 % |
|
Project |
13 % |
|
Quizzes |
12 % |
|
Midterm |
25 % |
|
Final Exam |
30 % |
Detailed Schedule of Lectures, Labs, Homework, Quizzes & Exams (Tentative)
Note: Material will be updated as necessary.
| Date | Lectures | Laboratories | Readings | ||||||
| Lec # | Topics | Other Activities | Lab # | Topics | Other Activities | ||||
| 5-Jul | Sat | 1 | Review of OO Concepts | Preiss Chapter 5 | |||||
| 6-Jul | Sun | 2 | Design Patterns | 0 |
Getting Started <download> |
||||
| 7-Jul | Mon | 3 | Complexity Analysis I | Preiss Chapter 3, Drozdek Chapter 2 | |||||
| 8-Jul | Tue | 4 | Complexity Analysis II | 01 | Design Patterns I | ||||
| 9-Jul | Wed | 5 | Complexity Analysis II (Cont.) | HW1 Assign | |||||
| 10-Jul | Thu | ||||||||
| 11-Jul | Fri | ||||||||
| 12-Jul | Sat | 6 | Singly Linked List | Quiz 1 | Preiss Chapter 4, Drozdek Chapter 3 | ||||
| 13-Jul | Sun | 7 | Doubly Linked List | 02 | Design Patterns II | ||||
| 14-Jul | Mon | 8 | Stacks | Preiss Chapter 6, Drozdek Chapter 4 | |||||
| 15-Jul | Tue | 9 | Queues | HW1 Due | 03 | Linked List | |||
| 16-Jul | Wed | 10 | Recursion I | HW2 Assign | Slides, Drozdek Chapter 5 | ||||
| 17-Jul | Thu | ||||||||
| 18-Jul | Fri | ||||||||
| 19-Jul | Sat | 11 | Recursion II | ||||||
| 20-Jul | Sun | 12 | Analysis of Recursive Algorithms | 04 | Stacks & Queues | Lab Quiz1: Design Patterns & Linked Lists | |||
| 21-Jul | Mon | 13 | Trees | HW2 Due | Preiss Chapter 9, Drozdek Chapter 6 and 7, Heap Sort (Drozdek pg 484) | ||||
| 22-Jul | Tue | 14 | Binary Search Trees (BSTs) | 05 | Recursion | ||||
| 23-Jul | Wed | 15 | Tree Traversal Algorithms | ||||||
| 24-Jul | Thu | ||||||||
| 25-Jul | Fri | ||||||||
| 26-Jul | Sat | 16 | Heaps | ||||||
| 27-Jul | Sun | 17 | AVL Trees I | 06 | Binary Trees & BST | ||||
| 28-Jul | Mon | 18 | AVL Trees II | ||||||
| 29-Jul | Tue | 19 | B-Trees | 07 | Binary Heaps | ||||
| 30-Jul | Wed | 20 | Huffman Coding | Quiz 2: on Complexity, Linked Lists, Stacks and Queues | |||||
| 31-Jul | Thu | ||||||||
| 1-Aug | Fri | ||||||||
| 2-Aug | Sat | 21 | Introduction to Graphs | HW3 Assign | Preiss Chapter 16, Drozdek Chapter 8 | ||||
| 3-Aug | Sun | 22 | Graph Implementation | 08 | AVL Trees | ||||
| 4-Aug | Mon | 23 | Graph Traversals | ||||||
| 5-Aug | Tue | 24 | Graphs: Topological Sort | 09 | Huffman Coding | ||||
| 6-Aug | Wed | 25 | Review | HW3 Due | |||||
| 7-Aug | Thu | ||||||||
| 8-Aug | Fri | ||||||||
| 9-Aug | Sat | 26 | Review | Midterm: from lecture 1 to lecture 20 | |||||
| 10-Aug | Sun | 27 | Graphs: Cycles and Connectedness | 10 | Review | Lab Quiz 2: Stack, Queue, BST | |||
| 11-Aug | Mon | 28 | Graphs: Shortest Path Algorithm | ||||||
| 12-Aug | Tue | 29 | Graphs: Minimum Spanning Tree (MST) | 11 | Graphs | ||||
| 13-Aug | Wed | 30 | Hashing I | HW4 Assign | Preiss Chapter 8 | ||||
| 14-Aug | Thu | ||||||||
| 15-Aug | Fri | ||||||||
| 16-Aug | Sat | 31 | Hashing II | ||||||
| 17-Aug | Sun | 32 | Hashing III | 12 | Graph Algorithms | ||||
| 18-Aug | Mon | 33 | Data Compression: LZ78 | Slides, Drozdek Chapter 10 | |||||
| 19-Aug | Tue | 34 | Data Compression: LZW | HW4 Due | 13 | Hashing | |||
| 20-Aug | Wed | 35 | Garbage Collection | Preiss Chapter 13, Drozdek Chapter 12 | |||||
| 21-Aug | Thu | ||||||||
| 22-Aug | Fri | ||||||||
| 23-Aug | Sat | 36 | Memory Management | Quiz3: Graphs + Hashing | |||||
| 24-Aug | Sun | 37 | Review & Project Presentations | 14 | Review | Lab Quiz 3: Heaps, Huffman, Graphs | |||
| 25-Aug | Mon | 38 | |||||||
| 27-Aug | Wed |
Final Exam As Posted by the Registrar
|
|||||||
Download Software (portable versions)
1. J2SE6 Documentation
2. JCreator
3. JGrasp
4. JEdit
5. SmartDraw
Additional Notes
Course Website. Students are required to periodically check the course website and download course materials as needed. Lecture notes will be made available ahead of time for students to read, print out, and bring to class. It is much easier to take additional notes this way, and gain the most out of class. Several resources will be posted through the website as well. Keys to quizzes and exams are generally discussed during class as time permits but solutions will not be posted. WebCT will be used for communication and interaction, posting and submitting assignments, posting grades, posting sample exams, etc. Also it is expected that you get benefit of the discussion board by raising questions or answering questions put by others.
Attendance: It is very important to attend all classes. Attendance will be checked at the beginning of each class. More than 9 lectures will result in a DN grade without prior warning. To avoid being considered as absent, an official excuse must be shown no later than one week of return to class. There is no penalty for the first two absences, after that you lose one full percentage per absence.
Class participation: Students are expected to be active and collaborative in the discussion of the topics. Homework assignments are given for you for practice but it is expected that you hand in a typed solution before or on the due date. You will not do well in the quizzes and exams if you do not do the homework assignments.
No make up quizzes or exams will be given.
Re-grading policy: if you have a complaint about any of your grades, discuss it with the instructor no later than a week of distributing the grades (except for the final). Only legitimate concerns on grading should be discussed.
Office Hours. Students are encouraged to use the office hours to clarify any part of the material that is not clear; however the instructor will only provide hints if it is an assigned task but not solve it.
Lab Guidelines. For the Labs, you must store all your work in a package ics202 on your z-drive. We shall be adding files to this package in each lab. Your lab exercises should be stored in sub-packages lab01, lab02, etc. You are required to observe this package structure throughout the semester. A student is required to prepare himself for a laboratory session by reading the laboratory document for that session, by studying the code, and by reading all lecture material related to the session. THIS PREPARATION IS ESSENTIAL FOR A STUDENT TO BE ABLE TO DO THE LABORATORY TASKS. The lab instructor will not conduct lectures; he may just elaborate on specific issues related to the current lab session.
Academic honesty: Students are expected to abide by all the university regulations on academic honesty. Cheating will be reported to the Department Chairman and will be severely penalized. Although collaboration and sharing knowledge is highly encouraged, copying others’ work without proper citation, either in part or full, is considered plagiarism. Whenever in doubt, review the university guidelines or consult the instructor.
Courtesy: Students are expected to be courteous toward the instructor and their classmates throughout the duration of this course. Talking while someone else is speaking will not be tolerated. Furthermore, all cell phones must be turned off during class. In addition, students are expected to be in class on time. Late arrivals will disrupt the class session. If you are 15 minutes late, you will be marked as absent and will not be permitted to enter the class. More importantly, you are not allowed to leave the class unless it is of an urgent matter. To contact me, please use email through WebCT whenever possible and avoid using phone calls or written notes. When necessary to send an email through the university email system, please indicate ICS202-073 in the "Subject" field of your email, e.g. ICS202-073: Question about HW1.
888 Best of luck!! 888
Data Structures and Algorithms in Java, 4th edition,
Michael T. Goodrich and Roberto Tamassia,
John Wiley & Sons, 2006.
Data Structures, Algorithms, and Applications in Java, 2nd edition,
Sartaj Sahni,
Silicon Press, 2004.
William H. Ford and William R. Topp,
Prentice Hall, 2005.
Data Structures and the Java Collections Framework, 2nd edition,
William Collins,
McGraw-Hill, 2005.
Object-oriented Data Structures Using Java, 2nd edition,
N. Dale, D. Joyce, C. Weems,
Jones and Bartlett, 2006.
Data Structures and Algorithms in Java
Prentice-Hall, 2006.
Data Structures & Other Objects Using Java, 3rd edition,
Michael Main,
Addison-Wesley, 2006.
Data Structures and Problem Solving Using Java, 2nd edition
Mark Allen Weiss,
Addison-Wesley, 2001.
Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein
Mc-Graw Hill, 2003
Data Structures and Algorithm Analysis in Java, 2nd edition,
Addison-Wesley, 2007
Algorithms in Java, Parts 1-4 (Fundamental Algorithms, Data Structures, Sorting, Searching), 2002
Algorithms in Java, Part 5 (Graph Algorithms), 2003
Others
Algorithms: Design Techniques and Analysis
M. H. Alsuwaiyel
World Scientific Publishing Company, 1998
The Algorithm Design Manual, 2nd edition,
Steven S. Skiena
Springer, 2008
Data Structures and Algorithms
Alfred V. Aho, John E. Hopcroft, Jeffrey Ullman
Addison-Wesley, 1982
Fundamentals of Computer Algorithms
Ellis Horowitz
Data Structure Techniques
Thomas A. Standish
The Java Language Specification, Third Edition, Sun Microsystems, Inc. 2005
James Gosling
Bill Joy
Guy Steele
Gilad Bracha
The Design Patterns Java Companion, 1998 [online] [pdf]
James W. Cooper
