Course syllabus

Jump to today

Welcome to the course homepage of DIT961 V19 Data Structures. The course is given by the Department of Computer Science and Engineering at Campus Johanneberg during Study Period 4, 2019. You find information about the course below and via the following pointers:

Teachers

  • Lecturer: Alex Gerdes
    Phone: +46 31 772 6154
    Email: alex.gerdes "at" cse.gu.se
    Office: Room 6479 in the EDIT building
  • Course assistants:
    • Oskar Lyrstrand, guslyros "at" student.gu.se
    • Marco Vassena, vassena "at" chalmers.se

Student representatives

  • Emanual Olaison, gusolaiem "at" student.gu.se
  • Sophia Thanh Pham, gusphaso "at" student.gu.se
  • Bashar Oumari, gusoumba "at" student.gu.se

Course evaluation results
Course evaluation protocol

 

Course plan

The course will cover the following subjects:

  • Basic data structures and algorithms such as binary search, self-resizing arrays and linked lists
  • Big-Oh complexity and how to reason about it, in iterative and recursive programs
  • Sorting algorithms: insertion sort, selection sort, bubblesort, quicksort, mergesort, heapsort, counting sort
  • Data structure invariants; abstract data types
  • Hash tables
  • Binary heaps; heapsort
  • Binary search trees, balanced binary search trees (AVL trees, red-black trees), 2-3 trees
  • Graphs; Dijkstra’s algorithm; Prim’s algorithm

You can find the official syllabus here.

Course organisation

The course is organised as follows:

  • 9 weeks in total
  • Two lectures per week, which cover the theoretical part
  • One exercise session per week, where you can get personal help to understand the material; these sessions are not obligatory, but recommended
  • 2 to 3 lab sessions per week, where you can get help from the course assistants
  • 4 lab assignments and one hand-in, which all need to be completed in order to complete the course; these are done in groups of two
  • One written exam at the end of the course; this is obligatory and done individually
  • Your final grade will be determined by your grade on the written exam only

Study period 4 is loaded with Holidays, so the schedule is quite irregular and the amount of teaching per week will vary.

Literature list

We don’t have an official course book, since the lectures are fairly self-contained and you can find so much online. If you feel like buying a book anyway, we can recommend Algorithms, by Robert Sedgewick and Kevin Wayne. This is an excellent book that covers much of the stuff in the course in a very clear way.

If you have Sedgewick’s book, then the course covers most of chapters 1-3 (Fundamentals, Sorting, Searching) and some of chapter 4 (Graphs). The main differences are:

  • We also cover AVL trees, skew heaps, skip lists, and queues implemented as a pair of lists (see e.g. the Chalmers FP course).
  • Sedgewick treats AA trees slightly differently and calls them “red-black BSTs”. If you prefer to use this variant then that’s fine.
  • We don’t cover: union-find, selection sort, shellsort, bottom-up mergesort, heapsort, and several of the graph algorithms. In particular, the graph algorithms we cover are breadth-first search, depth-first search, topological sorting, strongly-connected components, Dijkstra’s algorithm and Prim’s algorithm.

Note that this is not meant to be an exhaustive list; you should look at the lectures to see everything in the course.

Links

Course summary:

Date Details Due