Last updated: 11 July 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
(cancelled).
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 ANSWERS FOR TUTORIAL 3
SEE BELOW FOR QUESTIONS FOR TUTORIAL 4
SEE BELOW FOR ANSWERS FOR TUTORIAL 4
***SEE BELOW FOR ANSWERS FOR 2017 Exam Paper
SEE BELOW FOR MODEL ANSWER FOR ASSIGNMENT Q.6
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.
ANSWERS for Tutorial 3:
Q7/2009
Q8/2009
Q7/2010
Q8/2010
Q7/2011
Q8/2011
Q7/2012
Q8/2012
Q7/2013
Q8/2013
Q7/2014
Q8/2014
Q7/2015
Q8/2015
Q7/2016
Q8/2016
Q9/2009
Q9/2011
Q9/2012
FILE ORGANISATION
Additional Questions from exam papers on File Organisation for TUTORIAL 4:
2011 Q.10(a); 2013 Q.9(a); 2015 Q.9(a); 2016 Q.9(a) (i) & (iii)
ANSWERS for Tutorial 4 :
Q10/2011
Q9/2013
Q9/2015
Q9/2016
ALGORITHMS
The two lectures on algorithms are based on material from
"Programming Pearls" by Jon Bentley (2nd edition):
 Column 8: Maximum subsequence sum problem
 Column 11: Sorting
Maximum subsequence sum problem
Sorting
***MODEL ANSWERS to 2017 EXAM PAPER
Q6/2017
Q7/2017
Q8/2017
Q9a/2017
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
Assignment model answer for Q.6