Data Structure and Algorithms Analysis SWEN 3411

Course description:

This course revisits and covers in depth lists, stacks, and queues. In addition, sets, trees, heaps, graphs and hash tables. The course will also presents in details notions of complexity and algorithm running time analysis; notion of abstract data type; sets and sequences as examples. Several searching and sorting algorithms will be explained during the coverage of the previously mentioned data structures.

Course Aims:

Upon completion of the course, students will be able to:
  • Be able to determine the time complexity of algorithms using amortised analysis 
  • Be able to design and analyse simple randomised algorithms 
  • Understand the implementation, complexity analysis and some applications of classical algorithms for string matching, primality testing 
  • Be able to formulate and solve max-flow problems 
  • Be able to formulate and solve linear programs 
  • Understand the implementation, complexity analysis and some applications of splay trees, binomial heaps, Fibonacci heaps and disjoint sets

Course outcomes:

By the successful completion of this unit, students will be able to:
• Analyze and make a critical comparison between alternative designs of advanced algorithms and data structures.
• Design appropriate and efficient implementations for a number of advanced data abstractions.