Summary

This chapter focused on the fundamentals of programming and randomized algorithms. The chapter built on the programming concepts of dynamic programming, and presented the difference between dynamic programming and recursion. The DAGs was also introduced in this chapter, and how it can be used to set up dynamic programming was discussed. Two popular examples of the knapsack problem and two APSP were covered in this chapter, and their solutions using dynamic programming were presented. Randomized algorithms, Las Vegas and Monte Carlo, were introduced with their application in determining max value using randomization. This chapter also introduced skip lists and the extension to randomized skip lists. The probabilistic analysis of skip list was covered for major operations and data storage. The next chapter will introduce functional algorithms concepts. Functional algorithms provide the ability to write clean and clear code by eliminating state during runtime so that output is always...