CSC 211 Fundamental Data Structures 2017

First term First Semester 2017


.

Data Structures and Algorithms

CSC211 in the first term is a foundation for COS211, second term, and CSC212 third and fourth terms.

Themes

The two terms of CSC211 and the Complexity part of CSC212 should be seen as a unit in which similar themes are emphasized:
  1. understanding the simple mathematics that underlies the theory of complexity
  2. the time and space complexity of algorithms
  3. order notation
  4. the best, worst and average behaviour of algorithms
  5. derivation of the performance algorithms
  6. implementation of algorithms
  7. comparison of theoretical and actual run times
  8. correctness of programs

In almost every practical the student is expected to implement some algorithms and run timing experiments to gain an understanding of their performance as measured on the size of the input data.

CSC211

This course, CSC211, is a practical introduction to Data Structures and the implementation of Algorithms for the manipulation of Data Structures. The implementation language is Java and many examples in Java are developed and timed in the practicals. Objects are implemented and manipulated in Java.

The time and space complexity of the algorithms are emphasized so that the student attains a proper grasp of the efficiency of algorithms.

The student should on successful completion of the course

  1. calculate the asymptotic bounds for algorithms;
  2. implement algorithms for manipulating data structures to
  3. execute efficiently on computing machinery;
  4. run timing experiments
  5. to compare the performance of algorithms in practice with their theoretical complexity and
  6. reproduce algorithms and answer theoretical questions about them 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 can derive and explain the time and space complexity of algorithms.

  • The student has been enabled to tackle software problems from a procedural, object-oriented approach.

  • The student has cultivated a positive outlook and will develop the attitude that it is a simple matter to deliver working products from tools the he has produced ab initio.

    Framework of the course:

    Some of the following topics are covered in this part of the Second Year Course CSC211, other topics from the same list are treated in the follow-up Second Year Course CSC212 and even repeated in more depth there during the second semester.
  • 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 at request for a modest fee. 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 and PDF you might want to adapt your net reader for reading PostScript, or PDF otherwise you can download the notes and then read the PostScript with gv(GhostView) or KGostview, or read the PDF files with Acroread.

    If you are inside the SunLab then the most up to date version of the notes is always available on zaber and boulder at /home/export/notes/ds/ds-slides.ps or /home/export/notes/ds/ds-slides.pdf. Since your home directory is at /home/export/ these files can be reached from your home directory as ../../ds-slides.ps or ../../ds-slides.pdf.

    Prescribed book in 2017

  • Algorithms FOURTH EDITION
    Robert Sedgewick and Kevin Wayne
    (2011) Addison-Wesley

    An excellent book. Since this book is newly prescribed in 2017 second-hand copies are unlikely to be available.

    Recommended book in 2017

  • Data Structures and Algorithms in Java
    4th Edition
    Michael T. Goodrich
    (2004) John Wiley and Sons. Inc.

    A very good book. Since this book was prescribed in 2003, 2004, 2005, 2006, 2008 there should be second-hand copies available.

    Recommended reading in 2008

  • 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 (4rd Ed.)

  • Manual for make make.ps

    PostScript overheads for lectures

    If you are inside the SunLab then use the notes at zaber, boulder or breakpoint
    at /home/export/notes/ds/ds-slides.ps or at /home/export/notes/ds/4up-ds-slides.ps or

    ds-slides.ps (A4 format) and
    4up-ds-slides.ps (4 per page)

    PDF overheads for lectures

    If you are inside the SunLab then use the notes at zaber, boulder or breakpoint
    at /home/export/notes/ds/ds-slides.pdf. or at /home/export/notes/ds/4up-ds-slides.pdf.

    ds-slides.pdf (A4 format) and
    4up-ds-slides.pdf (4 per page)



  • PostScript and PDF for practicals

    Practical 1 Term 1

    Practical 1 Term 1—5 February 2008 (A4 format PostScript) and
    Practical 1 Term 1—5 February 2008 (A4 format PDF).

    Practical 2 Term 1

    Practical 2 Term 1—12 February 2008 (A4 format PostScript) and
    Practical 2 Term 1—12 February 2008 (A4 format PDF).

    The latest version of all the material here is always available on zaber in ~/../../notes/toc/.



    .


    E-mail me at:

    4 May 2017