Data Structures

Code:

CC114

Acronym:

CC114

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2013/2014 - 2S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~fds/aulas/EDados/1314/
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:AST	0	Plano de Estudos a partir de 2008	1	-	7,5	-
L:CC	69	Plano de estudos de 2008 até 2013/14	1	-	7,5	-
MI:ERS	176	Plano de Estudos a partir de 2007	1	-	7,5	-

Teaching language

Portuguese

Objectives

Strengthen the students programming skills using an object-oriented perspective. Emphasis will be given to fundamental concepts of obect-oriented design, design and implementation of basic data structures and their algorithms. Notions of efficiency and algorithm complexity will be given.

Learning outcomes and competences

At the end of the course, the students are expected to know:

* how to use the basic principles of an object-oriented programming language, namely inheritance, polymorphism, collections and iterators.

* how to write classes that implement some basic data structures such us, lists, stacks, queues, sets and graphs.

* use an API that implement lists, stacks and queues, sets and hash-tables.

* develop basic algorithms associated with the studied data-structures.

* use some algorithmic strategies for problem-solving, namely recursion, backtracking, and divide-and-conquer.

* use an IDE programming environment and a debugger.

 

Working method

Presencial

Program

* Principles of object oriented programming: inheritance, class hierarchy, polymorphism, abstract class interfaces, collections and iterators.

* Abstract data-types. Abstract data-structures: design and implementation; arrays, lists, sets, stacks, queues, doubled linked-lists, circular lists, hash-tables, binary trees, search binary trees, priority queues, heaps and graphs.

* Basic notions of complexity analysis of algorithms: best-case and worst-case scenario. Big.oh notation, empirical metrics for performance, space versus time performance.

* Sorting methods: insertion, bubble-sort, merge-sort, quicksort.

* Search methods: binary search in sorted arrays, list search, depth-first search and breadth-first search.

* Shortest distance algorithms in Graphs: Floyd-Warshall and Dijkstra.

* Problem solving strategies: recursion, backtracking and divide-and-conquer.

Mandatory literature

Stuart Reges and Marty Stepp ; Building Java Programs: A Back to Basics Approach , Addison Wesley, 2nd edition, 2010. ISBN: 0321382838

Complementary Bibliography

Cay Horstmann; Java Concepts, 5th edition, Wiley, 2007
Cormen, Leiserson, Rivest and Stein; ntroduction to Algorithms, 3rd edition, The MIT Press, 2009
Michael T. Goodrich, Roberto Tamassia; Data Structures and Algorithms in Java, 4th edition, Wiley, 2005
Bruce Eckel; Thinking in Java, (4th Edition), Prentice-Hall, 2006

Teaching methods and learning activities

In this course, the students will attend:

- classes to introduce the fundamental concepts of object oriented programming and basic data structures and algorithms.

- tutorial classes where example problems and case studies are presented, discussed and solved using the Java programming language.

- practical classes in which students can get hands-on assistance from faculty in solving their practical programming exercises and assignments. In classes, the students will:

* use the Java programming language.
* use a development IDE like Eclipse or NetBeans.
* solve practical programming exercises as practice for the assignments.
* solve the practical assignments proposed for evaluation.

keywords

Physical sciences > Mathematics > Algorithms
Physical sciences > Computer science > Programming
Physical sciences > Computer science

Evaluation Type

Distributed evaluation with final exam

Assessment Components

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

Amount of time allocated to each course unit

designation	Time (hours)
Estudo autónomo	102,50
Frequência das aulas	70,00
Trabalho laboratorial	30,00
Total:	202,50

Eligibility for exams

In order for students to be eligible to pass the course through the assessments, they must attend over 60% of the lecturers that are given.

Calculation formula of final grade

The are evaluated and classified based on the following assessments:

1. Final exame - 70% of final mark
2. Practical problem-solving assessments - 30% final mark

The final mark is obtained by considering the weighted sum of the partial assessments. Students are approved if the following two conditions are satisfied:

1. the average classification on both written exams is at least 35%.
2. the final classification is higher or equal to 9.5 points out of 20.

The students that aren't approved with this evaluation or those that want to improve their score, can resit once the written components which account for 70% of the final mark.

Special assessment (TE, DA, ...)

The practical component of the course is mandatory.