På Svenska

ID1300 Algorithms and Data Structures 7.5 credits

Algoritmer och datastrukturer

Please note

This course has been cancelled.

  • Educational level

    First cycle

  • Academic level (A-D)

    B

  • Subject area

    Information Technology
    Techonology

  • Grade scale

    A, B, C, D, E, FX, F

Last planned examination: Spring 12

At present this course is not scheduled to be offered.

Learning outcomes

Grade E:

The student should be able to use the data structures available in the class libraries in an objectoriented programming language and decide which is the approprirate datastructure in a given application.

The student should be able to implementa a simple algorithm in a programming language based on a detailed description or pseudo code.

The student should be able to describe following data structures considering the most important operations, when to use them and how they work.

Linked list, doublelinked list, hashtable, stack, queue, priority queue, heap, binary search tree.

The student should be able to implement any sorting algorithm for an array.

The student should have such a good understanding of complexity that she/he is able to discuss the complexity for a given algorithm.

The student should have a common knowledge about the data structures and algorithms mentioned during the course and be able to give a short explanation and know where to get more information if needed.

The student should be able to construct an own solution (algorithm) to a simple problem and write pseudo code for the solution.

Grades D-A:

The student should be able to analyze an algorithm and tell what complexity it has.

The student should be able to implement a non-trivial algorithm in any programming language.

The student should be able to solve a problem by figuring out an algorithm and implement it.

Course main content

Data structures for example stacks, queues, arrays, ordered arrays, trees, tries, red-black trees, binary searchtrees, hashtables, linked lists, priority queues, heaps.

Algorithms for example binary search, insert in datastructures (above), deletion in datastructures (above), selection sort, insertion sort, heapsort, bubblesort, quicksort, mergesort, radix sort, counting sort, depth-first-search, breadth-first-search, Warshalls algorithm, some AI algorithms.

Basic understanding for the complexity of an algorithm. Something about complexity classes.

Disposition

Lectures, laboratory work.

Eligibility

Programming skills from at least a basic and an intermediate course in objectoriented programming.

Prerequisites

Programming skills from at least one basic and one  intermediate course in objectoriented programming.

Literature

To be decided.

Examination

  • LAB1 - Laboratory Work, 6.0 credits, grade scale: A, B, C, D, E, FX, F
  • TEN1 - Examination, 1.5 credits, grade scale: P, F

Requirements for final grade

Lab1 - 6hp (A-Fx)
The laboration is divided into 5 parts: Written task 1&2, laboration 1,2,3.
Each part gives a number of points depending on how many and how advanced tasks the students has completed and how much time he/she demanded to complete them.
Written task 1: maximum of 2 points
Written task 2, laboration 1,2,3: maximum of 12 points each
Totally 50 points. Grades:
E - 10 points
D - 20 points
C - 27 points
B - 37 points
A - 45 points
Ten1 - 1,5hp (G/U)
Written examination. Approved or not approved only.
The written examination is divided into 2 parts with a maximum of 20 points each.
Part 1: Theory. 10 points is demanded to be approved.
Part 2: Programming. 10 points is demanded to be approved.
It is not possible to be approved at only one part. Both parts of the examination has to be approved at the same examination opportunity.

Offered by

ICT/Software and Computer Systems

Contact

Fadil Galjic, fadil@kth.se, 08 -164942

Examiner

Fadil Galjic, fadil@kth.se, 08 -164942

Supplementary information

http://people.dsv.su.se/~fadil/ID1300/

Version

Course plan valid from: Spring 09.
Examination information valid from: Autumn 07.