INF1A: Informatics 1 - Introduction to Computation
Welcome to Informatics 1 - Introduction to Computation
This is a first year undergraduate course, designed as an introduction to concepts of programming, using the functional programming language Haskell, and to concepts of computation and specification using finite-state systems and propositional logic. These provide examples of the logical ideas of syntax and semantics and the computational ideas of structure and behaviour. You will learn to specify, model, and solve small-scale problems succinctly and at an abstract level.
The course has two strands: Functional Programming (FP) and Computation and Logic (CL).
We will be delivering the course via lectures, weekly tutorials in small groups, demonstrations/drop-in lab sessions, and a chat forum (piazza).
In addition, we have prepared a study guide on Maths for Computing (MC) to help you recall or learn basic mathematics concepts needed throughout the course. The guide consists of videos, exercises and recommended reading.
Please check the Weekly pages for your weekly list of resources, and the Assessment page for details on how you will be assessed. The Resource Lists page contains details about the required and recommended books. Don't forget to keep an eye on the Announcements which will be posted in Learn (and emailed to you)!
Course Team
The lecturers for this course are Don Sannella (FP) and Julian Bradfield (CL). Most questions about the course should be posted on Piazza.
The Course secretary for the course is Kendal Reid.
The lecturer for the Maths for Computing study guide is Heather Yorston. Please only email Heather about the Maths for Computing study guide.
We look forward to teaching you all!
Learning Outcomes
On successful completion of this course, you should be able to:
- Use sets, functions and relations to create a simple mathematical model of a real-world situation and use the syntax and semantics of propositional logic to express simple constraints.
- Solve simple programming tasks and define appropriate data types. Choose appropriate decompositions of given problems and compose corresponding functional programs from suitable function definitions, including their types.
- Read and write programs that use basic list processing functions, list comprehensions, case analysis, recursion, and higher-order functions. Understand algorithms for searching and sorting. Document, test and debug programs.
- Formalise simple propositional reasoning using various methods, including truth tables.
- Design finite state acceptors for particular languages. Use regular expressions to search for simple patterns. Understand the relationship between finite state acceptors and regular expressions.
Course Outline
An introduction to concepts of programming, using the Haskell functional programming language, and to concepts of computation and specification, using finite-state machines and propositional logic. The use of sets, functions and relations to describe models of logic and computation. Programming using functions and data structures, including lists and trees, equational reasoning, case analysis, recursion, higher-order functions, algebraic and abstract data types. Finite-state machines as a basic model of computation: deterministic and non-deterministic automata; regular expressions; acceptors; structured design of finite state machines. Propositional logic: truth tables; satisfiability; deduction. Applications from different areas will be used to illustrate and motivate the material.
Weekly Activities
The course will be delivered in-person. Lectures will be delivered live with live-streaming via Lecture Recordings. Recordings of lectures will be available within an hour or so. Tutorials are in person. Drop-in labs (optional) are in-person.
The course keeps up a steady and fairly demanding pace. It is important to manage your schedule in an effective way for achieving all the learning outcomes of the course. Please read the information below and plan carefully your weeks accordingly.
Each week, you have to complete the following activities:
- Attend four lectures (FP on Mon, Tue and CL on Thu, Fri) and review the associated slides (in the relevant Week's page).
- Attempt two quizzes - one for each strand of the course; FP is due 12.00 on Wednesdays, and CL is due 16.00 on Saturdays.
- Read the required and recommended chapters from the textbook (see the Resource List page).
- Attend one in-person tutorial session. These are 90-minute tutorials scheduled on Thursdays and Fridays, starting in week 2.
- Before attending the tutorials, you must prepare: you have to solve and submit two tutorial assignments, one for each strand of the course. The deadlines for submission are 12:00 on Tuesdays.
There are also weekly optional activities that we encourage you to do:
- Study the weekly topic in Mathematics for Computing
- Attend drop-in lab sessions where you can ask for help from demonstrators, especially with your practical work. There is a session in King's Building on Mondays at 15:10-17:00, and sessions Monday-Friday in Appleton Tower 16:10-18:00.
Each week, the Directed Learning and Independent Learning activities (i.e. the guided self-study activities, such as preparing your tutorial assignments, doing the required reading, or attending the drop-in labs) should take you about 10 hours in total.