# 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;

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++ Programming Review Encapsulation, Inheritance, Pointers, Polymorphism, Vectors. Mathematical Review Exponents, Logarithms, Series, Modular Arithmetic, Proofs. * 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)