This course is part of the Computer Science Essentials for Software Development Professional program.
This course, part of the CS Essentials for Software Development Professional Certificate program, takes an abstract, conceptual approach to the task of writing sophisticated, but efficient programs for complex computational tasks. When confronted with a computational problem, you will learn to model it abstractly and then design and analyze an algorithm to solve it. Critically, the course will focus on the correctness and efficiency of software by examining the mathematical underpinnings of the design and analysis of algorithms.
Continuing from SD2x, you will deepen your understanding of the design and analysis of data structures for specific types of access to data. You will also learn new data structures and understand how to choose the best data structure for a specific problem.
Picking the right data structure goes hand in hand with designing the right algorithm to solve a problem. In this course you will develop a general toolkit of algorithm design paradigms that will equip you to tackle new computational problems. Choosing the right type of algorithm and designing such an algorithm is an art, for which you will get a flavor.
Some of the most important computational problems are problems on graphs. These will be the major focus of the second half of the course, where you will learn to design algorithms for foundational problems on graphs, prove that these algorithms are correct, and analyze their running times.
While the main focus of the course is on designing correct and efficient algorithms, you will learn that not all problems have such algorithms. By understanding the beautiful theory of NP-completeness, you will learn to recognize problems that are unlikely to have efficient algorithms, and think about alternatives to solving these problems exactly. You will learn about reductions, which play a key role in this theory, and see that reductions can also be useful in the design of algorithms.
Prerequisites:
Understanding of basic data structures and Java programming Introductory discrete mathematics including an understanding of proofs Course Outline:
-
Week 1 - Algorithm design techniques – incremental and divide-and-conquer algorithms. Sorting and selection algorithms. Analysis of data structures – hash tables, heaps, and binary search trees.
-
Week 2 - Algorithm design paradigms – Dynamic programming and greedy algorithms.
-
Week 3 - Graphs and algorithms on graphs – graph traversals (depth-first and breadth-first search) and minimum spanning trees (Kruskal’s and Prim’s algorithms).
-
Week 4 - Shortest path algorithms (Dijkstra’s and Floyd-Warshall’s algorithms) and NP-completeness.