Insegnamento a.a. 2023-2024

30398 - FUNDAMENTALS OF COMPUTER SCIENCE

Department of Computing Sciences

Course taught in English
Go to class group/s: 25
BEMACS (8 credits - I sem. - OB  |  INF/01)
Course Director:
RICCARDO ZECCHINA

Classes: 25 (I sem.)
Instructors:
Class 25: RICCARDO ZECCHINA


Mission & Content Summary

MISSION

Scope of the course is to provide the basic methodological and conceptual tools which are instrumental for algorithmic thinking. In parallel the course provides an introduction to computer programming, using the Python programming language as reference. The course covers the theoretical and practical foundations of computer science, which is extensively used in subsequent courses of the education program.

CONTENT SUMMARY

Theoretical topics:

- Introduction to the notion of algorithms in Computing (Turing Machines, Church Thesis).

- Analyzing algorithms, growth functions and asymptotic notation (introduce elementary data structures).

- Recurrences and generating functions. Case study: Divide-and-Conquer algorithms.

- Probabilistic Analysis and Randomized Algorithms. Case study: Quicksort.

- Elementary Data Structures.

- Algorithms for Matrix Operations (inversions, eigensystems, page rank).

- Introduction to graph theory and Elementary Graph Algorithms (Minimum Spanning Trees, Single-Source Shortest Paths, Dijkstra's algorithm and Karger's randomized algorithm for the Minimum Cut problem).

- Introduction to computational complexity and NP-completeness.

Programming topics:

1. First part: introduction to programming; introductiontoPython; elementary data structures and control fow constructs; basic algorithms; basic programming techniques.

2. Second part: more  advanced data structures; introduction  to object-oriented programming-classes and methods; pseudo-random numbers.


Intended Learning Outcomes (ILO)

KNOWLEDGE AND UNDERSTANDING

At the end of the course student will be able to...
  • State the basic axioms of the theory of computation and explain the theory of computational complexity. Analyze elementary algorithms and recurrences.
  • Illustrate the role of different data structures for efficient computations.
  • Master the basic notions of graph theory and related algorithms.

APPLYING KNOWLEDGE AND UNDERSTANDING

At the end of the course student will be able to...
  • Read/write Python codes and use the Anaconda development environment.
  • Develop basic codes for algorithmic problem solving.

Teaching methods

  • Face-to-face lectures
  • Exercises (exercises, database, software etc.)

DETAILS

Exercises consist in programming assignments to be done in class under the supervision of the Instructor and Teaching Assistants.


Assessment methods

  Continuous assessment Partial exams General exam
  • Written individual exam (traditional/online)
   x x

ATTENDING AND NOT ATTENDING STUDENTS

The exam consists of a theory part and a programming part, separated in two distinct phases.

The theory part consist in exercises and questions to be answered on paper, and is used to asses the "knowledge and understanding" learning objectives. This contributes to 50% of the %nal grade.

The programming part consists in programming exercises to be performed at the PC in the computer room. It is used to asses the "applying knowledge and understanding" learning objectives. This contributes to the remaining 50% of the %nal grade.

The exam is not open-book: any material outside of what is provided by the instructors is forbidden. In order to pass the exam, students must achieve a passing grade in both parts individually.


Teaching materials


ATTENDING AND NOT ATTENDING STUDENTS

Adopted textbooks:

  • T.H. CORMEN, C.E. LEISERSON, R.L. RIVEST, et al., Introduction to Algorithms, MIT, 3rd edition.
  • A.B. DOWNEY, Think Python, O’Reilly Media, 2dn edition (http://greenteapress.com/wp/think-python-2e/).
  • C. MOORE, S. MERTENS, The Nature of Computation, Oxford (optional).

Handouts of each lecture and sample codes are provided.

Last change 05/03/2024 10:30