Data Structures, Algorithms and Programming Paradigms, 11 credits
Datastrukturer, algoritmer och programmeringsparadigm, 11 hp
TDDD86
Main field of study
Computer Science and Engineering Computer ScienceCourse level
First cycleCourse type
Programme courseExaminer
Ahmed RezineDirector of studies or equivalent
Ahmed RezineEducation components
Preliminary scheduled hours: 90 hRecommended self-study hours: 203 h
Course offered for | Semester | Period | Timetable module | Language | Campus | ECV | |
---|---|---|---|---|---|---|---|
6CDDD | Computer Science and Engineering, M Sc in Engineering | 3 (Autumn 2017) | 1, 2 | 2, 3 | Swedish | Linköping, Valla | C |
6CMJU | Computer Science and Software Engineering, M Sc in Engineering | 3 (Autumn 2017) | 1, 2 | 2, 3 | Swedish | Linköping, Valla | C |
Main field of study
Computer Science and Engineering, Computer ScienceCourse level
First cycleAdvancement level
G1XCourse offered for
- Computer Science and Software Engineering, M Sc in Engineering
- Computer Science and Engineering, M Sc in Engineering
Entry requirements
Note: Admission requirements for non-programme students usually also include admission requirements for the programme and threshold requirements for progression within the programme, or corresponding.
Prerequisites
Discrete mathematics, and basic knowledge of functional, imperative, and object-oriented programming.Intended learning outcomes
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.
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.
Course content
- 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
Teaching and working methods
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.
Examination
UPG2 | Written assignment | 1 credits | U, G |
UPG1 | Computer based exercises | 2 credits | U, G |
LAB1 | Programming assignments | 5 credits | U, 3, 4, 5 |
DAT1 | Computer examination | 3 credits | U, 3, 4, 5 |
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’s 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’s skills and knowledge in programming paradigms.
The final grade assigned is the weighted average grade of the computer examination and the programming assignments.
Grades
Four-grade scale, LiU, U, 3, 4, 5Department
Institutionen för datavetenskapDirector of Studies or equivalent
Ahmed RezineExaminer
Ahmed RezineCourse website and other links
http://www.ida.liu.se/~TDDD86/Education components
Preliminary scheduled hours: 90 hRecommended self-study hours: 203 h
Course literature
Additional literature
Books
- Lippman, Lajolie, Moo, (2012) "C++ Primer" fifth edition
Websites
Course specific version of OpenDSA.
Compendia
Lab compendium, C++ style guides, and other material available through the course web pages.
Code | Name | Scope | Grading scale |
---|---|---|---|
UPG2 | Written assignment | 1 credits | U, G |
UPG1 | Computer based exercises | 2 credits | U, G |
LAB1 | Programming assignments | 5 credits | U, 3, 4, 5 |
DAT1 | Computer examination | 3 credits | U, 3, 4, 5 |
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’s 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’s skills and knowledge in programming paradigms.
The final grade assigned is the weighted average grade of the computer examination and the programming assignments.
Regulations (apply to LiU in its entirety)
The university is a government agency whose operations are regulated by legislation and ordinances, which include the Higher Education Act and the Higher Education Ordinance. In addition to legislation and ordinances, operations are subject to several policy documents. The Linköping University rule book collects currently valid decisions of a regulatory nature taken by the university board, the vice-chancellor and faculty/department boards.
LiU’s rule book for education at first-cycle and second-cycle levels is available at http://styrdokument.liu.se/Regelsamling/Innehall/Utbildning_pa_grund-_och_avancerad_niva.
Additional literature
Books
Websites
Course specific version of OpenDSA.
Compendia
Lab compendium, C++ style guides, and other material available through the course web pages.
Note: The course matrix might contain more information in Swedish.
I | U | A | Modules | Comment | ||
---|---|---|---|---|---|---|
1. DISCIPLINARY KNOWLEDGE AND REASONING | ||||||
1.1 Knowledge of underlying mathematics and science (G1X level) |
|
X
|
X
|
DAT1
UPG1
|
||
1.2 Fundamental engineering knowledge (G1X level) |
X
|
X
|
X
|
DAT1
LAB1
UPG1
UPG2
|
||
1.3 Further knowledge, methods, and tools in one or several subjects in engineering or natural science (G2X level) |
|
|
|
|||
1.4 Advanced knowledge, methods, and tools in one or several subjects in engineering or natural sciences (A1X level) |
|
|
|
|||
1.5 Insight into current research and development work |
|
|
|
|||
2. PERSONAL AND PROFESSIONAL SKILLS AND ATTRIBUTES | ||||||
2.1 Analytical reasoning and problem solving |
|
|
|
|||
2.2 Experimentation, investigation, and knowledge discovery |
|
|
X
|
LAB1
|
||
2.3 System thinking |
|
|
|
|||
2.4 Attitudes, thought, and learning |
|
X
|
|
LAB1
|
||
2.5 Ethics, equity, and other responsibilities |
|
|
|
|||
3. INTERPERSONAL SKILLS: TEAMWORK AND COMMUNICATION | ||||||
3.1 Teamwork |
|
|
X
|
LAB1
|
||
3.2 Communications |
|
|
|
|||
3.3 Communication in foreign languages |
|
|
X
|
|||
4. CONCEIVING, DESIGNING, IMPLEMENTING AND OPERATING SYSTEMS IN THE ENTERPRISE, SOCIETAL AND ENVIRONMENTAL CONTEXT | ||||||
4.1 External, societal, and environmental context |
|
X
|
|
LAB1
UPG2
|
||
4.2 Enterprise and business context |
|
|
|
|||
4.3 Conceiving, system engineering and management |
|
|
|
|||
4.4 Designing |
|
|
|
|||
4.5 Implementing |
|
|
|
|||
4.6 Operating |
|
|
|
|||
5. PLANNING, EXECUTION AND PRESENTATION OF RESEARCH DEVELOPMENT PROJECTS WITH RESPECT TO SCIENTIFIC AND SOCIETAL NEEDS AND REQUIREMENTS | ||||||
5.1 Societal conditions, including economic, social, and ecological aspects of sustainable development for knowledge development |
|
|
|
|||
5.2 Economic conditions for knowledge development |
|
|
|
|||
5.3 Identification of needs, structuring and planning of research or development projects |
|
|
|
|||
5.4 Execution of research or development projects |
|
|
|
|||
5.5 Presentation and evaluation of research or development projects |
|
|
|
This tab contains public material from the course room in Lisam. The information published here is not legally binding, such material can be found under the other tabs on this page.
There are no files available for this course.