School of Engineering and Technology, (SET)
 
AT70.02 : Data Structures & Algorithms  3(3-0)
 
Course objectives:

An algorithm describes how to carry out a problem-solving task implementable by computer programs. The design of an algorithm is tightly coupled with how information to be manipulated by it is organized i.e. data structuring. A course in Algorithm and Data Structure is therefore fundamental to a study in Computer Science.
 
Learning Outcomes:

Fundamentals, Randomized Algorithms, Sorting, Hashing, Balanced Search Trees, Advanced Design Techniques, Graph Algorithms, Polynomials and the FFT, String Matching, Geometric Algorithms.
 
Pre-requisite(s):

None
 
Course Outline:
I.        Foundations
1.     Asymptotic Analysis
2.     Recursion and Recurrences

II.      Randomized Algorithms
1.     Indicator Variables
2.     Probabilistic Analysis

III.     Sorting
1.     Quicksort
2.     Sorting in Linear Time
3.     Order Statistics

IV.     Hashing
1.     Hash Tables
2.     Hash Functions
3.     Universal Hashing
4.     Perfect Hashing

V.      Balanced Search Trees
1.     Red-black Trees
2.     B-Trees
VI.     Advanced Design Techniques
1.     Dynamic Programming
2.     Greedy Algorithms

VII.   Graph Algorithms
1.     Shortest Paths
2.     Maximum Flow
 
VIII. Polynomials and the FFT
1.     DFT and FFT
2.     Efficient FFT Implementation

IX.     String Matching
1.     Rabin-Karp Algorithm
2.     String Matching with Finite Automata
3.     Knuth-Morris-Pratt Algorithm

X.      Geometric Algorithms
1.     Segment Intersection Algorithms
2.     Convex Hull Algorithms


 
 
Learning Resources:

Textbook:
Data Structures and Algorithm Analysis in C++, 3rd Ed. by Weiss. Addison Wesley.
 
 
 
 
 
Evaluation Scheme:
Exams                                                                  - 60%
Homework and Programming Assignments  - 40%
 
Instructor(s):
SECTION NAME