PGIA7323 and SI14039 - Design and Analysis of Algorithms

	A	B	C	D	E
1	This is the www repository for the Design and Analysis of Algorithms Class of the graduate program on Applied Informatics (PPGIA) and for Algorithms and Heuristics for NP-Complete Problems of the undergraduate program on Information System (BSI) from UFRPE. For any questions, please contac us: "PAA-UFRPE 2013-1" <paa-ufrpe-2013-1@googlegroups.com>,
2	Teacher
3			Jones Albuquerque	DEINFO-PPGIA	www.ppgia.ufrpe.br
4
5
6	Course Overview
7	SI14039 Plan		http://bit.ly/16PGPyE
8
9	Books
10	Text Book		Introduction to Algorithms, Thomas Cormen	http://www.cs.dartmouth.edu/~thc/	http://mitpress.mit.edu/books/introduction-algorithms
11	Reference Books
12			Introduction to Algorithms, Udi Manber	http://en.wikipedia.org/wiki/Udi_Manber	http://www.ebooks-share.net/introduction-to-algorithms-a-creative-approach/
13			Projeto de Algoritmos, Nivio Ziviani	http://homepages.dcc.ufmg.br/~nivio/en/index.php	http://www.dcc.ufmg.br/algoritmos/
14
15	Course - References
16			Tim Roughgarden	Stanford University	http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=IntroToAlgorithms
17			Antonio Loureiro	UFMG	http://homepages.dcc.ufmg.br/~loureiro/paa
18			Tiago Ferreira	UFRPE	http://www.ppgia.ufrpe.br/docentes/taef/disciplinas/PAA/index.html
19
20	Course Scores
21			Tests (60%) + Exercises (20%) + Projects (20%)	https://docs.google.com/spreadsheet/ccc?key=0AsRu59z3YZBHdGIzS1dhdjkyVWZiX3BIQlFIaFVBVkE#gid=0
22
23
24	Syllabus
25	DATE	CLASS	TOPIC	FOR HOME	REFERENCE
26	31/03/2014	1	Overview	Review of concepts
27					http://www.dcc.ufmg.br/algoritmos/index.php
28	02/04/2014 a 23/04/2014	2	Review, TEST 1	http://www.cs.helsinki.fi/u/tzniinim/teaching/daa2012/sol-I.pdf
29	28/04/2014	3	Dynamic Programming Video	http://www.youtube.com/watch?v=s1KmGK9D6ag	Chapter 15 - Text Book
30	30/04/2014 a 19/05/2014	04/07/2014	Dynamic Programming - Motivation - Bin Packing Problem	EXERCISE 1: Is it possible to solve bin packing problem better than O(2**n)?	Chapter 15 - Text Book
31				Solutions by Dynamic Programming:
32				http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/mochila-bool.html#prog-din	http://www.cs.uiuc.edu/class/sp07/cs473g/lectures/01-recursion.pdf
33				EXERCISE 2: to implement the binpacking code above!
34	21/05/2014	8	Implementation Status report		Chapter 1 - Nivio Ziviani´s Book
35	26/05/2014	9	Dynamic Programming - Solutions	http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/dynamic-programming.html	Chapter 15 - Text Book
36		10	Design and Analysis Problems and Strategies	http://homepages.dcc.ufmg.br/~loureiro/alg/111/paa_02Paradigmas.pdf	Chapter 15 - Text Book
37		11	Design and Analysis Problems and Strategies	http://www.ppgia.ufrpe.br/docentes/taef/disciplinas/PAA/Aula06.pdf
38		12	Exercises
39		13	Greedy Algorithms - Motivation	http://www.youtube.com/watch?v=rsGOB80v0-k	exercise: solution of the Traveling Ssalesman Problem - 29/04/2013
40				EXERCISE 3: Is is possible to solve TSP (Traveling Salesman Problem)? How?
41		14	List of EXERCISES with some practical problems that can be solved by greedy strategies	http://www.cs.wustl.edu/~sg/CSE441_FL04/greedy-practice-probs.pdf	and some solutions: http://www.cs.wustl.edu/~sg/CS441_FL01/greedy-practice-problems.pdf
42		15	Greedy Algorithms - Solutions and Exercises
43		16	Greedy Algorithms - Matroids and Exercises	http://ria.ua.pt/bitstream/10773/10085/1/tese_ayagi%20dias.pdf	http://www.das.ufsc.br/~camponog/Disciplinas/DAS-9003/slides_CLR/l17-matroides.pdf
44		17	TEST 2
45		18	Advanced Data Structures - B-Trees	http://pt.wikipedia.org/wiki/%C3%81rvore_B	http://www.perforce.com/blog/110928/short-history-btree
46		19	Advanced Data Structures - B-Trees PROBLEMS	http://www.google.es/url?sa=t&rct=j&q=b-tree%20practice%20problems&source=web&cd=1&cad=rja&ved=0CCkQFjAA&url=http%3A%2F%2Fwww.cs.wustl.edu%2F~sg%2FCSE241_SP06%2Fbtree-practice-probs.pdf&ei=ej2qUd35IoSK9QTEl4GgAw&usg=AFQjCNFpFMY6SktsdkrK-lGN_8lRjAnkAg&bvm=bv.47244034,d.eWU
47		20	Advanced Data Structures - B-Trees PROBLEMS	http://www.slideshare.net/ThiagoChaves/apresentao-sobre-rvores-b	http://www.gpec.ucdb.br/pistori/disciplinas/ed/aulas_II/bt.htm
48		21	Binomial Heaps??? and Design and Analysis Problems
49		22	Design and Analysis Problems	http://www.cs.sunysb.edu/~algorith/major_section/1.5.shtml
50		23	Graph Algorithms - Elementary	http://www.ime.usp.br/~pf/algoritmos_em_grafos/aulas/bfs.html	http://www.youtube.com/watch?v=BmsC6AEbkrw
51		24	IMPLEMENTATION (TEST 3)	https://docs.google.com/document/d/19feaYu4kF4Wg8x2KhakbZE4ttrYiZEgdiAQrFc2Xkf4/edit?usp=sharing
52		25	Graph Algorithms - All-Pair Shortest Paths	http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
53		26	Graph Algorithms - Maximum Flow	http://en.wikipedia.org/wiki/Shortest_path_problem
54		27	Design and Analysis Problems
55		28	TEST 4 - Submission to SBGAMES 2013 and LATEX	https://docs.google.com/document/d/1Rvd69VMrVHgrgV5oagbJ3iY_qu5thTaMAVXeA6JRcMs/edit?usp=sharing	http://200.17.137.109:8081/xiscanoe/courses-1/mentoring/tools-editors/
56		29	Advanced Topics - PROJECT DISCUSSION
57		30	Advanced Topics - Heuristics for solving Complex Problems
58		31	Advanced Topics - Heuristics for solving Complex Problems
59		32	Advanced Topics - Heuristics for solving Complex Problems
60		33	FINAL IMPLEMENTATION (Presentation of PROJECT and submission)
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100