Skip to content

Latest commit

 

History

History
55 lines (43 loc) · 2.46 KB

20150106.md

File metadata and controls

55 lines (43 loc) · 2.46 KB
Raw

CS 240 Enriched

Data Structures and Data Management

1/6/2015

Elvin Yung

Instructor: Alex Lopez-Ortiz

The objective of this course is the cover the same material as the regular sections, but with more material. This means that the pace of the course will be faster.

  • Tutorial: Monday 3:30 PM - 4:30 PM, MC 4064
  • Textbook: Robert Sedgewick, Introduction to Algorithms in C++

What is computer science?

You have some information. You want to

  • store it - use data structures.
  • process it - use algorithms.
  • trasmit it - use networking.
  • display it - use graphics.
  • secure it - use cryptography.
  • collect it - use sensor networks.
  • learn from it - use machine learning or data mining.

The more data you have, the more important the information structure is.

Course Topics

  • Priority queues, heaps, treaps
  • Sorting, selection
  • Binary search trees, AVL trees, B-trees, cache oblivious B-trees
  • Rank/select (succinct data structures), Van Emde Boas trees
  • Skip lists
  • Hashing, cuckoo hashing, bloom filters, MapReduce(/Hadoop)
  • Quad trees, k-d trees, range trees, R-trees
  • Tries
  • String matching, suffix trees, suffix arrays
  • Data compression, Huffman coding, LZW, Burrows-Wheeler, arithmetic compression, compressed sensing

Algorithms & Data Structures

  • The basic problem: Given an input, carry out a particular computation task.

  • The input is known as the problem instance.

  • The output is known as the problem solution.

  • The goal is to find an efficient way to compute the solution.

  • An algorithm is a step-by-step process to compute a problem solution, given a problem instance I. The algorithm solves the problem if for every instance it finds a valid solution.

  • If it doesn't work all the time, it's called a heuristic.

  • A program is an implementation of an algorithm using a particular computer language.

Efficiency of solution

  • Running time
  • Space usage

For a given problem we have a choice of algorithms that solve the problem. The goal of algorithm design is to devise algorithms that solve a problem, and the goal of algorithm analysis is to study the efficiency of a proposed solution. Algorithm design will be covered in CS341, and we will study algorithm analysis in this course. Specifically, we will focus on algorithms that utilize storage, where the complexity comes from handling data.

Observation

There is in general an observed correlation between the size of the input and the difficulty of the problem.