COMP2211

Course Title: 
Analysis of Algorithms
Credits: 
3
Educational Level: 
II
Semester offered: 
II
Associated Programme: 
B.Sc. CS
Core Course: 
yes
Course Aims: 

This course introduces the student to techniques for designing and analysing efficient algorithms. The emphasis is on the principles at work in algorithms that solve some common problems in a variety of topics, and on techniques for analysing algorithm performance. Students who take this course should already be familiar with writing Mathematical proofs, and be able to argue rigorously about abstract objects such as numbers, functions and graphs.

Syllabus: 
  • Analysing algorithms (solving recurrence equations with the Master Theorem);
  • Algorithm strategies (brute force, greedy, divide, and conquer, branch-and-bound, heuristic; Iterated approximations (Newton = Raphson method, searching for roots of a polynomial {in one variable});
  • Fast exponentiation;
  • Euclid’s algorithm;
  • Discrete logarithm;
  • RSA cryptography;
  • Heaps as implementations for priority queues;
  • Sorting;
  • Binary search trees;
  • Red-Black trees;
  • Hashing;
  • Graphs and graph algorithms;
  • Distributed computing (introduction { consensus vs. election algorithms});
  • NP Basic Computability: uncomputable functions, the halting problem implicated of uncomputability.
Course Assessment: 
  • Final Exam (2-hours long)     60%
  • Coursework       40%
    • 5 assignments
    • 1 in-course test
    • Weekly labs

Students will be required to pass both the coursework and the final examination to pass the course. Attendance at tutorials and lab sessions is mandatory.

Course Prerequisites: 

COMP1126 - Introduction to Computing I,

COMP1127 - Introduction to Computing I,

COMP1161- Object-Oriented Programming AND COMP1210 - Mathematics for Computing.