30398 - FUNDAMENTALS OF COMPUTER SCIENCE
Course offered to incoming exchange students
Department of Computing Sciences
RICCARDO ZECCHINA
Mission & Content Summary
MISSION
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
|
- Master the basic notions of graph theory and related algorithms.
APPLYING KNOWLEDGE AND UNDERSTANDING
- 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 | |
---|---|---|---|
|
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.