SCS2103 Algorithms and Data Structures

This course introduces fundamental algorithms in the context of significant applications in science, engineering, and commerce. Classical algorithms and data structures, with an emphasis on implementing them in modern programming environments, and using them to solve real-world problems. Particular emphasis is given to algorithms for sorting, searching, string processing, and graph algorithms. Fundamental algorithms in a number of other areas are covered as well, including geometric algorithms and some algorithms from operations research. The course concentrates on developing implementations, understanding their performance characteristics, and estimating their potential effectiveness in applications.

Course Objectives
The objectives of the course are:

• Introduce the student to the concept of data structures through abstract data structures including lists, sorted lists, stacks, queues, deques, sets/maps, directed acyclic graphs, and graphs; and implementations including the use of linked lists, arrays, binary search trees, M-way search trees, hash tables, complete trees, and adjacency matrices and lists.
• Introduce the student to algorithms design including greedy, divide-and-conquer, random and backtracking algorithms and dynamic programming; and specific algorithms including, for example, resizing arrays, balancing search trees, shortest path, and spanning trees.

Learning Outcomes
Upon completion of the course, the students will be able to:

• Apply appropriate data structures and abstract data types (ADT) such as bags, lists, stacks, queues, trees, tables, and graphs in problem solving
• Apply object-oriented principles of polymorphism, inheritance, and generic programming when implementing ADTs for data structures
• Create alternative representations of ADTs either from implementation or the standard libraries
• Apply recursion as a problem-solving technique.
• Determine appropriate ADTs and data structures for various sorting and searching algorithms
• Determine time and space requirements of common sorting and searching algorithms.