AlgoGPT
Log In

SC1007 Data Structures and Algorithms

Pre-requisite: SC1003 Introduction to Computational Thinking and Programming

Course Aims

This course aims to (i) teach the concepts, implementations and applications of data structures such as arrays, linked lists, stacks, queues and trees that are important for building efficient algorithms; (ii) provide an introduction to algorithm analysis and design. These are essential for future computer science and computer engineering courses.

Intended Learning Outcomes (ILO)

By the end of this course, the student would be able to:

  1. 1Select appropriate data structures such as arrays, linked lists, stacks, queues and trees and implement algorithms to solve real world problems using these data structures in Python.
  2. 2Conduct complexity analysis of simple algorithms.
  3. 3Select and implement appropriate search algorithm (sequential search, binary search, search using hash tables) as part of a problem solution in Python. Compare the efficiencies of these search algorithms.
  4. 4Select and implement appropriate graph traversal algorithm (DFS, BFS) as part of a problem solution in Python. Analyse the complexities of these graph traversal algorithms.

Course Content

1. Introduction & Dynamic Memory Allocation

Static vs dynamic memory allocation. 'Heap' management and 'garbage collection'. Run-time memory protection. Overview of node-based data structures.

2. Linked Lists

Linked List structures, doubly linked lists, circular lists. Their implementations in Python and examples that use lists.

3. Abstract Data Types and Their Implementation

Stacks, queues, priority queues. Their implementations using linked lists. Use of stacks to evaluate arithmetic expressions and use of queues, priority queues to schedule jobs.

4. Tree Structures

Overview of hierarchical/non-linear data structures. Tree structures and their implementations. Binary vs general trees. Tree traversal: pre-order, in-order, post-order. Expression trees: representation and evaluation. AVL trees and their balancing.

5. Introduction to Algorithms

What is an algorithm? Important problem types in computing. Algorithm design strategies.

6. Analysis of Algorithms

Time and space complexities of algorithms. Analyzing basic program constructs. Best case, worst case and average case time complexity analysis. Deducing recurrence relations for time complexity of recursive algorithms. Solving elementary recurrence relations. Asymptotic time complexity analysis. Big-Oh, big-Omega, and big-Theta notations. Common Complexity Classes. Basic techniques for proving asymptotic bounds. Space Complexity.

7. Searching

General exhaustive search. Iterative and recursive sequential search algorithms. Binary search, its invariance, and complexity. Open and closed address hashing using linear probing and double hashing collision resolution techniques. All algorithms covered are accompanied by asymptotic complexity analysis.

8. Graph Representations and Searching

Basic graph representation methods, adjacency lists, and adjacency matrix. Systematic graph traversals with breadth-first search (BFS) and depth-first search (DFS) algorithms. A generic backtracking algorithm and its complexity. Eight-queen, Maze-Search.