AY2018/9 Semester 1
Continual Assessment - Examinations

Examination Information

• Date: 1 December 2018, Saturday
• Time: 1-3pm
• Venue: MPSH1
• Open-book.
• Question paper cover page with instructions | Answer sheet cover page with instructions
• Format:
  • Part A MCQs section: 15 questions (30 marks)
  • Part B Structured questions section: 3 questions (40 marks)
  • Total: 70 marks
  
  
  
• Important:
  • Write your Student Number on the Answer Sheet correctly.
  • Shade and write your Student Number on the MCQ optical form correctly. Double check that you have shaded your Student Number correctly, or your optical form will be wrongly identified and you will get zero mark!
  • Use 2B (or above) pencil to shade on your optical form. The machine may not be able to capture your shading if your pencil is too light.
  
  
  
• Scope:
  All topics covered from Week 1 to Week 12 of lecture, as well as Tutorials 1 to 11. These topics include:
  • Proof techniques: by construction, if-then statements, for-all statements, by contraposition, by contradiction, by regular and strong induction.
  • Propositional logic: logical form and equivalence, conditional statements, valid/invalid arguments
  • Predicate calculus: quantified statements, arguments with quantified statements
  • Number theory: primes, divisibility, gcd, prime factorization, quotient-remainder theorem, well-ordering principle, modulo arithmetic
  • Sequences and recurrence relations
  • Sets, relations, functions: set operations, equivalence relations, equivalence classes, partitions, partial orders, total orders, well-ordered, composition, inverses, closures, injective, surjective, bijective.
  • Counting and probability: pigeonhole principle, addition and multiplication rules, inclusion/exclusion, Bayes formula, conditional probability, counting with and without replacement, ordered and unordered, multisets.
  • Graphs and Trees: undirected and directed graphs, simple graphs, complete graphs, bipartite graphs, weighted graphs, walks, trails, paths, circuits, Euler ciruits, Hamiltonian circuits, connected components, graph isomorphisms, planar graphs, Euler's formula, full binary trees, minimum spanning tree, depth-first traversals, breadth-first traversals.
  
  
  
• Excluded topics:
  
  • RSA
  • Cardinality: Countable, uncountable sets, infinity
  • Proofs of correctness of algorithms
  • Writing programs
  • Dijkstra's Shortest Path Algorithm
  
  
  
• What to bring
  • This is an OPEN BOOK exam. You are allowed to bring in the following:
    • Textbooks: Epp and Campbell
    • Lecture notes given this semester
    • Tutorial solutions given this semester
    • Other handwritten or printed notes
  • All the above should be HARDCOPY, not electronic. Note that if you photocopy the textbook, or print from an e-copy, please do not contravene the FAIR USE act, which allows up to 10% to be printed.
  • You must bring:
    • a non-programmable calculator (graphing calculator is ok, but you must clear all programs and memory)
    • your Student Card (if you do not have your Student Card, your I/C or passport is acceptable) for identification
    • 2B pencil and eraser, for the MCQ optical form
  
  
• Calculators and dictionaries
  • Please see NUS rules for the use of calcultors in exams. In particular, your calculator must be a standalone calculator, ie. not part of your phone or tablet.
  • For foreign students, you may bring a dictionary, which can be hardcopy or electronic.
  
  
• You MUST NOT bring any communication device, which includes, but is not limited to: mobile (cell) phones, smart watches, personal organizers, PDAs, tablets, Google glasses, laptops, PCs.
  
  
• You should be self-sufficient; you cannot borrow anything, eg eraser, sharpener, pencil, from your neighbour during the exam. Raise your hand to talk to an invigilator if you need help.
  
  
• It is a good idea to bring along a jacket, because the venue may be cold.
  
  
• Examination Directory
• Examination Time-Table (Semester 1)

Past-Years' Examination Papers

Answers are not provided.

• Exam paper (AY2018/9 Semester 1) | Answer Sheet (blank)
• Exam paper (AY2017/8 Semester 1) | Answer Sheet (blank)
• Exam paper (AY2016/7 Semester 1) | Answer Sheet (blank)
• Exam paper (AY2015/6 Semester 1)

Preparation

• Preparing for examinations
• Every student's nightmare exam