Course Description:

In our everyday life, we (perhaps, unknowingly) encounter problems involving taking input and returning output that satisfies some (possibly optimization) objective. For example, finding the cheapest priced product among hundreds or thousands of identical products (e.g., cars or tablets) online (e.g., cars or eBay), finding a matching sequence of two nucleotide sequences, or finding the shortest path/route (among all of the possible paths) to go from a given location to a given destination (e.g., home to campus). 

Off-the-shelf computational tools have made our life much more convenient. Many of these above problems can be solved at your fingertips (e.g., sorting from the lowest to highest prices or using google maps to obtain the quickest route) effortlessly. For many of these problems, solving them would not have been possible without the help of carefully designed algorithms (and possibly the appropriate data structures).

What is an algorithm? What is the central role of data structures in algorithmic designs? How can we leverage data structures to solve problems more efficiently? 

In this class, we will embark on a journey to understand the interplay between algorithms and data structures as well as obtain fundamental background and knowledge in various algorithmic techniques for solving (real-world) problems. In particular, the class will start by reviewing algorithm analysis, asymptotic notation, and solving recurrence relations. We will then discuss some advanced data structures and their associated algorithms, heaps, priority queues, hash tables, trees, binary search trees, and graphs. Some algorithmic techniques such as divide and conquer, transform and conquer, space-time trade-offs, greedy algorithms, dynamic programming, randomization, and distributed algorithms will be covered in this course (subject to the discretion of the instructor). Finally, the class will provide a basic introduction to computability and NP-completeness to discuss the limitation of computational power. 

Topics: 

Techniques: 

Complexity Notations, Summation, Induction, and Recursion Brute Force and Exhaustive Search Divide and Conquer Greedy Iterative Improvement Dynamic Programming Reductions Approximation Algorithms 

Data Structures: 

Binary Trees Balanced Binary Trees AVL Trees B-Trees Hashing Graphs Heaps 

Problems: 

Sorting and Searching Closest-Pair (Points) Convex-Hull (Points) Traversal and Shortest Paths on Graphs Topological Sort on Graphs Matrix Multiplication Linear Programming Maximum-Flow Knapsack String Matching TSP Vertex Cover Maximum Subgraph Set cover Maximum Matching in Bipartite Graph Stable Marriage