COMP108 Algorithmic Foundations - Past Exam Papers
Below are some past papers.
Checklist for preparing exam
- Lecture notes, Tutorials, In-class exercises, Class tests, Past exam papers
- Basics
- Basics of algorithms - what is an algorithm, representation (pseudo code
writing and tracing), analysis (time complexity,
space complexity, looking for improvement)
- simple example algorithms - Finding minimum/maximum
- Mathematical tools
- Big-O notation - definition, determining/proving the least order of
growth of a function
- Mathematical induction
- Polynomial / Exponential time algorithms
- Searching: linear search vs binary search, string matching - the algorithm, time and
space complexity
- Sorting: selection sort, bubble sort, merge sort - the algorithm,
time complexity (polynomial)
- Brute force approach - example algorithms (traveling salesman problem,
knapsack problem), time complexity (exponential)
- Divide and conquer method
- What is divide and conquer method?
- Merge sort
- Tower of Hanoi
- Fibonacci number
- Other simple tasks like finding maximum / minimum / sum / count of occurrences for an array
- Recurrence - definition, how to use recurrence to describe
time complexity of divide and conquer algorithms,
solving recurrences
- Graph theory
- Undirected / directed graphs -
basic terminologies (vertex, edge, adjacency, incidency, degree, path, etc.),
representation
(adjacency / incidence matrix and list)
- Euler circuit - definition, condition for presence / absence of
Euler circuit
- More terminologies on graphs - Hamiltonian circuit
- Graph traversal - Breadth-first search and Depth-first search
- Tree - definitions, terminologies (parent, children, root, etc.),
different traversals of binary tree
- Greedy methods
- What is greedy method?
- Kruskal's algorithm for computing minimum spanning tree
- Dijkstra's algorithm for finding single source shortest paths
- Greedy algorithm (not optimal) for 0/1 Knapsack problem
- Describe the algorithms, able to run them on examples,
pseudo code
- Dynamic programming (DP)
- What is dynamic programming?
- Computing Fibonacci numbers - execution tree of recursive algorithm,
recursive algorithm and dynamic programming algorithm,
time complexity
- Assembly line scheduling - the problem formulation, subproblems,
the algorithm, time complexity
Back to COMP108 homepage