. |

## Data Structures and Algorithms

This course is a practical introduction to Data Structures and the implementation of Algorithms for their manipulation. The implementation language is Java and many examples in Java are developed in the practicals. The time and space complexity of the algorithms are studied and the student should have a good grasp of the efficiency of algorithms. The student should: (1) be able to justify the correctness of algorithms by induction proofs; (2) understand loop invariants; (3) calculate the asymptotic bounds for algorithms; (4) implement algorithms for manipulating data structures to execute efficiently on computing machinery; and (5) reproduce algorithms under examination conditions.### Outcomes

- At the successful completion of this course the student has implemented many algorithms that run correctly on computing machinery.
- The student will understand the connection between justifying an algorithm using induction and loop invariants and the synthesis of programs from these proofs.
- Students will be enabled to tackle software problems from a procedural, object oriented approach. The student will cultivate a positive outlook and will develop the attitude that it is a simple matter to deliver working products
*ab initio*.## Framework of the course.

- Java programming
- Object-oriented Design
- Analysis and justification of algorithms
### Specific data structures

- Stacks and the implementation of recursion
- Queues, Vectors, Lists, and Sequences
- Trees and Heaps
- Hash tables, Dictionaries and Skip lists
- Searching and Sorting
- Pattern matching in text
- Graph and tree traversal
### Practicals and projects

- Practical implementation of course work will be handed in weekly.
### Class material

- All the transparencies for the course are available below in A4- or four-per-A4-format. The 4-per-A4 slide copies will be issued in class. Please don't print them yourself. The Latex for my own notes is available. You may download the complete manual for
*make*which will be useful if you are not programming in Java. Since all the documentation is available in PostScript you might want to adapt your net reader for reading PostScript, otherwise you can download it and then read it with*gv*(GhostView). The documentation is also available in PDF and this can be read using*acroread*.### Prescribed Book in 2008

- Data Structures and Algorithms in Java

4th Edition

Michael T. Goodrich

(2004) John Wiley and Sons. Inc.#### Recommended reading

- Data Structures and Algorithms in Java

Second Edition

Adam Drozdek

(2005) Thomson Learning#### Java and C++ Books

- Java First Contact (2nd Edition)

Roger Garside and John Marian

(2003) Thomson Brooks/Cole.- C++ for Programmers (3rd Edition)

Leen Ammeraal

(2000) Wiley.#### Other course material

- Link to Goodrich and Tamassia: Data Structures and Algorithms in Java (3rd Ed.)

- Manual for
*make*make.psMost of what follows below is still fictional.

- PostScript for tutorial and solutions

tut1solution.ps (A4 format PostScript) and

4up-tut1solution.ps (4 per page PostScript) and

cos2-slides.ps (A4 format) and

4up-cos2-slides.ps (4 per page)

. |