Algorithm Design and Analysis

Code:

CC2001

Acronym:

CC2001

Level:

200

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2016/2017 - 1S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~pribeiro/aulas/daa1617/
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	0	Official Study Plan	3	-	6	56	162
L:CC	52	Plano de estudos a partir de 2014	2	-	6	56	162
L:M	2	Official Study Plan	2	-	6	56	162
			3
L:Q	1	study plan from 2016/17	3	-	6	56	162
MI:ERS	103	Plano Oficial desde ano letivo 2014	2	-	6	56	162

Teaching language

Portuguese

Objectives

To learn techniques for designing and analyzing algorithms.

Learning outcomes and competences

Improving background on generic models of common problems and the algorithmic techniques for solving them. Practical experience in applying generic algorithms to specific problems. Competence in the asymptotic analysis of the running time of algorithms.

Working method

Presencial

Pre-requirements (prior knowledge) and co-requirements (common knowledge)

Students should know simple algorithms and data structures (for counting, searching and sorting) and a programming language (C/C++ or JAVA).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Program

Asymptotic analysis of algorithms: Big O notation (O, Ω e Θ), estimating execution time, analyzing iterative and recursive programs;

Sorting: sorting as basic element of other algorithms; comparative and non comparative algorithms, binary search and direct and indirect applications;

Algorithm design techniques: exhaustive search, greedy algorithms, divide and conquer, dynamic programming;

Some specialized data structures: priority queues, disjoint sets;

Balanced Binary Search Trees: AVL Trees, Red-Black trees;

Graph algorithms: graph representation, depth-first search, breadth-first search, minimum spanning trees, minimum distances, maximum flow.

Mandatory literature

Cormen Thomas H. 070; Introduction to algorithms. ISBN: 9780262033848 hbk
Skiena Steven S.; The algorithm design manual. ISBN: 978-1-84800-069-8
J. Kleinberg, E. Tardos; Algorithm Design, Addison-Wesley, 2005. ISBN: 978-0321295354

Complementary Bibliography

R. Sedgewick and K. Wayne; Algorithms, 4th Edition, Addison-Wesley, 2011. ISBN: 978-0321573513
S. Halim and F. Halim; Competitive Programming, 1st Edition, 2011

Teaching methods and learning activities

Regular lectures for exposing the program topics and discussing examples. Laboratory classes for solving exercise sheets and programming problems for implementation, with automatic feedback and evaluation by the Mooshak system. Extra-class quizzes for consolidating the exposed material.

Software

Servidor Mooshak para CC2001 (http://mooshak.dcc.fc.up.pt/~daa)
Linguagens de programação/Programming Languages: C, C++ or Java

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Exame	65,00
Teste	25,00
Trabalho laboratorial	10,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Frequência das aulas	0,00
Total:	0,00

Eligibility for exams

Students should fill out at least 50% of the weekly quizzes and should not have a grade lower or equal than 2 (out of seven) in the practical evaluation.

Calculation formula of final grade

P: practical grade, worth 35% of the final grade. Obtained with 3 components: 2 practical tests (2.5 points each) and continuous evaluation solving exercises during the semester (2 points). Required P>2.

T: theoretical grade, worth 65% of the final grade. Obtained with the average of two written tests, with grade from 0 to 20. Required in each test: grade >=5

R: in the appeals phase there will be a single exam, with grade from 0 to 20. Required R>=5.

Final grade (normal) :  C = T*0.65 + NP >= 9.5

Final grade (appeals) :  C = R*0.65 + NP >= 9.5

Examinations or Special Assignments

Along the semester there will be two written tests, two programming tests and there will be lab/homework exercises. The written tests and exams consist of generic questions plus questions about problems seen in the theoretical and laboratory classes. The programming tests are mandatory and consist in the submission, using the Mooshak system, of solutions to problems similar to those seen in the laboratory classes.

Special assessment (TE, DA, ...)

The pratical component is compulsory for every student, regardless of special status of any kind.

Classification improvement

Students approved in 2015/2016 may they to improve their grade in the same evaluatio conditions as last year, and the can opt to redo the theoretical exam, the practical test, or both components.