Lesson Objectives Aims Understand algorithms for the following

Lesson Objectives Aims Understand algorithms for the following

Lesson Objectives Aims Understand algorithms for the following data structures: 1. Stack 2. Queue 3. Tree Depth first traversal Breadth first traversal 4. Linked List

This lesson Tough though it sounds, you are going to need to learn the code for a lot of algorithms Youre going to need to be able to write and recognise that code. It WILL be in your exam wait until we look at the past papers for proof of that. If you dont do the tasks in this lesson you will find this incredibly difficult and

Notes CS is about NOT re-inventing the wheel. There is a folder in shared called Princeton University Notes These are EXCELLENT resources they contain diagrams, explanations, examples and CODE (in Java, suck it up) which are INVALUABLE to you. Were there enough caps there for emphasis??

Stacks A stack is a FILO data structure Imagine a pile of plates which one can you get next (realistically?) Stacks support two main operations Push put something on the top of the stack Pop get the first item from the top of the stack

Stacks Stacks are incredibly useful when we want to remember the order we did something in or return to a previous state: CPU states (interrupts) Undo (in a program) Reversal of a list of items Task Implement a Stack class in VB which makes a stack

of strings. It must have the following methods: Push Pop GetStackSize (returns the number of elements in the stack) IsFull (returns true or false) IsEmpty (returns true or false) The constructor should set the maximum size of the stack. Print your code and an example of it working and

add it to your notes. Queue A queue is a FIFO data structure New data is added to the end or tail of the queue Data is removed from the front or head of the queue As with stacks, we use a pointer to keep track of where the head and tail of the queue are.

Queue Like a stack, queues are of finite size (usually) and therefore must be checked for their empty/full states when adding or removing data. Task Implement a Queue class in VB which accepts a queue of Integers. It must have the following methods:

Enqueue Dequeue IsFull (returns true or false) IsEmpty (returns true or false) The constructor should set the maximum size of

the queue. If you use arrays, think about how you will use the empty elements MOD? Print your code and an example of it working and add it to your notes. Linked List A linked list is formed from Nodes. A node contains: The data A pointer to the next node

In reality, when you code it, the node may also contain an ID of some sort (if your language doesnt support pointers, how else are you going to link the list?!) Linked lists Linked lists Dynamic Bound by the size of the memory or allocation for nodes Can remove a node by simply

changing the pointer Could be expanded by: Creating links for different purposes Double linked lists?? Task Code a linked list of strings in VB VB does not have pointers! So You will need to create a STRUCTURE which contains the data and a pointer. Id also suggest it contains an ID? Or you could use the index of

an array to be the pointers? Your class should contain: Add node Remove node Fetch nodes (show the list) Tree A tree is a data structure made up of Nodes A node is simply a point in the tree which

holds: Some data A pointer to the left node A pointer to the right node A pointer may be: Another node Null (it doesnt exist) What does it look like?

Terminology (all are nodes (the same thing)): ROOT The top node in the tree. All trees have one (and only one) root node. LEAF A single node which isnt the root, but has no children. PARENT A node which isnt the root, but does have one or more children CHILD A node connected to a parent node.

Tree Vs Binary Tree Most tree data structures are implemented as Binary Trees These are identical, except for one important feature Each node may have a maximum of 2 children a left and a right node. Task I am not going to ask you to implement a tree

BUT, I am going to ask you to type in (not download and run) the code linked on the next slide You STILL need to understand the code It is also an excellent introduction to recursion and makes a lot of sense. Trees A really good resource https:// www.codeproject.com/articles/4647/asimple-binary-tree-implementation-wit

h-vb-net Traversal Trees are often used because they: Automatically sort data Make sense for AI: Decisions Following trains of thought Potential moves in a game etc. They can be traversed (searched) in multiple

ways. Find out about Depth first and breadth first (fairly obvious) and add to your notes. You will have already covered one if you tried the code and tested it. Review/Success Criteria You should know: The main data structures in computer science How to recognise a data structure from its code How to code each data structure in VB and, by default, pseudo code

Recently Viewed Presentations

  • Staff Meeting Mayhem - NACADA

    Staff Meeting Mayhem - NACADA

    Staff Meeting Mayhem - a meeting attended by members of staff, to which they look forward on a weekly basis. Not the legal definition of mayhem - which is the crime of maliciously injuring or maiming someone, originally so as...
  • MATH THE BUTLER WAY A Unique Modular Approa

    MATH THE BUTLER WAY A Unique Modular Approa

    MA050 Persistence to College Algebra . As the number of courses between college algebra and the students starting course decreases, the percentage of students who persist to college algebra increases ( which makes sense, the shorter the pipeline the more...
  • White Collar Crime UWF Employee Symposium Betsy Bowers,

    White Collar Crime UWF Employee Symposium Betsy Bowers,

    Overview. Fraud Triangle. Cash . Handling. Red Flags of Fraud. PCard Responsibilities. Special Thanks to the Association of College & University Auditors [ACUA] member institutions for aspects of this presentation.
  • Using Quotations - WordPress.com

    Using Quotations - WordPress.com

    Using Quotations. A guide to improving quote use in essays. ... If you use lineated text (poetry or some plays), you need to maintain the lineation. ... but the block quote is set off with indentations and follows the lineation...
  • What is Ctrip? Ctrip is Chinas Largest Travel

    What is Ctrip? Ctrip is Chinas Largest Travel

    - Fan and his team developed the EBooking network, which electronically connected bookable hotels to Ctrip via the Internet and enabled them to exchange booking information. This EBooking system now acts as the company's hotel global distribution system (GDS) in...
  • BIOLOGY EOC 10-DAY REVIEW Written by Chris Jackson,

    BIOLOGY EOC 10-DAY REVIEW Written by Chris Jackson,

    Mendelian Genetics © Hedgehog Learning. Genetics is the study of the odds and percentages any given offspring will have a set of traits. Three Laws of Mendelian ...
  • Porter's Five Force's Model - Winthrop

    Porter's Five Force's Model - Winthrop

    Apple, Inc. Formulation Presentation March, 7 2008 Mathew Lugo, Brooks Johnston, Jessica-Anne Stoudemire, Kerri Barringer, & Ben Ponds Possible Objective Shifts Worst Case Scenario Competitive position Best Case Scenario Productivity Public responsibility Corporate Level Business Alternatives Presented by: Brooks Johnston...
  • Proteinuria a háziorvos szemével - NEPHROLOGIA

    Proteinuria a háziorvos szemével - NEPHROLOGIA

    44 off legs and polyuric. colif urine, e coli bcu. hypercalcaemia o/a diarrhoea myeloma diagnosed, decision for conservative treatment or rf, perindopril stopped on admission, required incr care package. CRF cr 368 ckd V cr eGFR 11. u4536397. sayani. aziz.