DSCI 512: Algorithms and Data Structures
How to choose and use appropriate algorithms and data structures to help solve data science problems. Key concepts such as recursion and algorithmic complexity (e.g., efficiency, scalability).
|1||Exploring data structures: list, sets, dictionaries, arrays, multidimensional arrays, nested dictionaries, and more|
|2||Time complexity, big O, space complexity|
|3||Linear search, binary search, trees|
|5||Introduction to graphs (directed and undirected), graph searches|
|6||More graphs, graph representations|
|8||Writing efficient code|
Course Learning Objectives
By the end of the course, students are expected to be able to:
- Apply fundamental algorithms such as sorting and searching, including iterative and recursive algorithms, using lists.
- Select and justify the use of elementary data structures such as arrays, hash tables, trees, and simple graphs.
- Analyze the scalability and trade-offs of various basic algorithms and data structures, using Big-O notation.
- Explain why using a different (better) algorithm for a problem can result in a much, much bigger performance improvement than tweaking the algorithm already being used.
- Apply basic discrete optimization methods such as dynamic programming.
Online reference material
- Visualizing Algorithms
- Algorithms to Live By
- 500 Data Structures and Algorithms practice problems and their solutions
- Recursion practice problems
- P vs. NP and the Computational Complexity Zoo (video)
- Michael Goodrich and Roberto Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, Inc. ISBN: 0-471-38365-1
- Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani, Algorithms, McGraw Hill Book Company, 2008, ISBN 0-07-352340-2, also available here.
- John Kleinberg and Eva Tardos, Algorithm Design, Addison-Wesley Publishing company, 2005, ISBN 0-321-29535-8.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, 3rd edition, MIT Press, 2009, ISBN 0-262-03384-4.
- Donald E. Knuth, The Art of Computer Programming, Volume 1, Third edition: Fundamental Algorithms, Addison-Wesley Publishing company, 1997, ISBN 0-201-89683-4.
- Donald E. Knuth, The Art of Computer Programming, Volume 2, Third edition: Seminumerical Algorithms, Addison-Wesley Publishing company, 1998, ISBN 0-201-89684-2.
- Donald E. Knuth, The Art of Computer Programming, Volume 3, Second edition: Sorting and Searching, Addison-Wesley Publishing company, 1998, ISBN 0-201-89685-0.
- Donald E. Knuth, The Art of Computer Programming, Volume 4a: Combinatorial Algorithms, Part 1, Addison-Wesley Publishing company, 2011, ISBN 0-201-03804-8.