Abstract data structures

This is one of the most important ideas you can take with you:

Decompose a problem into smaller parts, model a problem with flowcharts. Learn to think sequentially

Computational thinking, problem-solving and programming

Computational Thinking (CT) is a process that generalizes a solution to open-ended problems. Open-ended problems encourage full, meaningful answers based on multiple variables, which require using decomposition, data representation, generalization, modeling, and algorithms found in Computational Thinking. Computational Thinking requires the decomposition of the entire decision making process, the variables involved, and all possible solutions, ensuring that the right decision is made based on the corresponding parameters and limitations of the problem. The term computational thinking was first used by Seymour Papert in 1980[1] and again in 1996.[2] Computational thinking can be used to algorithmically solve complicated problems of scale, and is often used to realize large improvements in efficiency

The big ideas in Abstract data structures

Thinking recursively

• Recursive thinking
• Recursive algorithms

Abstract data structures

• Two dimensional arrays
• Stack
• Queue

Linked lists

• Dynamic data structures
• Linked lists

Trees

• Trees

Standards

• Identify a situation that requires the use of recursive thinking.
• Identify recursive thinking in a specified problem solution.
• Trace a recursive algorithm to express a solution to a problem.

• Describe the characteristics of a two- dimensional array.
• Construct algorithms using two- dimensional arrays.
• Describe the characteristics and applications of a stack.

• Construct algorithms using the access methods of a stack.
• Describe the characteristics and applications of a queue.
• Construct algorithms using the access methods of a queue.
• Explain the use of arrays as static stacks and queues.
• Describe the features and characteristics of a dynamic data structure.
• Describe how linked lists operate logically.

• Sketch linked lists (single, double and circular).
• Describe how trees operate logically (both binary and non-binary).
• Define the terms: parent, left-child, right-child, subtree, root and leaf.
• State the result of inorder, postorder and preorder tree traversal.
• Sketch binary trees.
• Define the term dynamic data structure.
• Compare the use of static and dynamic data structures.
• Suggest a suitable structure for a given situation.

Separate into simpler constituents.

Separate into simpler constituents.

Provide an answer from a number of possibilities. Recognize and state briefly a distinguishing fact or feature.

Follow and record the action of an algorithm.

Give a detailed account or picture of a situation, event, pattern or process.

Develop information in a diagrammatic or logical form.

Give a detailed account including reasons or causes.

Represent by means of a diagram or graph (labelled as appropriate). The sketch should give a general idea of the required shape or relationship, and should include relevant features.

Give the precise meaning of a word, phrase, concept or physical quantity.

Give a specific name, value or other brief answer without explanation or calculation.

Give a specific name, value or other brief answer without explanation or calculation.

Propose a solution, hypothesis or other possible answer.