COS 254 Data Structures and Algorithms 2008

Second Term, First Semester 2008


.

  • 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.ps

    Most 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
  • PostScript overheads for classes
    cos2-slides.ps (A4 format) and
    4up-cos2-slides.ps (4 per page)



    .


    E-mail me at:
    20 December 2007