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):   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.


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


Syllabus

    Term 1

  1. Digital logic.
  2. Arithmetic for computers.
  3. Elements of set theory. Elements of graph theory.
  4. Finite state machines (automata).
  5. Nondeterministic automata. Determinism vs. nondeterminism.
  6. Regular languages.
  7. Context-free languages and pushdown automata.
  8. Turing machines.
  9. The halting problem. Undecidable problems.
  10. Term 2

  11. Data structures: representations and operations .
  12. Lists; stacks, queues and deques.
  13. Trees, forests, binary trees
  14. Binary tree traversal and other operations. Representation of trees.
  15. Binary search trees.
  16. Organisation of disk storage; methods of file organisation; B-trees.
  17. Algorithms: design and analysis; algorithmic complexity; space utilisation.
  18. 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: Questions for TUTORIAL 1:
    Question 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: 
  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 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: 
  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 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.

    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