teaching machines

CS 245 Lecture 28 – Review

May 8, 2014 by Chris Johnson. Filed under cs245, lectures, spring 2014.

Agenda

• what ?s
• review

Topics

• hashing
• maps
• linked structures vs. array structures
• trees
• binary search trees
• heaps and priority queues
• stacks
• queues

When Will I Use This Stuff?

All the time, none of the time, or some of the time. Check out http://programmers.stackexchange.com/questions/102041/why-are-data-structures-so-important-in-interviews.

Donald Knuth, in Structured Programming with Goto Statements:

Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified. It is often a mistake to make a priori judgments about what parts of a program are really critical, since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail.

What is the value of an education?

Haiku