ICS220 – Data Structures and Algorithms

Welcome to Data Structures & Algorithms

Instructor: Dr. Ken Cosh

Schedule: Tu/Th 8:30-10:00

Course Description:

An understanding of data structures and algorithm analysis will be presented in the following topics: stacks queues, recursion, linked lists, trees, graphs, sorting and searching.  This will serve as the basis for further studies in information systems and approaches using an application perspective.  Case Studies are required.

Course Objectives:

1 Perform complexity analysis of algorithms using Big-O notation.

2 Use and understand the following data structures;

Linked Lists

Stacks and Queues

Binary and Multiway Trees

Graphs

3 Understand and use recursion in conjunction with recursive data structures.

4 Analyse and use different sorting algorithms such as shell sort, quick sort and heap sort.

5 Understand what hashing means and create good hash functions.

6 Understand what data compression is and use some common algorithms to perform compression.

7 Understand what garbage collection is.

Syllabus

References:

1 (Compulsary) Adam Drozdek, 3rd edition, Data Structures and Algorithms in C++, Thomson Course Technology, 2005. ISBN: 0-534-49182-0

Materials:

Week Content Exercise Hours(Lect/Lab)
1 Object Oriented Programming Using C++

* Case: Random Access File 3 (3-0)
2 Complexity Analysis

  • Computational and Asymptotic Complexity
  • Big-O Notation
  • Properties of Big-O Notation
  • Amortised Complexity
  • NP-Completeness
3 (3-0)
3 Linked Lists

  • Singly Linked Lists
  • Doubly Linked Lists
  • Circular Linked Lists
  • Skip Lists
  • Self Organising Lists
  • Sparse Tables
*Case: A Library 3 (3-0)
4 Stacks and Queues

  • Stacks
  • Queues
  • Priority Queues
Case: Exiting a Maze 3 (3-0)
5 Recursion

  • Recursive Definitions
  • Function Calls and Recursive Implementations
  • Anatomy of a Recursive Call
  • Tail Recursion
  • Non-tail Recursion
  • Indirect Recursion
  • Nested Recursion
  • Excessive Recursion
Case: A Recursive Descent Interpreter 3 (3-0)
6 Binary Trees

  • Trees, Binary Trees and Search Trees
  • Implementing Binary Trees
  • Searching Binary Trees
  • Tree Traversal
  • Insertion
  • Deletion
  • Balancing a Tree
  • Self-Adjusting Trees
  • Heaps
Case: Computing Word Frequencies 3 (3-0)
7 Multiway Trees

  • The family of B-Trees
    • B-Trees, B*-Trees, B+-Trees, Prefix B+-Trees, Bit-Trees.
  • Tries
Case: Spell Checker 3 (3-0)
8-9 Graphs

  • Graph Representation
  • Graph Traversals
  • Shortest Paths
  • Cycle Detection
  • Spanning Trees
  • Connectivity
  • Topological Sort
  • Networks
  • Matching
  • Eulerian and Hamiltonian Graphs
  • NP-Complete Problems in Graph Theory
Case: Distinct Representatives 6 (6-0)
10 Sorting

  • Elementary Sorting Algorithms
  • Decision Trees
  • Efficient Sorting Algorithms
Case: Adding Polynomials 3 (3-0)
11 Hashing

  • Hash Functions
  • Collision Resolution
  • Deletion
  • Perfect Hash Functions
Case: Hashing with Buckets 3 (3-0)
12 Data Compression

  • Conditions for Data Compression
  • Huffman Coding
  • Run-Length Encoding
Case: Huffman Method with Run-Length Encoding 3 (3-0)
13 Memory Management

  • Sequential Fit Methods
  • Non-Sequential Fit Methods
  • Garbage Collection
Case: An in Place Garbage Collector 3 (3-0)
14 String Matching

  • Exact String Matching
  • Approximate String Matching
Case: Longest Common Substring 3 (3-0)
15 Review 3 (3-0)