Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Está em: • 2024-2

Barra Lateral

Índice

cmp625:2024-2

Tabela de Conteúdos

CMP 625: Algorithms (2024/2)

Somebody once asked John Hopcroft about the problem of P and NP. He answered: “On Tuesdays, I try to prove that they are equal, on the rest of the week - that they are different.” I believe that he has reduced the time to try to show that they are equal to Sunday afternoons.

General information

Professor: Marcus Ritt
Total hours: 60 h (in 30 lectures of 2h)
Credits: 4
Summary: Algorithms: Analysis of algorithms. Main techniques for designing algorithms.
Time and room: Tue/Thu 10.30, 109/43413.
Consultation hours: By appointment.
Details: On the homepage of the course at PPGC.

News

  • Oct 4, 2024: second list of exercises and solution to the first list available
  • First lecture: Sep 24, 2024.

Results

Additional material

Lectures

No. Date Topics Chap. in
notes 		Exercises Solutions Reading
1 24/09 Administrativa. Introduction. 1 E1 S1 1
2 26/09 Introduction and representative problems. 2 1
3 01/10 Introduction and representative problems. 2 1
4 03/10 Exercises: Introduction.
5 08/10 Basics of analysis 1. 2 E2 S2 2
6 10/10 Basics of analysis 2. 2 2
7 15/10 Basics of analysis 3. 2 2
8 17/10 Exercises: Basics.
9 22/10 Graph algorithms 1. 4.2 E3 S3 3
10 24/10 Graph algorithms 2. 4.2 3
11 29/10 Graph algorithms 3. 4.2 3
12 31/10 Exercises: Graphs.
13 05/11 Greedy algorithms 1. 4 E4 S4 4
14 07/11 Greedy algorithms 2. 4 4
15 12/11 Greedy algorithms 3. 4 4
16 14/11 Exercises: Greedy algorithms.
17 19/11 Divide-and-conquer algorithms 1. 5 E5 S5 5
18 21/11 Divide-and-conquer algorithms 2. 5 5
19 26/11 Divide-and-conquer algorithms 3. 5 5
20 28/11 Exercises: Divide-and-conquer algorithms.
21 03/12 Dynamic programming 1. 6 E6 S6 6
22 05/12 Dynamic programming 2. 6 6
23 10/12 Dynamic programming 3. 6 6
24 12/12 Dynamic programming 4. 6 6
25 17/12 Exercises: Dynamic programming.
26 19/12 Exam.
23/12-04/01 Summer break
27 07/01 Review of the exam and exercises.
28 09-13/01 Retake Exams.
29 14/01 Additional topics and exercises in design techniques 4,5,6
30 16/01 Additional topics and exercises in design techniques 4,5,6
18/01 Official end of the lecture period. 4,5,6
20/01 Qualification exam.

Evaluation

See the homepage of the course at PPGC. Specifically in this source we have

  • An exam (see the agenda above), which contributes 60% to the final grade
  • Six exercise lists, which contribute 30% to the final grade
  • The presentation of two solved exercises in class, which contributes 10% to the final grade

Material

  • Template (LaTeX,PDF) for exercise lists.

Bibliography

  • Jon Kleinberg and Éva Tardos. Algorithm design. Addison-Wesley, 2005.
  • Udi Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.
  • Jeff Erickson. Algorithms. 2019.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 4th edition, 2022.
  • Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: Algorithms and complexity. Prentice-Hall, dover edition, 1982.
  • S. Dasgupta, C. Papadimitriou, and U. Vazirani. Algoritmos. McGraw-Hill, 2009.
  • Juraj Hromkovič. Algorithmics for hard problems. Springer, 2001. INF 65.012.122 H873a.
  • Bernhard H. Korte and Jens Vygen. Combinatorial Optimization – Theory and Algorithms. Springer, 6th edition, 2018. INF 65.012.122 K85c.

Locations of visitors to this page

cmp625/2024-2.txt · Esta página foi modificada pela última vez em: 2025/03/10 09:19 (Edição externa)

Ferramentas de Página

Excepto menção em contrário, o conteúdo neste wiki está sob a seguinte licença: CC Attribution-Noncommercial-Share Alike 4.0 International
CC Attribution-Noncommercial-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki