Course Info.

Princess Sumaya University for Technology - Fall 2015
11212 - Data Structures and Introduction to Algorithms

Instructors Information

Dr. Ibrahim Albluwi

Email: i.albluwi@psut.edu.jo

Office: IT-309

Extension: 243
Office Hours: 
Sundays and Thursdays: 9:00 - 10:00
Tuesdays: 9:00-10:00 and 11:00-12:00
Mondays and Wednesdays: 14:00 - 15:30

Dr. Sufyan Almajali

Email: s.albmajali@psut.edu.jo

Office: IT-218

Extension: 248
Office Hours:

Sun, Tue, Thu: 10:00 - 11:00 
Mon, Wed: 12:00 - 1:00

Class Meetings

Section 1: Sun, Tue, Thu:  9:00 -10:00  @ IT-205 (Dr. Sufyan)

Section 2: Sun, Tue, Thu:  14:00 - 15:00 @ IT-204 (Dr. Ibrahim)

Section 3: Mon, Wed: 9:30 - 11:00 @ IT-201 (Dr. Syfyan)

Course Description

Prerequisites: Object Oriented Programming in C++ (11206) and Discrete Math (20134).

The purpose of this course is to introduce the students to the complexity analysis of algorithms, the fundamental methods for representing data in memory and the algorithms which access data, using the C++ language. Data structures include: lists, stacks, queues, trees, heaps, priority queues, hashing and graphs. Algorithms include searching and sorting. Programming topics include: pointers, dynamic memory allocation, templates and the C++ Standard Template Library (STL). At the end of the course, students will be equipped with the tools that will enable them to write clear and efficient programs.

After completing this course, students will be able to:

• Perform worst and best case analysis of algorithms. 
• Implement and use simple searching and sorting algorithms and compare between them. 
• Implement and use several data structures and compare between them. 
• Choose the right combination of data structures and algorithms for solving a problem based on complexity analysis. 

Course Schedule

Week(s)	Topic(s)	Chapter(s) in Text
1	Introduction to Data Structures and Algorithms.
1, 2	Complexity Analysis of Algorithms: Running time calculations, Asymptotic Notation (Big-O) for representing the complexity of an algorithm, Growth Rates of Functions.	Chapter 2
3	Searching: Linear search, binary search and their complexity analysis.	Chapter 2
3	Sorting : Selection Sort, Insertion Sort, Bubble Sort.	Chapter 9
4, 5, 6	Lists : Array and linked implementations, advantages and disadvantages of each implementation, list operations (search, insertion, deletion), ordered vs un-ordered lists, merging two lists, lists in the C++ standard template library (STL), applications.	Chapter 3
7, 8	Stacks and Queues: Array and linked implementations, stacks and queues in the STL, applications.	Chapters 4
8	Recursion: Recursive functions (review), stack frames, activation records.	Chapter 5
9, 10, 11	Trees: Basic concepts, binary search tree (BST), operations (search insertion, deletion), tree traversals, applications.	Chapter 6
12	Priority Queues: ordered array, unordered array and heap implementations of a priority queue, priority queues in the STL, applications.	Chapters 4 and 6
12, 13	Hashing : Hash functions, collision resolution, load factor, hash tables in the STL (non-standard), applications.	Chapter 10
13, 14	Graphs: Basic concepts, graph representations, graph traversals, applications.	Chapter 8

Textbook

All material covered in class and posted on this blog is required. Topics covered are mostly based on the following textbook:

Data Structures and Algorithms in C++,
Adam Drozdek,
Cengage Learning; 4th edition.

Other useful books include:

• Data Structures and Algorithm Analysis in C++, Mark A Weiss; Addison Wesley. 
• Data Structures Using C++, D.S. Malik; Thomson Course Technology. 
• Data Structures and Algorithms in C++, Michael T. Goodrich, et al; Wiley.
• Introduction to Algorithms, Cormen et al; MIT Press.

Grades Distribution

• Assignments (15%) 
• There will be around 5 assignments worth 3 marks each. 
• Late submissions are accepted after deducting 25% for each late day. 
• Details of each assignment will be provided in the assignments tab. Make sure to read carefully the collaboration policy below.                                                                               .
• Participation (3% Bonus)
• Positive participation in the class and the Facebook group and a clean attendance record can account to up to 3 bonus marks at the end of the semester.                              .

• Midterms (45%): 
• There will be two exams worth 22.5% each. 
• As a help, the exam with the higher grade will be considered out of 25 and the lower out of 20.  .                                                                               .

• Final Exam (40%)

Note: In order to pass this course, you need to get a passing grade in the exams. In other words, the sum of your grades in exam1, exam2 and the final should be more than 42.5/85. Getting less than this grade, means that the assignment marks are not credible, and therefore, they will not be considered.

Collaboration Policy

Collaboration is great! We all learn by discussing with others. However, collaboration can be harmful if we abuse it.

You are encouraged to discuss with your colleagues in the course and out side the course, provided that you respect the following rules:

• Never show your code to any student in the course.
• Never look at the code of any student in the course.
• Never write any piece of code to anyone in the course. This includes writing pieces of code on paper and on electronic devices.
• Never ask (or allow) anyone taking this course or not taking it to write any piece of code for you.
• Never copy and paste pieces of code from the internet or any other resource.

Not respecting these rules may lead to any (or all) of the following consequences (depending on the case):

• A grade of zero in the assignment (or in all of the previous assignments).
• A report written and sent to the dean of the college of IT and the deanship of student affairs.
• A failing grade in the course.

We do not guarantee that everyone who does not respect these rules will be caught. However, we guarantee that everyone that is caught will be strictly penalized.

Remember that assignments are a great opportunity for you to learn, so make sure to invest them well.

Attendance Policy

Attending lectures is very important for understanding the material. Please make sure to always come on time and to avoid any unnecessary absence.

According to the university laws, a student should not be allowed to enter the final exam in any of the following two situations:

• Missing 15% of the lectures without a valid excuse (8 lectures or more).
• Missing 20% of the lectures even if there is a valid excuse. If there is a valid excuse, the student is allowed to drop the course without receiving a failing grade.

Valid excuses include the following:

• Medical Excuses attested by the university doctor.
• Excuses issued by the deanship of student affairs or the university administration.

Official letters or documents that explain the reason behind the absence may and may not be accepted depending on the case and the body issuing the letter/document.

Every lecture, I typically spend around 5 minutes reviewing what has been covered in the previous lecture and introducing what we will cover next. I then take the attendance and start the lecture.

Any student that arrives after taking the attendance is considered late. Two late arrivals are considered as one absence. The reason for this policy is that arriving late disrupts the lecture since the door is just beside the white-board.

Students who have a clean (or almost clean) record will be awarded with up to 3 marks towards the end of the semester depending on their positive participation in the classroom.