30398 - FUNDAMENTALS OF COMPUTER SCIENCE
Course taught in English
Go to class group/s: 25
Being familiar with elementary calculus and basic combinatorics help students better understand the covered topics.
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.
- 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.
- First part: introduction to programming; introduction to Python; elementary data structures and control flow constructs; basic algorithms; basic programming techniques.
- Second part: more advanced data structures; introduction to object-oriented programming - classes and methods; pseudo-random numbers.
- 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.
- Read/write Python codes and use the Anaconda development environment.
- Develop basic codes for algorithmic problem solving.
- Face-to-face lectures
- Exercises (exercises, database, software etc.)
Exercises consist in programming assignments to be done in class under the supervision of the Instructor and Teaching Assistants.
|Continuous assessment||Partial exams||General exam|
- 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 final 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 final 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.
- 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.