This course offers an in-depth exploration of algorithms and data structures, focusing on design, analysis, and their applications in computer science. Students will learn to analyze the performance of algorithms, prove their correctness, and apply various algorithmic paradigms. Through rigorous study and hands-on practice, participants will develop the skills necessary to synthesize efficient algorithms in real-world engineering contexts.
Analyze the asymptotic performance of algorithms.
Write rigorous correctness proofs for algorithms.
Demonstrate familiarity with major algorithms and data structures.
Apply important algorithmic design paradigms and methods of analysis.
Synthesize efficient algorithms in common engineering design situations.
UNIT I: Introduction to Algorithm Design and Analysis
Asymptotic notations and their significance.
Introduction to the RAM model of computation.
Complexity analysis: worst-case and average-case scenarios.
Overview of algorithmic paradigms: divide and conquer, recursion, and greedy methods.
UNIT II: Data Structures and Sorting Algorithms
Searching algorithms: binary search trees, balanced trees (AVL, red-black), B-trees, skip lists, and hashing.
Priority queues and heaps, interval trees, tries, and order statistics.
Sorting algorithms: comparison-based (quick sort, heap sort, merge sort) and linear-time (radix sort, bucket sort, counting sort).
Decision tree model and lower bounds on sorting.
Introduction to string matching algorithms.
UNIT III: Advanced Graph Algorithms
Fundamental graph algorithms: BFS, DFS, connected components, topological sort, minimum spanning trees, and shortest paths.
Models of computation: the RAM model and logarithmic cost.
Advanced algorithmic paradigms: dynamic programming, branch and bound.
Advanced data structures: Fibonacci heap, union-find, and splay trees.
Introduction to amortized complexity analysis.
UNIT IV: Randomized Algorithms and Applications
Introduction to randomized algorithms as a technique.
Application areas in geometric algorithms: convex hulls, nearest neighbor search, Voronoi diagrams.
Algebraic and number-theoretic algorithms: Fast Fourier Transform (FFT), primality testing.
UNIT V: Optimization and NP-Completeness
Graph algorithms for network flows and matching.
Optimization techniques: linear programming.
Discussion of NP-completeness, including problems like satisfiability, clique, vertex cover, independent set, Hamiltonian cycle, TSP, knapsack, set cover, and bin packing.
Techniques: backtracking, branch and bound, and constant ratio approximation algorithms.
E. Horowitz, S. Sahni, and S. Rajsekaran, Fundamentals of Computer Algorithms, Galgotia Publications.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, PHI.
Sedgewick, Algorithms in C, Galgotia.
Paul Berman, Algorithms, Cengage Learning.
Richard Neopolitan, Kumar S.S. Naimipour, Foundations of Algorithms.
A basic understanding of programming and familiarity with fundamental concepts in computer science and mathematics.
Lectures, coding assignments, group projects, and examinations.