Course overview
This course provides an introduction to program development techniques with a focus on basic ideas of correctness and proof. The course introduces, among others, notions of complexity and analysis, recursion, abstract data types, representation of lists, stacks, queues, sets, trees and hash tables, graphs and Graph Traversal. The course allows students to experience different approaches to problem solving.
Course learning outcomes
- Skills in performing analysis of given recursive and iterative algorithms.
- Understanding and performing simple proofs of algorithmic complexity and correctness.
- An ability to understand and derive recurrences describing algorithms and properties of data structures.
- An understanding of the implementation and efficiency of a range of data structures including, trees, binary heaps, hash-tables and graphs.
- An understanding of a variety of well-known algorithms on some of the data structures presented.
- The ability to implement and use these algorithms in code.
- A foundational understanding of intractability.
- An understanding of proof techniques for NP-Completeness.
- Ability to solve new analytic and algorithmic problems.