Hari: 1 Maret 2012

Teaching data structures
• adjacency matrix, adjacency list
• Degree of all vertices, connected component, checking connectivity
• Breadth-first search
• Shortest path
• Topological sort
• All shortest paths from a vertex
• Spanning trees: Kruskal, Prim
• Cycle detection: union-find
• Numerical algorithms: GCD, exponentiation, integer multiplication
• Strings
• Text search (brute force, Rabin-Karp, Knuth-Morris-Pratt, others)
• Edit distance
• Pattern matching by regular expressions, advanced regular expressions
• Categories of algorithms: divide and conquer, greedy, dynamic programming,
search
• Tractability: constant, logarithmic, linear, quadratic
• Decision problems: P, NP

Sumber: Finkel, Raphael, 2009. How to Teach Data Structures.

Exercise -lesson
• Form teams of no more than 6 students.
• Choose a data-structures topic.
• Discuss how to structure a lesson on that topic.

Subject matter

• Generally important ideas (“screwdrivers”) versus specialty topics
(“voltmeters”).
• Common themes that one finds throughout the study of data structures.
• pointers: cells in memory that refer to other cells
• recursion
• fencepost errors
• dummy value
• experimentation and invention
• What is a data structure? Howdoes it relate tomore general software
tools?
• How does one discuss efficiency of data structures?
• Linked lists (the first structure built with pointers)
• Queues, stacks, deques: built out of either linked lists or arrays
• Quick example of using an array for a queue
• Searching though numeric data: linked lists, unsorted array, sorted
array (binary search, interpolation search), binary tree
• Recursion theorem (without proof)
• Finding the jth largest element in a set (recursive partitioning)
• Sorting numeric data: insertion sort, selection sort, quicksort, bin
sort, radix sort
• short discussion: Never use bubble sort, although bumble sort
is far worse!
• Priority queues: heaps and heap sort
• Balanced binary trees: red-black trees, 2-3 trees, B treee
• Hashing, including the ”hash” data structure of Perl or PHP
• Quick example of hashing “we came we saw we conquered”
• Cryptographic hashing (digests)
• Quad trees, k-d trees
• Graphs

Sumber: Finkel, Raphael, 2009. How to Teach Data Structures.

Lesson: Binary trees
• Participants name integers
• Leader adds them to a growing sorted binary tree
• At some point, the integers are probes, not inserts median?
• Enumeration of operations
• insert
• search
• delete (seems hard)
• modify a node (seems as hard as delete followed by insert)
• enumerate all nodes
• find the smallest element (seems easy)
• find the middle element (seems hard)
• What is the cost of searching for a target? O(log n).

Sumber: Finkel, Raphael, 2009. How to Teach Data Structures.

Teaching styles
• Every instructor has a personal style of teaching.
• Every culture has its own style of instruction.
• The instructor cannot successfully deviate too far from the style
of the culture, but deviating a bit can focus the student's attention.

Sumber: Finkel, Raphael, 2009. How to Teach Data Structures.

Topics to cover
• What is the subject matter of a data structures course?
• What do students need to learn in a data structures course?
• How should a teacher present data structures material?
• What sort of assignments are appropriate for a data structures course?
• How should assignments be graded?
• What facilities are needed to support a data structures course?
• What textbooks are available, and howshould the teacher user them?
• How can the teacher evaluate the success of the course and improve
it for the future?