King Fahd University of Petroleum & Minerals
College of Computer Sciences and Engineering
ICS 202: Data Structures (3-3-4)
Spring Semester 2008-2009 (082)
<< 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: SMW @ 09:00am-10:00am or by appointment
Class Times & Venues:
|
Office: 22:108 Telephone: 1930 E-mail: alfy@kfupm.edu.sa |
Office: 22:148-2 Telephone: 2081 E-mail: said@kfupm.edu.sa Office Hours: UMT 1:00-2:00pm or by appointment |
|
Office: 22:101 Telephone: 7699 E-mail: hamdi@kfupm.edu.sa Office Hours: SMW 10:00-11:00AM or by appointment |
Office: 22:313 Telephone: 1715 E-mail: wasfi@kfupm.edu.sa Office Hours: SMW 11:00AM-1:00PM or by appointment |
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 |
20% (see Lab Guidelines) |
|
Homework (4 to 5) [common] |
10% |
|
Quizzes (4 to 5) |
10% |
|
EXAM 1: Wednesday April 8, 2009, 7:00-9:00pm [common] |
15% |
|
EXAM 2: Wednesday May 27, 2009, 7:00-9:00pm [common] |
20% |
|
Final Exam: Sunday June 21, 2009, 7:30am [common] |
25% |
Detailed Schedule of Lectures, Labs, Homework, Quizzes & Exams (Tentative)
Note: Material will be updated as necessary.
|
Wk |
Date |
Day |
LECTURES |
|
LABS |
||||
|
No |
Topic |
Appointment |
|
No |
Lab Topic |
Appointment |
|||
|
1 |
28-Feb |
Sat |
1 |
|
|
0 |
Jcreator and Packages |
|
|
|
2-Mar |
Mon |
2 |
|
|
|||||
|
4-Mar |
Wed |
3 |
Design Patterns (cont.) |
|
|||||
|
|
5-Mar |
Thurs |
4 |
|
|
|
|
|
|
|
2 |
7- Mar |
Sat |
5 |
Complexity Analysis (cont.) |
|
|
1 |
Design Patterns (intro)
|
|
|
9- Mar |
Mon |
6 |
Complexity Analysis (cont.) <exercise set> |
|
|
||||
|
11- Mar |
Wed |
7 |
|
|
|||||
|
3 |
14- Mar |
Sat |
8 |
Singly Linked Lists (cont.) |
|
|
2 |
Design Patterns (more) |
|
|
16- Mar |
Mon |
9 |
Doubly Linked Lists (cont.) |
|
|
||||
|
18- Mar |
Wed |
10 |
|
|
|||||
|
4 |
21-Mar |
Sat |
11 |
HW1 Due |
|
3 |
Linked Lists |
Lab Quiz 1: Design Patterns |
|
|
23- Mar |
Mon |
12 |
|
|
|||||
|
25- Mar |
Wed |
13 |
Recursion (cont.) |
|
|
||||
|
5 |
28- Mar |
Sat |
14 |
Recursion (cont.) |
|
4 |
Stacks and Queues |
|
|
|
30- Mar |
Mon |
15 |
|
|
|||||
|
1-Apr |
Wed |
16 |
Analysis of Recursive Algorithms (cont.) |
|
|
||||
|
6 |
4-Apr |
Sat |
17 |
|
|
5 |
Recursion |
Lab Quiz 2: Linked Lists, Stacs, Queues |
|
|
6- Apr |
Mon |
18 |
Binary Trees (cont.) |
HW2 Due |
|
||||
|
8- Apr |
Wed |
19 |
|
|
|||||
|
8- Apr |
Wed |
|
Major Exam #1 |
7:00-9:00pm |
|||||
|
7 |
11- Apr |
Sat |
20 |
|
|
6 |
Binary Trees & BST |
|
|
|
13- Apr |
Mon |
21 |
|
|
|||||
|
15- Apr |
Wed |
22 |
AVL Trees |
|
|||||
|
8 |
18- Apr |
Sat |
23 |
AVL Trees |
|
|
7 |
Binary Heaps |
|
|
20- Apr |
Mon |
24 |
|
|
|||||
|
|
22- Apr |
Wed |
25 |
|
|
|
|
||
|
|
|
|
|
Midterm Vacation |
|
|
|
|
|
|
9 |
2-May |
Sat |
26 |
B-Trees |
|
|
8 |
AVL Trees |
|
|
4- May |
Mon |
27 |
B+-Trees |
|
|
||||
|
6- May |
Wed |
28 |
|
|
|||||
|
10 |
9- May |
Sat |
29 |
HW3 Due |
|
9 |
Huffman Coding |
|
|
|
11- May |
Mon |
30 |
Graphs (Implementation) |
|
|
||||
|
13- May |
Wed |
31 |
|
|
|||||
|
11 |
16- May |
Sat |
32 |
|
|
10 |
Revision
|
Lab Quiz 3: Trees |
|
|
18- May |
Mon |
33 |
|
|
|||||
|
20- May |
Wed |
34 |
|
||||||
|
12 |
23- May |
Sat |
35 |
Minimum Spanning Trees |
|
|
11 |
Graphs
|
|
|
25- May |
Mon |
36 |
|
|
|||||
|
27- May |
Wed |
37 |
|
|
|||||
|
27- May |
Wed |
|
Major Exam #2 |
7:00-9:00pm |
|||||
|
13 |
30- May |
Sat |
38 |
|
|
12 |
Graphs Algorithms
|
|
|
|
1- Jun |
Mon |
39 |
Hashing (cont.) |
|
|
||||
|
3- Jun |
Wed |
40 |
HW4 Due |
|
|||||
|
14 |
6- Jun |
Sat |
41 |
Garbage Collection |
|
|
13 |
Hashing |
|
|
8- Jun |
Mon |
42 |
|
|
|||||
|
10- Jun |
Wed |
43 |
|
|
|||||
|
15 |
13- Jun |
Sat |
44 |
Review |
|
|
14 |
Revision |
Lab Quiz 4: Graphs |
|
15- Jun |
Mon |
45 |
Review |
|
|
||||
| Final Exam As Posted by the
Registrar
|
|||||||||
Download Software (portable versions)
Homework assignments
Homework #01 (Due Saturday March 21, 2009)
Homework #02 (Due Midnight Saturday April 18, 2009)
Homework #03 (Solution) (Due Midnight Sunday May 10, 2009)
Homework #04 (Due Midnight Sunday May 24,
2009)
Quizzes
| Section 1 | Section 2 | Section 3 |
| Quiz 1 (Solution) | Quiz 1 (Solution) | Quiz 1 (Solution) |
| Quiz 2 (Solution) | Quiz 2 (Solution) | Quiz 2 (Solution) |
| Quiz 3 (Solution) | Quiz 3 (Solution) | Quiz 3 (Solution) |
| Quiz 4 (Solution) | Quiz 4 (Solution) | Quiz 4 (Solution) |
| Quiz 5 (Solution) |
Some Previous Exams
|
Exam |
Semester |
| Major Exam 1 | 081 - 072 - 071 - 062 |
| Major Exam 2 | 081 - 072 - 071 - 062 - 061 |
| Final Exam | 081 - 072 - 071 - 062 - 061 |
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.
Check the WebCT course page and the ICS 202 Webpage regularly for announcements and updates.
Attendance (for lecture part only): It is very important to attend all classes. Attendance will be checked at the beginning of each class. More than 9 lectures will result automatically in a DN grade without prior warning. To avoid being considered as absent, an official excuse (ONLY by an official letter from the Dean of Student’s office) 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.
Homework submission: Hard copies of homework are due at the beginning of the first class after the electronic submission deadline. No late homework will be accepted. Discussing questions among your classmates and on WebCT is highly encouraged. Copying homework solutions from each other is NOT permitted and will be considered CHEATING.
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.
Exams, homework assignments and quizzes are generally CHALLENGING. 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). If for some reason you cannot contact the instructor within this period, send him an email requesting an appointment. The email should be sent within the 24-hour time period. 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.
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 instructors 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 and exams. 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.
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.
1. Grade Distribution:
· 6 % Participation (0.5% * 12)
· 14 % Four Laboratory Quizzes (3% + 3% + 4% + 4%)
(a) There will be no make-up for missed laboratory quizzes.
(b) A student will not be allowed to take a laboratory quiz in a different section; unless permitted by the laboratory instructor to do so.
(c) Being able to configure the Software used in the lab, being able to fix the common ICS 202 laboratory errors (as explained in Laboratory session 0), and making sure a student’s Z drive is properly configured (before coming for a quiz) is considered part of a quiz.
(d) Each laboratory quiz will be an open-book programming quiz.
(e) A student will be given zero in a quiz if he misses a lab quiz in his section without an official excuse or if he copies even a small portion of his quiz from another student. All students involved in a cheating offence will get a zero grade. It is a student’s responsibility to protect his work.
(f) A student will be given a grade of zero (out of 0.5) for the participation part of the laboratory if he does any of the following:
(1) He is absent without an official excuse (2) He is late by more than 15 minutes (3) He does not come back promptly to the lab after a prayer break (4) He leaves the laboratory session without the instructors permission (5) He does not attempt to do the current laboratory tasks (6) He does anything not related to the current laboratory session, like connecting to a Web site other than the ICS 202 WebCT site without the instructor’s permission, or reading other material. A STUDENT MUST BE DOING THE LABORATORY TASKS EVEN IF THE LABORATORY INSTRUCTOR IS LATE OR HE IS NOT PRESENT IN THE LAB (7) He does not pay attention when the instructor is explaining something (8) He disrupts the laboratory session. Discussions are allowed (except during a quiz); but they must be done in a manner that does not disturb other students. A STUDENT IS REQUIRED TO PUT HIS MOBILE PHONE IN SILENT MODE DURING THE LABORATORY SESSIONS.
2. Announcement of Laboratory quizzes: The dates and the topics that will be covered in each quiz are in the course syllabus. You are required to know these dates. Students may or may not be reminded about the quizzes.
3. Preparation for each laboratory session: 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.
4. Laboratory Quiz solutions will be discussed in the appropriate laboratory sessions. Solutions will not be posted. This is to encourage student participation.
5. Complaints regarding Laboratory quiz grades must be submitted to the laboratory instructor within one week of the posting of the grades for that particular quiz.
6. Laboratory Instructor’s Office Hours: Students are encouraged to use the office hours to clarify any part of the laboratory tasks that is not clear; however the instructor will only provide hints and not solve a task.
7. Some aspects of the laboratory tasks may be asked in the ICS 202 major exams and the final exam. Students are thus required to take the laboratory part of this course seriously.
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
