Last updated: 21 February 2018
Fundamentals of Computing
MSc/PGDip in Computer Science/Data Science/IT/Information Systems & Management 2017/18
Lectures (Term 2):
Tutorials (optional but highly recommended): Term 2
Alternate Fridays 18:00-21:00 on:
26 January, 9 February, 23 February, 9 March, 23 March.
Term 3 Tutorial: Friday 27 April.
***Tutorials will be in Malet Street, MAL B35 (except Term 3 tutorial)***
If you have questions about the module, please send them via email,
or email or phone for an appointment.
Wednesdays 19:30-21:00 (part-time evening students)
Thursdays 15:30-17:00 (full-time and day release students)
See below for Miniquiz on Stacks and Queues
SEE BELOW FOR QUESTIONS FOR TUTORIAL 1
SEE BELOW FOR ANSWERS FOR TUTORIAL 1
SEE BELOW FOR QUESTIONS FOR TUTORIAL 2
SEE BELOW FOR ANSWERS FOR TUTORIAL 2
SEE BELOW FOR QUESTIONS FOR TUTORIAL 3
See below for a note on LIST NOTATION
See below for a simple revision test on Data Structures
(and answers to some of the questions)
Course Structure and Assessment
- 15 credits, 33 lecture hours over 22 weeks and 3 hours of revision lectures
- 2 assessed courseworks
- written examination in May
- final mark = CW (20%) + exam (80%)
- Digital logic.
- Arithmetic for computers.
- Elements of set theory. Elements of graph theory.
- Finite state machines (automata).
- Nondeterministic automata. Determinism vs. nondeterminism.
- Regular languages.
- Context-free languages and pushdown automata.
- Turing machines.
- The halting problem. Undecidable problems.
- Data structures: representations and operations .
- Lists; stacks, queues and deques.
- Trees, forests, binary trees
- Binary tree traversal and other operations. Representation of trees.
- Binary search trees.
- Organisation of disk storage; methods of file organisation; B-trees.
- Algorithms: design and analysis; algorithmic complexity; space utilisation.
- Sorting and searching.
Term 2: Data Structures, File Organisation and Algorithms
Course notes and other materials
Newer textbooks that use JAVA or PYTHON:
Data Structures and Algorithms in PYTHON, Goodrich & Tamassia (Wiley 2016)
Data Structures and Algorithms in PYTHON, Lee & Hubbard (Springer 2015)
Data Structures and Algorithms in JAVA, Goodrich & Tamassia (Wiley 2011)
Data Structures with JAVA, Ford & Topp (Pearson 2005)
Data Structures and Abstractions with JAVA, Carrano (Pearson 2007)
Questions for TUTORIAL 1:
Question 6 on FoC exam papers 2009-2016
NOTE: Some of these questions require knowledge of material to be covered in week 3.
ANSWERS for Tutorial 1:
Questions for TUTORIAL 2:
Question 8 on FoC exam papers 2009-2013
Question 9 on FoC exam papers 2009 and 2012
NOTE: Some of these questions refer to a binary tree constructed in an earlier question.
As you do not have that tree, use instead
this binary tree.
ANSWERS for Tutorial 2:
NOTE: These are the answers for the binary trees referred to in the exam paper
not the binary tree referred to above.
Here is a
simple revision test on Data Structures
The questions are easier than those you can expect in the
coursework assignment and in the exam.
---   and some model answers:
Questions for TUTORIAL 3:
Questions 7 and 8 on FoC exam papers 2009-2016
Question 9 on FoC exam papers 2009, 2011, 2012
NOTE: Some of these questions were covered in Tutorial 2 using the binary tree
referred to above.
- Lists:  notes pp.1-4
- Lists:  notes pp.5-8
- File Organisation: notes
- Slides from lecture:
Coursework Term 2
Issued on Wednesday, 21 February 2018
Submission deadline: Monday, 23 April (before noon)
Late submission deadline: Monday, 7 May (before noon)
Return date by Monday, 14 May
- Coursework assignment:  Part 1
- Coursework assignment:  Part 2
- Datafile:  TEXT