Updated Code

If you have downloaded the code of the tree before Exam2 then please re-download it again now. The code that was uploaded before contains an implementation of the deleteNode function that is different from the one we have discussed in class.

To make sure that you have the right file, check if the file name is BST_NewDelete.cpp, if the file name is BST.cpp/h then please re-download the code again.

Previous Exams

Here is a link for the solution of the exam we have solved in class (Thanks to Safaa Horize).

Here is also an alternative link for the previous exams.

Assignment 3 and an Alternative Link For the Code

Assignment 3 is ready! Check it out in the assignments tab.

Here is also an alternative link for the code since the university's E-Learning system is down.

HW2 Solution and Some Tree Operations

Here is the solution for HW2.

Here is also the code we have written in today's session:

- GetMax (3 ways).
- IsComplete (3 ways).
- IsBalanced.

Meeting On Saturday

There will be two sessions this Saturday 20/12/2014 inshaAllah.
The first session will start at 10:00 AM and the second at 12:00 PM.

I haven't had the chance to reserve a room. We will meet where we usually take our lecture and then move to any empty room.

Iterative InOrder and PostOrder

We have seen in class the iterative version of the pre-order traversal. The following two links that discuss how post-order and in-order traversals can be implemented iteratively:

http://leetcode.com/2010/04/binary-search-tree-in-order-traversal.html

http://leetcode.com/2010/10/binary-tree-post-order-traversal.html

Exam Review Session

There will be a review session with the TA on Sunday 14/12/2014 at 3:00 PM in IT 201.

In this session, the TA will answer any questions you have regarding Stacks, Queues and ArrayLists.

Session on Recursion

There will be another session on recursion inshaAllah today (Thursday 11/12/2014) with our teaching assistant, Ms. Safaa Horize,  from 3:00 to 5:00 PM at IT 201.

Overloading the "<<" Operator

If you are facing problems implementing the operator overloading of the stream extraction operator "<<", then note the following:

• The function should be a non-member function. Overloading it as a member function should cause compilation errors when you implement the main function.
• The function should be inlined (i.e. implemented inside the class).
• To be able to access the private members of class DLList, the operator overloading function should be a friend of DLList.

To summarize, if you add the following inside the DLList class, your program should compile correctly:

friend ostream & operator<<(ostream & out, DLList<T> & list) {
    // code that prints the list should go here.}


On the other hand, overloading the assignment operator "=" can be done as usual, as a member or a non-member function and inlined or not inlined. In all cases it should work fine.

Here are two links if you wish to read more:
http://www.parashift.com/c++-faq-lite/template-friends.html
http://stackoverflow.com/questions/9814345/cant-overload-operator-as-member-function

On Stacks and Queues

The following is a link for a visualization of the queue as an array:
http://www.cosc.canterbury.ac.nz/mukundan/dsal/CQueueAppl.html

Here is also the code we have written in class for printing and reversing queues:
StacksAndQueues.cpp

Some students have also requested that I post the code for checking expressions for bracket consistency. I have drafted a quick solution today that can be found here. Such problems are excellent exercises. It is a pity though that we rarely ask questions on stacks and queues with this level in the exam.

Wall of Fame!

Are you following the updates at the Wall of Fame?
Check them out and please be jealous!!

Recursion Review Sessions

By the end of this week, we will have started discussing "trees" in all of the sections, which is the second major topic in this course after linked lists.

When dealing with trees, we will often write recursive code. Therefore, it is very important that you review your information about recursion.

Our TA is willing thankfully to give two review sessions on recursion: Wednesday from 10:00 - 11:00 and Thursday from 12:00 -1:00 (at lab 103).

Make sure to attend, especially if you are not fluent in recursion or if you need a refresher!

Assignment 2 Deadline

The deadline for assignment 2 has been postponed until 7/12/2014 11:55 PM.

Bittawfeeq!

Queue As An Array

For section (SuTuTh):

As we wrote in class the code of the Enqueue method for the queue as an array, we forgot to handle an important case, which is when the queue is empty.

It is not enough in this case to increment last; we have to increment also first, since both first and last are -1 when the queue is empty.

The code should look as follows:

template <class T>

void QueueArray<T>::Enqueue(T& el)

{

    if(IsFull()){

        printf("\n Can't enqueue into a full queue!");

        return;

    }

    if(IsEmpty())

        first = last = 0;

    else if(last == capacity-1)

        last = 0; 

    else

        last++;

    

    data[last] = el;

    size++;

}

Assignment 2

It is ready. Check it out, start early and have fun!

I am curious to see innovative solutions for the bonus question!

Announcements

1) 
As I will be traveling to Egypt tomorrow inshaAllah to attend the annual ACM Arab Collegiate Programming contest, I will not attend the lectures on Sunday and Tuesday.

On Sunday, at 9:00 AM in room 203, Dr. Ghassan will solve the exam. Please attend his lecture as a substitute for our lecture on Sunday. For Tuesday, you are free to attend with Dr. Ghassan or not, as he will start a new subject: Array Lists.

2)
Sister Safaa Horaiz, our teaching assistant, is thankfully willing to help in the course. Her office is at the meeting room under Dr. Arafat's office. You can see her to ask about anything related to the course. Her office hours are:

Sundays: 2:00 - 4:00 PM
Mondays and Wednesdays: 8:00 AM - 1:00 PM.
Tuesdays: 12:00 - 2:00 PM.

I wish you all the best of luck in your exams.

Exam1 - Spring 2014

Here is a link to the first exam of Spring 2014.
Here is also a link to the solutions for the coding questions.

Linked Lists in Arabic

This is a good video series about data structures in Arabic (... or in Egyptian maybe!):

http://www.youtube.com/watch?v=epfRLOWfzWI

HW1 Deadline Extension

Due to the overwhelming demand for a deadline extension, and because the e-learning site was down during the weekend, the deadline for assignment 1 is now Sunday 9/11/2014.

Bittawfeeq!

Assignment 1

Assignment 1 is ready ... checkout the "Assignments" tab.

Start early and do not hesitate to ask if you face any problems.

Enjoy!

Update: It seems that the E-Learning website at PSUT is down. I have added an alternative link just in case you are facing problems in downloading this assignment

Searching and Sorting

I have just uploaded a new version of the file "Searching and Sorting" in the "Course Material" tab. If you have already downloaded the file, then please delete the old version and re-download the new one again.

Visualizations of Sorting Algorithms

The following links contain interactive visualizations for sorting algorithms.

http://math.hws.edu/TMCM/java/xSortLab/

http://visualgo.net/sorting.html

Visualgo.net contains many excellent visualizations for many data structures and algorithms that we cover in the course. It is worth going back to this website every time we cover a new data structure or algorithm.

Have fun playing :)

Asymptotic Analysis Slides

I have just uploaded the Big-O slides. You can find them in the "Course Material" tab.

Asymptotic Analysis of Algorithms

Here is a good-short-informal summary of the asymptotic analysis of algorithms.

At the end of the video Big-Theta and Big-Omega are mentioned, which we do not cover in this course. More about them in the "Design and Analysis of Algorithms" course inshaAllah.

What is an Algorithm?

A short video that explains informally what an algorithm is and how to compare between algorithms.

As we have said in class, we should ask ourselves three questions whenever we design any algorithm:

• How quick is the algorithm?
• How much space does it require?
• Is it correct?

Our concentration in this course is on the basics of answering the first question ... just to the level that allows us to understand which operations are faster on which data structures!

Welcome!

Assalamu Alaikum everyone!

Welcome to this adventure in the world of data structures.

This blog will be our out-off-class interaction space. I will regularly post here announcements, supporting material and supplementary exercises. You are also welcome to comment and discuss here about any of the posts.

To stay posted about what goes on in this blog, make sure to subscribe by email using the widget right above my profile pic.

 See you in class!