Algorithms and data structures Lecture Notes by The University of Waterloo

This is a collection of lecture notes in power-point slide format which presenting a course in algorithms and data structures. Following are the topics covered in this Lecture material.

    Introduction and review
    Algorithm analysis
    List, stacks and queues
    Trees and hierarchical orders
    Ordered trees
    Search trees
    Priority queues
    Sorting algorithms
    Hash functions and hash tables
    Equivalence relations and disjoint sets
    Graph algorithms
    Algorithm design
    Theory of computation
    Other topics
    Concluding remarks

Read Online/Download

Purely Functional Data Structures By Carnegie Mellon University and written by Chris Okasaki

Purely Functional Data Structures is a PDF book released By Carnegie Mellon University and written by Chris Okasaki. This book consists of functional programming, data structures, lazy evaluation, amortization,  Eliminating Amortization, Lazy Rebuilding, Numerical Representations, Data-Structural Bootstrapping, Implicit Recursive Slowdown, etc

In this book author describe several techniques for designing functional data structures, and numerous original data structures based on these techniques,including  multiple variations of  lists,  queues,  double-ended queues,  and  heaps, many supporting more exotic features such as random access or efficient catenation.

Read Online/Download

Advanced Data Structures By The Institute of Mathematical Sciences (IMSc), India

This Pdf book is about advanced data structures and is published by The Institute of Mathematical Sciences (IMSc), India. It covers the following topics: 

Self adjusting data structures, amortized analysis, self adjusting lists, Splay trees, their performance and related conjectures, Hashing, FKS perfect hashing, Cuckoo hasing, dynamic perfect hashing, Fusion Trees, Fully dynamic connectivity in polylogarithmic time, Dynamic all pairs shortest paths, Linear time construction of Suffix trees and arrays, Succinct Data Structures, etc.

Data  structures  play  a  central  role  in  modern  computer  science.   In  a  typical  data  structureproblem, one is interested in storing some data to support fast queries and/or updates using littlespace.  The course will cover recent developments in the subareas including, but not limited to,

1. self adjusting data structures (these are structures that store no balance information, are easy to implement, but harder to analyze)
2. hashing
3. succinct data structures
4. data structures optimized for external memory and cache-oblivious data structures
5. data structures for dynamic graph problems

Read Online/Download

Electronic Lecture Notes on Data Structures and Algorithms By Ernet India Education & Research Network

This Lecture note is written by Y. Narahari, Indian Institute of Science, Bangalore and is published by Ernet India Education & Research Network.

The Lecture Notes is organized into eleven chapters. Besides the subject matter, each chapter includes a list of problems and a list of programming projects. Also, each chapter concludes with a list of references for further reading and exploration of the subject.

1.Introduction
2.Lists
3.Dictionaries
4.Binary Trees
5.Balanced Trees
6.Priority Queues
7.Directed Graphs
8.Undirected Graphs
9.Sorting Methods
10.NP-Completeness
11.References

Read online/Download

Design and Analysis of Algorithms: Course Notes Prepared by Samir Khuller of University of Maryland

This book covers core material in data structures and algorithm design, and also helps students prepare for research in the field of algorithms. Topics covered includes: Splay Trees, Amortized Time for Splay Trees, Maintaining Disjoint Sets, Binomial heaps, F-heap, Minimum Spanning Trees, Fredman-Tarjan MST Algorithm, Light Approximate Shortest Path Trees, Matchings, Hopcroft-Karp Matching, Linear Programming, Two processor scheduling, Network Flow, Graph Colouring, Planar Graphs, Min Mean Cycle Problem,Vertex Cover, Weighted Vertex Cover, etc and more.

Read Online/Download

Design and Analysis of Algorithms By Massachusetts Institute of Technology

Design and Analysis of Algorithms By Massachusetts Institute of Technology is an intermediate algorithm course which teaches various techniques to design and analysis of algorithms.

Various topics included in this lecture Notes are

1. Overview, Interval Scheduling (PDF)    
2. Divide & Conquer: Convex Hull, Median Finding (PDF)    
3. Divide & Conquer: FFT (PDF)    
4. Divide & Conquer: Van Emde Boas Trees (PDF)    
5. Amortization: Amortized Analysis (PDF)    
6. Randomization: Matrix Multiply, Quicksort (PDF)    
7. Randomization: Skip Lists (PDF)    
8. Randomization: Universal & Perfect Hashing (PDF)    
9. Augmentation: Range Trees (PDF)    
10. Dynamic Programming: Advanced DP (PDF)    
11. Dynamic Programming: All-pairs Shortest Paths (PDF)
12. Greedy Algorithms: Minimum Spanning Tree (PDF)    
13. Incremental Improvement: Max Flow, Min Cut (PDF)    
14. Incremental Improvement: Matching (PDF) Baseball Elimination Notes (PDF)
15. Linear Programming: LP, Reductions, Simplex (PDF)    
16. Complexity: P, NP, NP-completeness, Reductions (PDF)     )
17. Complexity: Approximation Algorithms (PDF)    
18. Complexity: Fixed-parameter Algorithms (PDF)    
19. Synchronous Distributed Algorithms: Symmetry-breaking. Shortest-paths Spanning Trees (PDF)
20. Asynchronous Distributed Algorithms: Shortest-paths Spanning Trees (PDF)    
21. Cryptography: Hash Functions (PDF)    
22. Cryptography: Encryption (PDF)    
23. Cache-oblivious Algorithms: Medians & Matrices (PDF)    
24. Cache-oblivious Algorithms: Searching & Sorting (PDF)    

Read Online/Download

Introduction to Algorithms By University of Washington

This Lecture note is about Introduction to Algorithms and is written by Shayan Oveis Gharan. Various topics covered in this note are Stable Matchings, Algrithm Design by Induction, Graphs, Trees or BFS, Connected Comps/Bipartite Graphs, DFS or Topological Ordering, Interval Scheduling, Interval Partitioning, MST, MST, Union find, Closest Points, Master Theorem, Integer Multiplication, Median, Vertex Cover or Set Cover, Network Connectivity, Image Segmentation, Reductions, NP-Completeness, Network Flow, Max Flow-Min Cut, Bipartite Matching, Linear Programming, etc.

Read Online/Download

Introduction to Algorithms By Johns Hopkins University

Johns Hopkins University published well defined Lecture Notes focuses mainly on the design of various algorithms and analysis of their efficiency.  Topics covered includes: the basic definitions of algorithmic complexity, basic tools such as dynamic programming, sorting, searching, and selection; advanced data structures and their applications, graph algorithms and searching techniques such as minimum spanning trees, depth-first search, shortest paths, Online Algorithms, Machine learning Theories, Algorithmic Game Theory, etc.

Read Online/Download

Approximation Algorithms By The University of Wisconsin Madison

The field of approximation algorithms has developed in response to the difficulty in solving a good many optimization problems exactly. In the case of NP-hard problems, we sacrifice optimality in the favor of efficient heuristics that give nearly-optimal (approximate) solutions, and aim for provable guarantees on the performance of these algorithms. This course will present some general techniques (such as convex programming-based approaches, randomness and metric methods) that underly these algorithms. The following is a selection of the techniques and problems that we will cover:

Techniques: greedy algos, local search, randomized methods, LP techniques, primal-dual method, lagrangean methods, semi-definite programming, metric methods, inapproximability.

Problems: Set cover. Vertex cover. TSP & other planning problems. Scheduling. Facility location. Steiner tree and other network design problems. Sparsest cut, multicut and other partitioning problems. MaxSAT. Generalized assignment problems. Graph coloring. Approximate counting.

1. Online optimization algorithms [PDF] by Dave Andrzejewski
2. Bounds on alphabet size and rate for network coding [PDF] by Siddharth Barman
3. Network coding [PDF] by Matt Elder
4. Stochastic optimization [PDF] by Chi Man Li

Read Online/Download

Advanced Algorithms By University of Wisconsin-Madison

This lecture note by Shuchi Chawla teaches students about various techniques to design and analysis of various algorithms such as Greedy algorithms, Dynamic programming, Network flow applications, matchings, Randomized algorithms, Karger's min-cut algorithm, NP-completeness, Linear programming, LP duality, Primal-dual algorithms, Semi-definite Programming, MB, etc.

Read Online/Download

Distributed Algorithms Lecture Notes By Massachusetts Institute of Technology

Distributed Algorithms Lecture Notes
Distributed Algorithms are Algorithms that are supposed to work in distributed networks, or on multiprocessors.
Topics Covered 
1 Course overview. Synchronous networks. Leader election in synchronous ring networks. (PDF) 2 Leader election in rings. Basic computational tasks in general synchronous networks: leader election. Breadth-first search. Broadcast and convergecast. Shortest paths. (PDF) 3 Spanning trees. Minimum spanning trees. (PDF) 4 Fault-tolerant consensus. Link failures: the two generals problem. Process failures (stopping, Byzantine). Algorithms for agreement with stopping and Byzantine failures. Exponential information gathering. (PDF) 5 Number-of-processor bounds for Byzantine agreement. Weak Byzantine agreement. Time bounds for consensus problems. (PDF) 6 k-set-agreement. Approximate agreement. Distributed commit. (PDF) 7 Asynchronous distributed computing. Formal modeling of asynchronous systems using interacting state machines (I/O automata). Proving correctness of distributed algorithms. (PDF) 8 Non-fault-tolerant algorithms for asynchronous networks. Leader election, breadth-first search, shortest paths, broadcast and convergecast. (PDF) 9 Spanning trees. Gallager et al. minimum spanning trees. (PDF) 10 Synchronizers. Synchronizer applications. Synchronous vs. asynchronous distributed systems. (PDF) 11 Time, clocks, and the ordering of events. State-machine simulation. Vector timestamps. (PDF) 12 Stable property detection. Distributed termination. Global snapshots. Deadlock detection. (PDF) 13 Asynchronous shared-memory systems. The mutual exclusion problem. Mutual exclusion algorithms. (PDF) 14 More mutual exclusion algorithms. Bounds on shared memory for mutual exclusion. Resource allocation. The Dining Philosophers problem. (PDF) 15 Shared-memory multiprocessors. Contention, caching, locality. Practical mutual exclusion algorithms. Reading/writing locks. (PDF) 16 Impossibility of consensus in asynchronous, fault-prone, shared-memory systems. (PDF) 17 Atomic objects (PDF) 18 Atomic snapshot algorithms. Atomic read/write register algorithms. (PDF) 19 List algorithms: locking algorithms, optimistic algorithms, lock-free algorithms, lazy algorithms. (PDF) 20 Transactional memory: obstruction-free and lock-based implementations. (PDF) 21 Wait-free computability. The wait-free consensus hierarchy. (PDF) 22 Wait-free vs. f-fault-tolerant atomic objects. Boosting fault-tolerance. (PDF) 23 Asynchronous network model vs. asynchronous shared-memory model. Impossibility of consensus in asynchronous networks. Failure detectors and consensus. Paxos consensus algorithm. (PDF) 24 Self-stabilizing algorithms (PDF) 25 Timing-based systems. Modeling and verification. Timing-based algorithms for mutual exclusion and consensus. Clock synchronization.
Read Online or Download