| TDDD86 |
Data Structures, Algorithms and Programming Paradigms, 11 ECTS credits.
/Datastrukturer, algoritmer och programmeringsparadigm/
For:
D
U
|
| |
Prel. scheduled
hours: 90
Rec. self-study hours: 203
|
| |
Area of Education: Technology
Main field of studies: Computer Science, Computer Engineering
|
| |
Advancement level
(G1, G2, A): G1
|
|
Aim:
The purpose of the course is to give the student tools to be able to independently construct computer programs that use time and memory efficiently. Furthermore, the course gives deeper knowledge about programming, specifically procedural and object-oriented programming in the programming language C++, as well as an introduction to programming paradigms as a broader perspective on programming. The course also provides an introduction to how effective computer programs can help us understand and manage issues related to sustainable development.
Upon completion of this course the student should be able to:
- Demonstrate the ability to analyze time and space complexity of iterative and simple recursive algorithms.
- Explain and use the most common abstract data types and sorting algorithms.
- Implement the most common abstract data types and sorting algorithms with different data structures and algorithms.
- Describe established methods for design (and analysis) of algorithms in general.
- Implement procedural and object-oriented programs in the programming language C++.
- Solve non-trivial computational tasks by using different components of the C++ standard library in combination.
- Describe and compare the most common programming paradigms and their underlying principles.
- be able to apply effective algorithms to better understand social problems linked to sustainable development.
|
|
Prerequisites: (valid for students admitted to programmes within which the course is offered)
Discrete mathematics, and basic knowledge of functional, imperative, and object-oriented programming.
Note: Admission requirements for non-programme students usually also include admission requirements for the programme and threshhold requirements for progression within the programme, or corresponding.
|
|
Supplementary courses:
Design and Anlysis of Algorithms, Complexity Theory, Logic Programming, Programming Theory, Concurrent Programming and Operating Systems, Compiler Construction, Advanced Programming in C++.
|
|
Organisation:
Lectures are used to present theory that is then tested and implemented in laboratory exercises. The lectures on data structures and algorithms introduce new concepts at a summary level, where after students are expected to obtain detailed knowledge through reading and practicing using a course specific version of the open, interactive, teaching aid OpenDSA.
The course runs over the entire autumn semester.
|
|
Course contents:
- Basic notions
- Mathematical foundations for analysis of algorithms
- Fundamental abstract data types and data structures, such as lists, stacks, queues, search trees, heaps, hash tables, and graphs
- Efficiency analysis of algorithms
- Sorting and searching
- String algorithms
- Graph algorithms
- Algorithmic paradigms (dynamic programming, greedy algorithms, divide and conquer, brute force search)
- Procedural programming in C++ (variables, constants, declarations, expressions, statements, functions, fundamental data types and fundamental data structures)
- Pointers and dynamic memory management
- Object-oriented programming and classes in C++ (class declaration, data members, member functions, access specification for class members, constructors, destructor, inheritance, polymorphism, friends)
- Usage of the C++ standard library (input and output, character and string handling, containers, iterators, algorithms, user defined function objects and lambda expressions)
- Type parameterized functions and classes (templates) in C++
- Introduction to programming paradigms
- Introduction to efficient algorithms importance for society's goals of sustainable development
|
|
Course literature:
Lippman, Lajoie, Moo, �?�C++ Primer�?�, fifth edition, Addison Wesley, 2012.
Course specific version of OpenDSA.
Lab compendium, C++ style guides, and other material available through the course web pages.
|
|
Examination: |
|
Computer examination
Programming assignments
Computer based exercises
Written assignment
|
3 ECTS
5 ECTS
2 ECTS
1 ECTS
|
| |
|
The computer based exercises are performed in a course specific version of the open, interactive, teaching aid OpenDSA.
The computer exam tries the students knowledge about data structures and algorithms. The first part of the examination comprises assignments similar to the computer based exercises, giving a passing grade. For higher grades solving tasks from the second part of the examination is required.
The programming assignments train and test the student�?Ts skills and knowledge in programming in C++ and data structures and algorithms. By completing tasks besides those that are mandatory a higher than passing grade can be assigned.
The written assignment trains and tests the student�?Ts skills and knowledge in programming paradigms.
The final grade assigned is the weighted average grade of the computer examination and the programming assignments. |
Course language is Swedish.
Department offering the course: IDA.
Director of Studies: Ahmed Rezine
Examiner: Cyrille Berger
Link to the course homepage at the department
Course Syllabus in Swedish
|
|