General Information

Professor: Panagiota Fatourou
Office: 215 (White Building 1st floor)
Office hours: Thursday, 16:00-17:00
Email address:
Telephone number: +30 2810 393549
TAs: Kazepis Nikolas, Birliraki Chryssa, Paliouras Kwnstantinos, Tzompanaki Katerina, Katopodis Alexandros, Papadakis Manos, Fragkiadaki Gewrgia
TAs' office: Graduates' lab, White building sub level
TAs' office hours: Monday, 12:00
Course email address:

Class Information

Tuesday, 11:00-13:00, classroom L202. Thursday, 11:00-13:00, classroom L202.

Assisting Class Information

Friday, 11:00-13:00, classroom L202.

Course Summary

The course focuses on the study of basic data structures, i.e. arrays, stacks, queues, lists, trees, etc., as well as on more complex data structures such as balanced trees, graphs and others. In addition, the technique of hashing will be taught, as well as data structures for the implementation of dynamic dictionaries, simple sets and sets with special operations. Selected topics on sorting and basic techniques of algorithm design will be also taught.

Learning Outcomes

Course Contents

 
Introduction
Basic concepts on algorithms and data structures, Proof techniques (proof by example or counterexample, proof by contradiction, mathematical induction), RAM model, Analysis of algorithms, Time complexity , Asymptotic analysis (in terms of Ο, Ω, Θ), Standard complexity classes, Mathematical background , Recursive algorithms and their analysis, Recursive relations, Experimental analysis. Arrays
Operations on Arrays, Multi-dimensional Arrays, Symmetric and Triangular Arrays, Sparse Arrays
Basic data structures
Stacks (abstract data type, static and dynamic implementations, static implementation of multiple stacks, applications, complexity), stacks that support the multipop() operation, Amortized analysis.
Queues (abstract data type, static and dynamic implementation, complezity, applications).
Lists (unsorted and sorted lists, guard node, list traversals, zig-zag traversals, doubly linked lists, complexity, applications).
Trees
Definition, types of trees and their properties, implementation, tree traversals, ordered trees
Sets & Dictionaries
Abstract data type, Implementation using linked lists, Move-to-front and Transpose heuristic, Binary search, Expected analysis, Binary Search Trees
Balanced Trees
AVL Trees, (2,3)-trees, Red-Black trees
Hashing
Chain hashing (separate and coalesced chaining), Open addressing strategies (linear probing, double hashing), Analysis of different strategies, Ordered hashing, Extendible hashing, Hash Functions, Universal Hashing
Priority queues
Abstract data type, Implementation using balanced binary search trees, Partially ordered trees, Implementation using Heaps.
Sets with special operations
Disjoint sets that support Union-find, Up-Trees
Sorting
InsertionSort, SelectionSort, MergeSort, HeapSort
Graphs
Representation, implementation, traversal, applications

Program

Week Subject
1st Introduction - Basic concepts of algorithms and data structures
2nd Time complexity - Amortized cost, recursive algorithms and recursive relations - Arrays
3rd Basic data structures: Lists, stacks, queues
4th Lists
5th Trees
6th Trees
7th Balanced Trees: Implementation of dynamic dictionaries
8th Hashing
9th Hashing - Sets with special operations
10th Priority queues - Graphs
11th Graphs
12th Sorting
13th Techniques of algorithm design

Assignments and Marking

Throughout the semester, four sets of theoretical assignments and a project will be handed out. Every assignment must be turned in before the given deadline. Late turn-ins will be accepted only up to three days after the deadline with a penalty of 1 point (out of 10) per day. Solutions to the assignments will be given in class by the TAs after the deadline. Exceptionally good assignments can be marked with grades greater than 10.

The project is divided in two parts, each of which has a different deadline. Every part must be submitted before the given deadline. The same algorithm as for the theoretical assignments will be used for late submissions. All parts of the project will be orally examined (see the calendar for details). Students can select either C or JAVA for their programming tasks. Despite the fact that different parts of the project have a different deadline and will be marked seperately, the final grade of the project will be determined after the final submission. Students will be given the chance to improve the first two parts of their project based on feedback provided by the TAs during the oral exams. The final grade of the first two parts of the project will be determined as follows:.

0,2*B1 + 0,8*B2, where B1 is the original mark of each part and B2 is its mark after the final submission where all improvements have been taken into consideration.

Attention: The possibility of improving the last part will not be given.

It is important that every student understands the given problem and outlines a possible solution by him/herself (although s/he can ask the course assistants for any questions or problems he or she has concerning the project (e.g., code compilation or running problems). The code should be carefully written to simplify the task of correcting it. The marks given to each part of the project will reflect the completeness and correctness of the provided solution as well as the provision of explanatory comments on the submitted source code. Any non-academic behaviour (close colaboration or cheating) will be punished with grade deduction or nullification. It is best for a student to submit an incomplete project than an altered copy of another student's work. Students can contact the course TAs or the instructor for questions during the course office hours.

Although students can create their programs on any type of computer or operating system, the examination of the project will be performed on the Department's UNIX machines. So stundents must ensure that their submitted code can be compiled and run on these machines.

Students are responsible for the misuse of their electronic account. They must ensure that their password remains secret and nobody has access to their account. Moreover, the folders under which they keep their assignments/project should not have read (or even worse write) permision by others (you may find command "chmod" useful for this purpose).

During the final exam students can use their book or the lecture slides. Other notes are forbidden. The use of mobile phones is forbidden during the final exam and students should have some kind of document that verifies their identity (like paso, identification card, driving license, passport, etc.) with them.

The final grade will be derived according to the weights described below:


Theoretical assignments: 20%
Project: 20%
Final Exam: 60%

Students with score lower than four (out of ten) on the final exam will fail.

submit program

Project will be submitted only electronically. Theoretical exercises can be submitted either electronically using the program submitor in hardcopy to the professor or to the teaching assistants on the designated office hours on the deadline sumission day.

In order to use the program submit for handing in any of the four sets of theoretical exercises, the following commands must be used respectively:

 

For the programming assignment (your project) the respective commands are:


where <dir> is the directory where the student stores the files to be submitted. The submit program does not accept compressed files, so care must be taken not to submit files that are binary/compressed/gzipped.

For more information refer to "Use of the submit program".


Course Emailing-list & Electronic Account

The course uses an emailing list for the efficient communication of the instructor and the TAs with the students. Subscription to the emailing list is performed by sending an email to the following address:

with empty subject and the following line as the email body:

Students are obliged to subscribe to the emailing list by February 25, 2011. The address of the emailing list is:

All emails sent to this address will be forwarded to all members (students, instructor, TAs) of the list. It is a strong recommendation to the students to read email regularly (e.g., once a day).

The address of the electronic account of the course is the following:

Students may send any questions concerning the course to this address.

Attendance

Attendance is strongly recommended. Students are expected to know the material presented in class. Part of the material that will be taught is not covered by Greek books or it is presented in a different order.

Prerequisities

CS100 (Introduction in Computer Science) and CS150 (Programming) are prerequisite courses for this course. Successful completion of CS118 (Discreet Mathematics) will be also helpful. Students that have not succeeded on the courses mentioned above, do not have the required background to attend the course.

Books

The course uses more than one books (and mainly the english-written books mentioned below). Any of the above books covers most of the material that will be taught. Additionally, students should study carefully the course slides as well as any other material handed out throughout the semester.

Related Bibliography

Webpages of past semesters