### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Algorithms and Data Structures CS 200

CSU

GPA 3.51

### View Full Document

## 53

## 0

## Popular in Course

## Popular in ComputerScienence

This 6 page Class Notes was uploaded by Betty Kertzmann on Tuesday September 22, 2015. The Class Notes belongs to CS 200 at Colorado State University taught by Sangmi Pallickara in Fall. Since its upload, it has received 53 views. For similar materials see /class/210187/cs-200-colorado-state-university in ComputerScienence at Colorado State University.

## Popular in ComputerScienence

## Reviews for Algorithms and Data Structures

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/22/15

CS 200 Exam 1 Preparation Guide Exam Date Thursday September 29 2011 Location amp Time Inclass 930 1045 AM In this exam you will have a mix of multiplechoice questions some short answer questions and sometquestionsthat require you to read Java code and perform algebraic calculation You should attempt the examples and Exercises at the end of indicated textbook sectionis chapters Many of the exam q39U39e39Sti39on sWil have a similar form AIS39O review the written ass ignmentsa n uizizes Key concepts The problems in this exam will be about the concepts covered in the lectures week 1 through week 5 Please review your lecture notes httpwwwcscolostateeducs200Fa1111Schedulehtml The following textbook exercises and examples can help you prepare for the exam Recursion Mathematical Induction and Grammar Lecture Notes part 1 Textbook Chapter 6 from Prichard Section 41 from Rosen 51 in 7th Edition Exercise After chapter 6 in Prichard and after section 4151 in 7th ed in Rosen can help you understand mathematical induction You can start with exercises 3 4 5 7 11 15 after section 4151 in 7th ed in Rosen 1 What is the Backtracking 2 How are languages defined recursively 3 Mathematical Induction 4 How is the correctness ofyour software shown with mathematical induction 5 How is the cost of an algorithm proved with mathematical induction Advanced Object Oriented Programming Concepts Lecture Notes part 2 1 What is an object 2 What is data encapsulation 3 What is inheritance 4 What is information hiding and why is it useful 5 What are interfaces and abstract classes and how are they different 6 What is polymorphism Stacks and Queues Lecture Notes part 3 and part 4 Text book Chapter 7 8 from Prichard 1 What is a stack What is a queue How do they differ from a list 2 What are the operations that are typically associated with a stackqueue 3 How can you implement a stackqueue using arraysreferenceslinked lists Computational Complexity Lecture Notes part 5 1 2 3 Textbook Sections 32 33 71 73 from Rosen in 6th Edition section 71 and 73 are sections 81 and 83 in 7th Edition Chapter 10 from Prichard Examples and exercises will help you to understand concepts You can start with exercises 127910111213 from 7383 in 7th ed in Rosen 1 Factors of complexity analysis 2 Growth of functions definitions and understanding of BigO Bigtheta and Big omega notations 3 Sorting algorithms and their time complexities 4 Know how to obtain a closed form from a recurrence relation using substitution and find its Big O complexity 5 Know how to obtain a recursive definition from the source code and find its Big O complexity 6 Know the purpose and form of the Master Theorem and how to use it to obtain BigO complexity 7 Know how to apply the Master Theorem to a divideandconquer style algorithm to find the big 0 complexity CS 200 Midterm ExamZ Preparation Guide Exam Date Thursday October 27 2011 Location amp Time Inclass 930 1045 AM In this 39exam39 you will have a mix of multiplechoice questions some short answer questions and somequestionsthatrequire you to read Java code and perform algebraic calculations You should attempt the examples and Exercises at the end of indicated textbook sectionis chapters Many of the exam q ue sti on sWill have a similar form AISO review the inclass quizzes Key concepts The problems in this exam will be about the concepts covered in the lectures week 1 through week 5 Please review your lecture notes httpwwwcscolostateeducs200FallllSchedulehtml The following textbook exercises and examples can help you prepare for the exam Binary Tree Binary Search Tree Lecture Notes part 61 Textbook Chapter 11 Trees from Prichard What are the Binary Tree and Binary Search Tree Search and Traversal algorithms Insertion and Deletion algorithms Implementation of BSTs Efficiency of Binary Search Tree Know how to sort a list using a BST treesort Know how to prove the properties of EST and binary tree with mathematical induction 8 What is the complexity of treesort 9 Algorithms for storingrestoring BST 10 Understand psuedocode for BST operations NQ F39HFSNN Balanced Trees 23 tree 234 tree Redblack tree and AVL tree Lecture Notes part 62 Textbook Chapter 13 Section 1 Balanced Search Trees From Prichard What are 23234 Redblack and AVL trees SearchTraversalInsertingDeleting algorithm for 23 tree SearchTraversalInsertingDeleting algorithm for 234 tree Know how to convert a 234 tree to a Redblack tree Know how to convert a RedBlack tree to a 234 tree EanSNNEquot 6 What is the advantage ofusing 23 trees when compared with the BST 7 What is the advantage ofusing 234 trees when compared with the 23 trees 8 What is the advantage of using Redblack tree when compared with the 234 trees 9 How do AVL trees keep the balance External Methods Btree Lecture Notes part 63 Text book Chapter 151 3pp845856 from Prichard 1 What is the advantage of an external storage to maintain a data structure 2 What is the Btree 3 Know how to use Btree to organize data blocks 4 DeletingInsertingTraversals algorithms CS 200 Final Exam Preparation Guide Exam Date Monday December 12 2011 Location amp Time Clark A202 620 820 PM Key concepts The problems in this exam will be about the concepts covered in the lectures week 1 through week 16 Please review your lecture notes httpwwwcscolostateeducsZOOFallllSchedulehtml For material covered from week 19 please refer to the exam guides that were provided for Midterms 1 and 2 From the lectures ofweek 10 week 16 Heaps and Heapsort Lecture Notes part 7 Heaps and Heapsort Text Chapter 12 Prichard 1 What is a heap 2 How to insert and delete items 3 Array representations of heap 4 What is the difference between heap and binary tree 5 Heapsort algorithm and efficiency Hashing Lecture Notes part 8 Hashing Text section 132 Prichard 1 Why do we need hashing 2 What are linear and the quadratic probing 3 What is chaining Relations Lecture Notes part 9 Relations Text section 81 83 6th Ed Rosen Revisit the problems in the written assignment 3 Binary relations 2 Re exive relations Transitive relations and Symmetric antisymmetric relations 3 Combining relations The powers ofa relation R Representation of the relations yup Graphs Lecture Notes part 10 Graphs Text Chapter 14Prichard Section 91 96 6th Ed Rosen Solve the problems in the worksheet 1 Know the terminologies ofa graph such as vertex edge degree directed graph undirected graph loop subgraph path and cycle The handshaking theorem Graph representation Graph implementation Graph traversal algorithms Know both DFS and BFS algorithms Connectedness of graphs What is a strongly connected graph What is a weakly connected graph 7 What is a planar graph Topological sorting algorithms 9 Know the Minimum spanning tree algorithm 10 Know the Shortest path algorithm 11 What is an Euler path and circuits Know how to find them 12 What is an Hamiltonian circuit Know how to find them 99145390 X

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.