Introduction and objectives

This course is about designing algorithms for computational problems, and how to think clearly about analyzing correctness and running time. The main goal is to provide the intellectual tools needed for designing and analyzing your own algorithms for new problems you need to solve in the future.

The official plan of this course is hosted in FCUP here.

Learning outcomes and competences

Students should be able to understand the relationship between algorithm design, correctness proof and complexity analysis. Students should learn algorithmic techniques of general applicability and get to know some major algorithms in a few common domains. They will also obtain practical experience in applying generic algorithms to specific problems.

Syllabus

  • Algorithm correctness
  • Complexity: worst/best-case analysis
  • Fundamentals of asymptotic analysis
  • Average-case and randomized algorithms
  • Recursive algorithms
  • Amortized analysis
  • Data structures - Collections and Dictionaries

Lectures

Literature and Material

Slides

  1. Introduction to the course
  2. Algorithm correctness
  3. Counting steps and asymptotic notation
  4. Average-time and probabilistic algorithms
  5. Amortised analysis
  6. Data structures

Main book

Example Tests

  • Intermediate test, used on the 10th Nov 2023, covering around 30% of the topics
  • Final test (or improvement test), used on the 15th Dec 2023, covering the remaining 70% of the topics

Previous years

Complementary Bibliography

Teaching methods and learning activities

Lectures; intermediate test (mandatory) and final test or final exam.

The lectures mix the presentation of new material (introducing concepts, main algorithms and some results) with interactive discussion of their application when solving real problems.

The homework focus is on practical application of algorithmic concepts, consolidating the learned material.

The final exam and intermediate tests (closed book), globally evaluates the knowledge acquired by the students.

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation Weight (%)
Exam 70,00
Test 30,00

Amount of time allocated to each course unit

designation Time (hours)
Home study 120,00
Attendance time 42,00
Total: 162,00

Eligibility for exams

All students will be admitted to the exams.

Calculation formula of final grade

  • (IT) intermediate mid-term test (mandatory) 30%
    • 10 Nov, during the lecture time.
  • (FE) final exam: 70% (can be replaced by IT2)

  • (IT2) improvement test: can replace the final exam. Required IT2 >= 8.

1st Exam (“Normal”) classification: C = max(FE,IT2)0.7+ IT0.3 >= 9.5

2nd Exam (“Recurso”) classification: C = max(FE0.7+IT0.3, FE) >= 9.5

Required FE >=8.

Contact

The day and time for appointments is Friday afternoon (José Proença). Please email me the day before if you wish to meet. If you prefer you can also just send an email with your questions to José Proença, or we can try to book an online meeting.