CPCS204 - Data Structures

Syllabus

Data Structure I- Fall 2018 (1^st Semester)

Data Structures Learning Objects: https://abasuhail.kau.edu.sa/Pages-DSLO.aspx

Course Pre-Requisites: CPCS – 202 & CPCS - 203

Course Description

“This course is an introduction to data structures that intends to train students for problem solving by using simple data structures and developing algorithms. The students will mainly learn static and dynamic data structures, including arrays, linked lists, stacks, queues and trees. They will also learn some basic searching and sorting algorithms and algorithm analysis tools, particularly ‘Big O’.”

For clarity, this class is a follow up to the CPCS-203 material, in which you learned (ideally) the syntax and use of major constructs of JAVA (conditional statements, loops, functions, arrays, pointers, strings, structures, and file I/O) as well as object-oriented programming. This course now focuses on the actual algorithmic design (i.e., how efficient are your algorithms), analysis of running time, a variety of abstract data types (new data structures), and lastly, but definitely not least important, recursion.

Course Text Book

"Object-Oriented Data Structures Using Java", Nell Dale, Jones & Bartlett Learning; 3rd edition (February 25, 2011). ISBN-10: 1449613543. ISBN-13: 978-1449613549. (While beneficial, this book is not necessary. The PPT slides, provided on Blackboard, are more than sufficient.)

Class Schedule

Lecture (Theory)         2 times a week for 80 minutes

Lecture (Lab)              once a week for 120 minutes

Attendance Policy: Class attendance and Lab attendance is mandatory. Students must attend at least 75% of theory as well as lab classes. If anyone miss more than 25% of the classes, he will not be allowed to take the final exam.

Course Instructor: Dr. Abdullah Basuhail

Exams: There will be two midterm exams and one final exam. As the material in this course builds on itself, each exam can be considered “cumulative”, and material from the beginning of the semester is certainly not off-limits for the 2nd Midterm. And of course, the Final exam is cumulative as well.

Quizzes: Quizzes will consist of a small number of basic questions on material that has been covered recently, with the goal of forcing students to keep up with the material. Quizzes will be announced on Blackboard AND the quiz will be on Blackboard (so you can take the quiz at your home). The quiz will usually be 20 minutes, and we will make it available for 6 hours. There will be no makeup quizzes. It is your responsibility to take the quiz during this open availability period.

Students Assessments Policy

Course Learning Outcomes

By the completion of the course the students should be able to:

1. Differentiate between static and dynamic data structures. Determine the tradeoffs between different data structures and identify applications of them. (SO – b)

2: Design and analyze more efficient algorithms for solving basic problems.(SO –j)

3. Comprehend and trace the output of a given piece of code or algorithm.  (SO – a)

4. Demonstrate linear and binary search techniques in problem solving.      (SO – a)

5. Represent and implement linked data structures.                                       (SO – j)

6. Apply different operations, including search, insertion, and deletion, on linked lists.   (SO – a)

7. Apply recursion in solving simple problems.                                             (SO – a)

8. Implement stacks using arrays and linked lists.                                         (SO – j)

9. Implement queues using arrays and linked lists.                                        (SO – j)

10. Describe and represent different tree terminologies.                                (SO – a)

11. Apply different operations, including search, insertion, and deletion, on trees and binary search trees.   (SO – k)

12. Comprehend, compare, and apply sorting algorithms in problem solving.(SO – a)

13. Evaluate and Analyze the running time of small algorithms in terms of the number of operations performed.   (SO – b)

14. Experiment and practice recursive sorting algorithms in problem solving. (SO – b)

15. Describe, represent, and apply hash table terminologies and operations. (SO – j)

16. Describe, represent, and apply heap (priority queue) terminologies and operations.  (SO – b)

17. Develop small-scaled programming assignments in Java, taking space and time efficiency into account. (SO – b)

Other Important Course Policies

1. The lab instructor is your main point of contact regarding the programming assignments and projects. If you have any questions at all regarding the assignments, solving the program, how to code it, syntax errors, you name it, contact the lab instructor or TAs (if applicable). You can also email them with your questions, but understand that they may not respond immediately. If you want help via email, start your assignment early. Finally, the Lab Instructors will be grading the assignments. Therefore, any and all questions you have regarding your grade should be directed to them. If you feel your grade was unfair and you were not satisfied after contact the lab instructor, please come to my office hours to discuss.
2. Cheating will not be tolerated. If a student is caught cheating, then the grade on that assignment/exam for all students knowingly involved (the person providing answers as well as the one taking the answers) will be a 0%. Each program is worth 6%. So if a student is caught cheating, they get a zero on the program. Furthermore, based on the severity of the case and if this is the second instance of cheating, the student may be given an "F" in the course, dismissal from an academic unit, revocation of admission, suspension from the university, etc. Decision of the Lab Instructor about the cheating will be final.

   Since discussion of concepts with other students is often helpful, cheating must be more clearly defined. So to be very clear, the following items are cheating:

1. copying a segment of code of three lines or more from another student from a printout or by looking at their computer screen
2. taking a copy of another student's work and then editing that copy
3. sitting side by side while writing code for assignments and working together on segments of code
4. searching online for code/answers and then using that code

   In all of these situations, BOTH people responsible, the one from whom the three lines of code are taken as well as the person who takes those lines of code are engaging in academic misconduct. For example, if someone makes an electronic copy of their code accessible to ANYONE in the class (except for themselves) before 48 hours after an assignment is due, they are automatically culpable of academic misconduct. It does not matter if the recipient of the code doesn’t use it, uses it a little, or copies it directly.

   If you get stuck on an assignment, please ask the lab instructor for help instead of getting help from another student. Part of the learning process in programming involves debugging on your own. In our experience, when a student helps another student with an assignment, they rarely allow the student getting help to "figure out" problems on their own. Ultimately, this results in a lack of debugging experience for the student receiving help. The goal of the lab instructor is to provide the facilitation necessary for students to debug and fix their own programs rather than simply solving their problems. But, you are encouraged to work together on any non-graded programs to enhance and expedite the learning process.

   1. In order to take a make-up exam, you must request one from the instructor. The instructor will grant requests using his own judgment by applying the following general rule: "Make-up exams will only be given if the reason for missing the exam was out of the student's control." For example, being hospitalized unexpectedly is out of a student's control, but oversleeping or going to happy hour is not out of a student's control. If possible, it is recommended that the instructor be contacted before the exam.
   2. Blackboard will be a crucial element of the course. It is your responsibility to check Blackboard before every class meeting for any updates that may be posted. Additionally, some clarifications may only be given in class and won’t be posted online at all, so make sure you keep up with announcements in class.
   3. Class Attendance. Class attendance is mandatory and will be taken immediately at the beginning of each class. If you miss more than 25% of the lectures, you will receive a DN.
   4. Lab Attendance. Lab attendance is mandatory. If you miss more than 25% of the Labs, you will receive a DN for the lab and cannot take the Lab Final Exam.

Tentative Schedule for Lectures

Tentative Schedule for Labs