BSc:PhilosophyI
Philosophy 1: Logic and Discrete Mathematic
- Course name: Philosophy 1: Logic and Discrete Mathematic
- Course number: n/a
- Subject area: n/a
Course characteristics
This course consists of two distinct but overlapping parts: i. Logic; and ii. Discrete Mathematics.
The first part of the course is an introduction to formal symbolic logic. Philosopher John Locke once wrote that ``logic is the anatomy of thought. This part of the course will teach students to analyse and evaluate arguments using the formal techniques of modern symbolic logic.
The second part of the is designed for students to teach them basic notions of graph theory, discrete optimization and dynamic programming. This part will give practical experience with basic algorithms in discrete mathematics.
Key concepts of the class
- Deductive Reasoning
- Inductive Reasoning
- Categorical Logic
- Propositional Logic
- Predicate Logic
- Basic elements of Graph Theory
- Planar Graphs
- Algorithms on Graphs
What is the purpose of this course?
The first part of the course (on Logic) sets students upon a path of finely honed logical skills essential for life in the modern world. This part of the course is thus specifically designed to improve writing, thinking and oral presentation skills that are applicable to all areas of academic study and relevant to working life.
The Discrete Math part of the course introduces students to the basic concepts of structuring algorithms through graph theory. This gives students the skills of deep algorithmic thinking. Thus, the successful completion of the course by students will give them the skills for further deep mastering of computer science courses.
Course Objectives Based on Bloom’s Taxonomy
What should a student remember at the end of the course?
- how to use Venn diagrams
- how to calculate truth values
- the formal structures of some arguments
- the difference between deduction and induction
- how to build spanning trees
- how to find Euler tour and Hamilton path
- how to use Dijkstra’s algorithm
- how to solve maximum flow problem
What should a student be able to understand at the end of the course?
By the end of the course, the students should be able to understand:
- what is categorical logic
- what is propositional logic
- what is predicate logic
- what is the difference between deduction and induction
- what is trees and spanning trees
- what is Euler and Hamilton graphs
- what is planar graphs
- Dijkstra’s algorithm
What should a student be able to apply at the end of the course?
By the end of the course, the students should be able to apply the content of this course in all areas of their academic study but also in their working life, with special reference to the following disciplines:
- computer science
- engineering
- robotics
Course evaluation
Type Default points Proposed points
Final Exam (Written, Math) 40 40 Mid Term (Written, Logic) 40 40 Participation/Attendance 20 20
Marks Final Exam – Written – on Math (40% of final grade) The final exam will consist of theoretical and practical questions. The exam will be 90 minutes long.
Mid-Term Exam – Written – on Logic (30% of final grade) The midterm exam will consist of quizzes and various exercises (such as open theoretical questions, multiple choices, and true/false questions). The Mid-Term will be held in class on week 8. The exam will last 75 minutes.
Attendance/Participation Weekly exercises (hereby reports) must be uploaded on moodle the day after the lab sessions are over. Although reports are not marked, they directly count towards participation. Failure to submit reports will incur in a penalty of the course mark, which will be proportional to the number of reports missing.
| Proposed points | ||
|---|---|---|
| Final Exam (Written, Math) | 40 | 40 |
| Mid Term (Written, Logic) | 40 | 40 |
| Participation/Attendance | 20 | 20 |
If necessary, please indicate freely your course’s features in terms of students’ performance assessment.
Labs/seminar classes:
In-class participation 1 point for each individual contribution in a class but not more than 1 point a week (i.e. 14 points in total for 14 study weeks), overall course contribution (to accumulate extra-class activities valuable to the course progress, e.g. a short presentation, book review, very active in-class participation, etc.) up to 6 points.
Interim performance assessment:
In-class tests up to 10 points for each test (i.e. up to 40 points in total for 2 theory and 2 practice tests), computational practicum assignment up to 10 points for each task (i.e. up to 30 points for 3 tasks).
Exams:
Mid-term exam up to 30 points, final examination up to 30 points.
Overall score: 100 points (100%).
Grades range
| Proposed range | ||
|---|---|---|
| A. Excellent | 85-100 | 85-100 |
| B. Good | 75-84 | 75-84 |
| C. Satisfactory | 60-75 | 60-75 |
| D. Poor | 0-59 | 0-59 |
If necessary, please indicate freely your course’s grading features: The semester starts with the default range as proposed, but it may change slightly (usually reduced) depending on how the semester progresses.
Resources and reference material
- Alfred V.Aho, Monica S.Lam, Ravi Sethi, Jeffrey D. Ullman. Compilers. Principles, Techniques, & Tools, Second Edition, Addison-Wesley, 2007, ISBN 0-321-48681-1.
- N. Wirth, Compiler Construction, Addison-Wesley, 1996, ISBN 0-201-40353-6
- http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf, 2005
Course Sections
The main sections of the course and approximate hour distribution between them is as follows:
| Section | Section Title | Lecture Hours | Seminars (labs) | Self-study | Knowledge evaluation |
|---|---|---|---|---|---|
| 1 | Introduction to compilers and compiler construction | 12 | 6 | 12 | 2 |
| 2 | Lexical, syntax and semantic analyses | 8 | 4 | 8 | 1 |
| 3 | Code generation, optimization and virtual machines | 8 | 4 | 8 | 1 |
| 4 | Project presentation | 2 |
Section 1
Section title:
Introduction to compilers and compiler construction
Topics covered in this section:
- Basic notions: source and target languages, target architecture, compilation phases.
- The history of languages and compiler development. Typical compiler examples.
- Compilation & interpretation. Virtual machines, JIT & AOT technologies. Hybrid modes.
What forms of evaluation were used to test students’ performance in this section?
|a|c| & Yes/No
Development of individual parts of software product code & 1
Homework and group projects & 1
Midterm evaluation & 0
Testing (written or computer based) & 0
Reports & 0
Essays & 0
Oral polls & 1
Discussions & 1
Typical questions for ongoing performance evaluation within this section
- What is compilation process?
- What’s the difference between compiler and interpreter?
Typical questions for seminar classes (labs) within this section
- How to compile a program?
- How to run a program?
- How to debug a program?
Test questions for final assessment in this section
- What are significant phases of a compilation process?
- Why do we need optimization phase?
- What’s the difference between syntax and semantic analyses?
Section 2
Section title:
Lexical, syntax and semantic analyses
Topics covered in this section:
- Compilation pipeline & compilation data structures
- Lexical analysis and deterministic state automata
- Bottom-up and top-down parsing
- Principles of semantic analysis
What forms of evaluation were used to test students’ performance in this section?
|a|c| & Yes/No
Development of individual parts of software product code & 1
Homework and group projects & 1
Midterm evaluation & 0
Testing (written or computer based) & 0
Reports & 1
Essays & 0
Oral polls & 0
Discussions & 1
Typical questions for ongoing performance evaluation within this section
- Abstract syntax tree & symbol tables: what is it for and how create and manage them?
- How to organize communication between compilation phases?
- What are basic differences between bottom-up and top-down parsing?
Typical questions for seminar classes (labs) within this section
- How to implement a hash function for a symbol table?
- How to write a grammar for an expression using YACC/Bison tool?
Test questions for final assessment in this section
- Characterize the principles of top-down and bottom-up parsing.
- Explain how a symbol table can be implemented.
- AST: is it a tree or a graph? What’s about semantic attributes in an AST?
Section 3
Section title:
Code generation, optimization and virtual machines
Topics covered in this section:
- Low-level code generation: machine instructions, assembly language
- Virtual machines’ architecture and their byte codes.
- The notion of language projections.
- Introduction to optimization techniques.
What forms of evaluation were used to test students’ performance in this section?
|a|c| & Yes/No
Development of individual parts of software product code & 1
Homework and group projects & 1
Midterm evaluation & 0
Testing (written or computer based) & 0
Reports & 0
Essays & 0
Oral polls & 0
Discussions & 0
Typical questions for ongoing performance evaluation within this section
- What’s the difference between assembly and machine instructions?
- What’s the similarities and differences between real target platforms and virtual machines?
- Explain some of widely used approaches for optimizing program source code? How these approaches can be implemented in a compiler?
Typical questions for seminar classes (labs) within this section
- Explain the idea behind the notion of control flow graph.
- What is “basic block” in CFG and what is it for?
Test questions for final assessment in this section
- Give some simple examples of language-code projections.
- How the object code for an expression can be optimized?
- How to avoid tail recursion while optimizing code?