Tue Jan 29

chap 2 - analysis & divide-and-conquer take 1

Discuss the homework due today. My answers are posted.

Finish our discussion of the chapter 2 material, including

• making plots
• O() notation
• logs
• exponentiation by squaring
• divide-and-conquer : recursively subdividing the problem to get log(n) rather than n behavior
• binary search

Any questions about any of this ?

chap 3 - data structures

Depending on time, we may start the chapter 3 material : data structures.

• First what's a "data structure" ? Check out for example wikipedia's definition

We want to distinguish between an "abstract data types" (i.e. API) vs its "data structure" implementation (i.e. code to make it happen).

When we're using one for some algorithm or other, we just needs its API and a knowledge of its O() and storage behavior. When we're trying to understand what it is and how it works, then we'll want to look at the implementation.

Chapter 3 gives an overview of the most common data structures, the basic ideas and their advantages and disadvantages, without going into the full implementation details.

The ones we'll discuss

• array : a[i] where i is 0,1,2,3,... - contiguous storage (implementation)
• linked list : a0 -> a1 -> a2 -> a3 -> null - pointers (implementation)
• stack : push, pop ; last in is first out (API)
• queue : push, pop ; first in is first out (API)
• dictionary : key => value API
• hash table : a common implementation of a dictionary <== tricky and important
• binary search tree (implmentation)
• balanced search trees (implementation)
• priority queue (API)
• heap (implementation - common way to make a priority queue)

related topics

• "hashing" : turning a key (usually a string) into a number (often an index into an array)

specialized data structures (which we'll mostly just wave our hands at)

• strings
• geometric data
• sets
• ...

I gave an example of a linked list in python - see the attached code.

attachments

		last modified	size
	node.py	Tue Dec 03 2024 05:21 pm	484B