Last updated: 21 February 2018
Fundamentals of Computing
MSc/PGDip in Computer Science/Data Science/IT/Information Systems & Management 2017/18
Lecturers:
Lectures (Term 2):

Wednesdays 19:3021:00 (parttime evening students)

Thursdays 15:3017:00 (fulltime and day release students)
Tutorials (optional but highly recommended): Term 2
Alternate Fridays 18:0021: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.
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%)
Syllabus
Term 1
 Digital logic.
 Arithmetic for computers.
 Elements of set theory. Elements of graph theory.
 Finite state machines (automata).
 Nondeterministic automata. Determinism vs. nondeterminism.
 Regular languages.
 Contextfree languages and pushdown automata.
 Turing machines.
 The halting problem. Undecidable problems.
Term 2
 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; Btrees.
 Algorithms: design and analysis; algorithmic complexity; space utilisation.
 Sorting and searching.
Term 2: Data Structures, File Organisation and Algorithms
Course notes and other materials
DATA STRUCTURES
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)
 TERMINOLOGY
 Lists: notes pp.14
 Lists: notes pp.58
Questions for TUTORIAL 1:
Question 1
Question 6 on FoC exam papers 20092016
NOTE: Some of these questions require knowledge of material to be covered in week 3.
ANSWERS for Tutorial 1:
Q1
Q6/2009
Q6/2010
Q6/2011
Q6/2012
Q6/2013
Q6/2014
Q6/2015
Q6/2016
Questions for TUTORIAL 2:
Question 8 on FoC exam papers 20092013
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:
Q8/2009
Q8/2010
Q8/2011
Q8/2012
Q8/2013
Q9/2009
Q9/2012
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:
here
Questions for TUTORIAL 3:
Questions 7 and 8 on FoC exam papers 20092016
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.
FILE ORGANISATION
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