Algorithms and Data Structures
Prof. David Vernon
School of Informatics
University of Skövde
Sweden
davidvernon.eu
Course Outline 
Lecture Notes 
Recommended Reading 
Useful Links
Course Outline
This course provides an intensive treatment of most of the key elements of algorithms and datastructures, beginning with the fundamentals of searching, sorting, lists, stacks, and queues, but quickly building to cover more advanced topics, including trees, graphs, and algorithmic strategies. It also covers the analysis of the performance and tractability of algorithms and will build on the concept of Abstract Data Types. A key focus of the course is on effective implementation and good design principles.
Topics covered include the following.
 Analysis of complexity: performance of algorithms, time and space tradeoff, worst case and average case performance, Big O notation, recurrence relationships, analysis of complexity of iterative and recursive algorithms.
 Complexity theory: tractable and intractable algorithmic complexity, travelling salesman problem, Hamiltonian circuit, 3colour problem, SAT, cliques, determinism and nondeterminism, P, NP, and NPComplete classes of algorithm.
 Simple searching algorithms: linear search; binary search (iterative and recursive)
 Simple sorting algorithms: bubblesort, selection sort, Quicksort, worst case and average case complexity.
 Containers, dictionaries, Abstract Data Types (ADTs), lists, stacks, and queues, ADT specification, array and linkedlist implementations; hashing.
 Trees: types of trees, tree terminology (level, height, external and internal nodes, skinny, fat, complete, leftcomplete, perfect, multiway, dary), binary trees, binary tree operations, binary tree representation, binary search trees, binary search tree implementation, depthfirst traversals, expression trees, preorder, inorder, postorder traversal, fixedlength codes, variable length codes, optimal code trees, Huffman's algorithm and implementation, heightbalanced trees, balance factor, AVL Trees, RR, RL, LR, LL rotations, RedBlack Trees, single promotion, zigzag promotion, recolouring and restructuring.
 Priority queues, binary heaps, array implementation, heapsort.
 Graphs, types of graphs (directed, undirected, weighted, unweighted, cyclic, acyclic, directed acyclic, simple, nonsimple, implicit, explicit, embedded, topological), adjacency list representation, adjacency matrix representation, depthfirst traversal, breadthfirst traversal, finding paths, topological sorting, minimum spanning trees, Prim's algorithm, Kruskal's algorithm, shortestpath algorithms, Dijkstra's algorithm, FloydWarshall's allpairs algorithm.
 Algorithmic strategies: bruteforce (Grenander's problem), divideandconquer (Quicksort, mergesort, Grenander's problem), greedy algorithms (Prim's algorithm, Dijkstra's algorithm, Huffman's algorithm, knapsack problem), dynamic programing (Fibonnaci number).
 Combinatorial search: exhaustive search and backtracking, pruning, generic algorithm implementation, enumeration of subsets, permutations, all paths in a graph, branchandbound.
Back to Top
Lecture Notes
Slide Format
Lecture 1: Introduction and Course Overview
Lecture 2: Complexity 1  Analysis of Complexity
Lecture 3: Complexity 2  Complexity Theory
Lecture 4: Searching Sorting
Lecture 5: Containers & Dictionaries 1  ADT Lists
Lecture 6: Containers & Dictionaries 2  Stack Queue Hashing
Lecture 7: Trees 1  Binary Tree ADT
Lecture 8: Trees 2  Binary Search Tree
Lecture 9: Trees 2  Optimal Code Trees
Lecture 10: Trees 3  HeightBalanced Trees
Lecture 11: Priority Queues Heaps
Lecture 12: Graphs 1  BFS DFS Toplogical Sort
Lecture 13: Graphs 2  Minimum Spanning Tree
Lecture 14: Graphs 3  Shortest Path
Lecture 15: Algorithmic Strategies 1  D&Q Greedy
Lecture 16: Algorithmic Strategies 2  Backtracking
Handout Format
Lecture 1: Introduction and Course Overview
Lecture 2: Complexity 1  Analysis of Complexity
Lecture 3: Complexity 2  Complexity Theory
Lecture 4: Searching Sorting
Lecture 5: Containers & Dictionaries 1  ADT Lists
Lecture 6: Containers & Dictionaries 2  Stack Queue Hashing
Lecture 7: Trees 1  Binary Tree ADT
Lecture 8: Trees 2  Binary Search Tree
Lecture 9: Trees 2  Optimal Code Trees
Lecture 10: Trees 3  HeightBalanced Trees
Lecture 11: Priority Queues Heaps
Lecture 12: Graphs 1  BFS DFS Toplogical Sort
Lecture 13: Graphs 2  Minimum Spanning Tree
Lecture 14: Graphs 3  Shortest Path
Lecture 15: Algorithmic Strategies 1  D&Q Greedy
Lecture 16: Algorithmic Strategies 2  Backtracking
Back to Top
Recommended Reading
S. Skiena, The Algorithm Design Manual, 2nd Edition, Springer (2012).
T. Cormen et al., Introduction to Algorithms, 3rd Edition, MIT Press (2009).
Back to Top
Useful Links
Algorist.com
This is Steven Skiena's website with lots of resources related to his book, The Algorithm Design Manual, including teaching material and sample programs.
Please refer to my wiki for links to other related resources and support material.
Back to Top
David Vernon's Personal Website
