Data Structures

Code:

CC1007

Acronym:

CC1007

Level:

100

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2020/2021 - 2S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~pribeiro/aulas/edados2021/
Responsible unit:	Department of Computer Science
Course/CS Responsible:	Bachelor in Computer Science

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
L:B	3	Official Study Plan	3	-	6	56	162
L:CC	97	Plano de estudos a partir de 2014	1	-	6	56	162
L:F	3	Official Study Plan	2	-	6	56	162
			3
L:G	1	study plan from 2017/18	2	-	6	56	162
			3
L:M	6	Official Study Plan	2	-	6	56	162
			3
L:Q	2	study plan from 2016/17	3	-	6	56	162
MI:ERS	132	Plano Oficial desde ano letivo 2014	1	-	6	56	162

Teaching language

Portuguese

Objectives

It is intended that the student reinforces his programmings skills, gets to know some of the main data structures and associated algorithms and gains basic knowledge on the conception and analysis of algorithms.

Learning outcomes and competences

The main learning goals are:

- Proficiency with the Java language and with the object oriented programming paradigm;
- Knowledge of the main basic data structures: arrays, matrices, linked lists and binary trees;
- Knowledge of the main abstract types of data and their implementations: queues, stacks, sets, dictionaries and priority queues;
- Basic knowledge of algorithmic analsyis and comprehension of the main classes of complexity;
- Enrichment of knowledge about some algorithmic techniques such as recursion, backtracking search and divide-and-conquer;
- Practical experience applied to concrete problems.

Working method

Presencial

Program

- Fundamental Java Concepts:
  . Classes, objects, attributes and methods
  . Primitive types, Strings, warappers, arrays and and enum types
  . Expressions, operators and control flow instructions
  . Input/Output and the the Scanner class
  . Packages and default libraries of Java
  . Principles of software development, style and documentation
- Object Oriented Programming:
  . Goals, principles, patterns and inheritance mechanism
  . Interfaces and Abstract Data Types (ADTs)
  . Using generics and iterators
- Asymptotic Analysis Concepts:
  . Basic notions of asymptotic analysis
  . Main complexity classes and how to compare them
  . Examples of algorithmic analysis
- Algorithm Design Techniques:
  . Structures Programming
  . Recursion
  . Exhaustive search and backtracking
  . Divid-and-conquer
- Fundamental Data Structures:
  . Arrays and matrices
  . Simple linked lists, circular linked lists and doubly linked lists
  . Árvores binárias, árvores de pesquisa e heaps
- Abstract Data ypes and their possible Implementations:
  . Sequences, stacks, queues and deques
  . Associative containers: sets and maps
  . Priority queues

Mandatory literature

Goodrich Michael T.; Data structures and algorithms in Java. ISBN: 0-471-73884-0

Complementary Bibliography

Sedgewick Robert; Introduction to programming in Java. ISBN: 978-0-321-49805-2
Cormen Thomas H. 070; Introduction to algorithms. ISBN: 978-0-262-03384-8

Teaching methods and learning activities

Theory classes where the material is explained, including live coding sessions. Practical classes with programming exercises.

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Exame	70,00
Teste	30,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Frequência das aulas	56,00
Estudo autónomo	66,00
Trabalho laboratorial	40,00
Total:	162,00

Eligibility for exams

Have filled in at least 50% of the online weekly quizzes.

Calculation formula of final grade

- NP: practical grade, worth 30% of the final grade, obtained with:
2 practical programming tests, in the Mooshak environment (6 points, 30% of final grade)

- EN: "normal" exam grade, worth 70% of the final grade, obtained with a written exam with a grade from 0 to 20.

"Normal" season classification: C = EN*0.7 + NP ≥ 9.5

- ER: on the "recurso" season, a single exam will be made, with a grade from 0 to 20, and it is not possible to repeat the practical prigramming tests.

"Recurso" season classification: C = ER*0.7 + NP ≥ 9.5

Examinations or Special Assignments

2 practical programming tests during the semester.

Classification improvement

Contact the professor (you can try to improve just the pratical component, just the theoretical component, or both)