Algorithm Analysis and Data Structures
(i) Short introduction to data bases and data base management systems. Relational DB and SQL. (ii) Storing methods, insertion, deletion and querying Data Bases. Ordered files, arrays, pointers, hashing, B trees and B+ trees (review). (iii) Problems and tradeoffs in big data sets in creating, updating and searching a DB. Input/output models, memory hierarchy, the Disk Access Model (DAM). Examples. (iv) Disk sorting algorithms. Merge Sort. Analysis. Divide and conquer. The DAM model, applications. Cache oblivious and non-oblivious algorithms. (v) Examples, models, analysis. Insertion/searching tradeoffs. Appropriate data structures. (vi) Application matters. Performance. (vii) Introduction/overview in data mining. Introduction to machine learning. (viii) Programming techniques for big data. MapReduce, Hadoop. Physical organization. Some algorithms on the model. (ix) Representation, LSH for texts. Distance measures. (x) The model. Sampling in runs. Data filtering. Estimation. (xi) Link analysis.