Data Structures and Algorithms for Engineers
Course Description  | 
Learning Objectives  | 
Lecture Notes  | 
Course Textbook  | 
Recommended Reading | 
Software | 
Useful Links
Course Description
The primary objective of the course is to provide engineers without formal training in computer science, a solid background in the key principles of computer science, in general, and of the algorithms and data-structures, in particular. The key purpose of this course is to complement the experience that engineers may already have in writing software with formal computer science underpinnings, making those engineers more capable in developing software intensive systems.
The course begins by considering the main phases of the software development lifecycle, from requirements elicitation, to computational modelling, system specification, software design, implementation, and software quality assurance, including various forms of testing, verification, and validation. Then, building on the concept of abstract data types, the course provides an in in-depth treatment of the key elements of algorithms and data-structures, beginning with the fundamentals of searching, sorting, lists, stacks, and queues, but quickly progressing to more advanced topics, including trees, graphs, and algorithmic strategies. It also covers the analysis of the performance and tractability of algorithms, finishing with automata theory and computability theory. A key focus of the course is on effective implementation and good design principles.
Learning Objectives
After completing this course, students should be able to:
- Recognize and analyze critical computational problems, generate alternative solutions to problems, and assess their relative merits.
- Understand, analyze, and characterize those factors that influence algorithmic computational performance and memory consumption.
- Design, implement, and document appropriate, effective, and efficient data structures & algorithms for a variety of real-world problems.
- Understand detailed software structures and their underlying strengths and weaknesses.
- Perform detailed, code-level design and document the design in an understandable way.
Lecture Notes
Module 1: Introduction
Lecture 1: Levels of abstraction. The software development life cycle. Formalisms for representing algorithms.
Module 2: Complexity of Algorithms
Lecture 1: Complexity Analysis.
Lecture 2: Complexity Theory.
Module 3: Searching and Sorting Algorithms:
Lecture 1: Linear and binary search. In-place sorts: bubblesort, selection sort, insertion sort.
Lecture 2: Not-in-place sorts: quicksort, mergesort. Characteristics of a good sort.
Module 4: Abstract Data Types
Lecture 1: Abstract Data Types (ADT). Information hiding. Types and typing. Design Goals. Design practices.
Module 5: Lists
Lecture 1: Containers. Dictionaries. List ADT: array implementation.
Lecture 2: List ADT: implementation with linked lists. Doubly linked lists and circular lists. Performance considerations.
Lecture 3: Stacks. Implementation using List ADT. Comparison of order of complexity. Stack applications.
Lecture 4: Queues. Implementation using List ADT. Comparison of order of complexity. Dedicated ADT. Circular queues. Queue applications.
Module 6: Trees
Lecture 1: Types of trees. Binary Tree ADT.
Lecture 2: Binary Search Tree.
Lecture 3: Height Balanced Trees: AVL Trees.
Lecture 4: Height Balanced Trees: Red-Black Trees.
Lecture 5: Optimal Code Trees. Huffman's Algorithm.
Lecture 6: Priority queues, binary heap, heapsort.
Module 7: Graphs
Lecture 1: Types of graph. Adjacency matrix representation. Adjacency list representation.
Lecture 2: Breadth-First Search (BFS) traversal & application of BFS.
Lecture 3: Depth-First Search (DFS) traversal & Topological Sort.
Lecture 4: Minimum Spanning Tree, Prim's algorithm, Kruskal's algorithm.
Lecture 5: Shortest Path Algorithms, Dijkstra's algorithm, Floyd's algorithm.
Module 8: Algorithmic Strategies
Lecture 1: Brute force, divide and conquer, greedy algorithms, dynamic programming, combinatorial search, backtracking, pruning, branch and bound
Module 9: Complex Networks
Lecture 1: The importance of complex networks and network science, review of graph theory.
Lecture 2: Communities (Part 1).
Lecture 3: Communities (Part 2).
Module 10: Hashing
Lecture 1: Dictionaries, hashing, hash functions, collision resolution, complexity, applications.
Module 11: Algorithm Correctness, ADT & OOP, and STL
Lecture 1: Types of software defects, formal verification, testing strategies, verification and validation strategies
(OOA, OOD, OOP, OOT, standard template library).
Course Textbook
Alfred V. Aho, Jeffrey D. Ullman, and John E. Hopcroft, Data Structures and Algorithms.
David Harel and Yishai Feldman, Algorithmics: The Spirit of Computing, Third Edition.
Recommended Reading
S. Skiena, The Algorithm Design Manual, 2nd Edition, Springer (2012). (a selection of examples will be taken from this book).
T. Cormen et al., Introduction to Algorithms, 3rd Edition, MIT Press (2009).
Software Development Environment
Click here for a step-by-step guide to downloading, installing, and using the software required to run examples and complete the assignments.
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.
David Vernon's Personal Website
|