data_structures_feb_2016

Exercises and Homework for SoftUni's Data Structures February 2016 course, in Python.

Problems with an asterisk (*) are considered hard and optional.

Notable code

• **Trie Data Struccture
• ****Rope Data Structure
• ****Red-Black Tree RB Tests
• ****B-Tree sloppy implementation that needs refactoring B-Tree Tests
• **Left-Leaning Red-Black Tree
• **AA Tree AA Tree Tests
• **Balanced Ordered Set tests
• ***Calculate Arithmetic Expression - calculate arithmetic expressions using the Shunting Yard Algorithm
• KD-Tree - *Mass Effect Galaxy Map

Lessons

1.Data Structures, Algorithms and Complexity

Overview of the course, introduction to the Big-O notation and why algorithm speed matters.

Exercises

• Given slow and fast functions, compare their speed.

Homework

• Given functions, figure out their Big-O complexity.

2.Linear Data Structures – Lists

Linked List, how a List(Vector) works and how it differs from a traditional array.

Exercises

• Implement a Double-Linked List

Homework

• Get the sum and average of a list of integers
• Sort the words in a list
• Find the longest subsequence of equal numbers in an array
• Remove odd occurrences
• Count of occurrences
• Implement a ReversedList
• Implement a LinkedList
• *Distance in Labyrinth

3.Linear Data Structures – Stacks and Queues

Analysis of both data structures, their complexities and when to use which.

Exercises

• Implement a Circular Queue

Homework

• Reverse numbers with a stack

• Calculate sequence with a queue

• Implement an Array-Based Stack

  Array-Based Stack Tests

• Implement a Linked Stack

  Linked Stack Tests

• Implement a Linked Queue

  Linked Queue Tests

• *Sequence N-M

4.Trees and Tree-Like Structures

Introduction to Trees, Binary Trees, Balanced Binary Trees(AVL, AA, B, RB) and Graphs

Exercises

• Implement a tree. tests
• Implement a binary tree. tests

Homework

• Play with Trees, a program which can find
  • The root node
  • All leaf nodes (in increasing order)
  • All middle nodes (in increasing order)
  • The longest path in the tree (the leftmost if several paths have the same longest length)
  • All paths in the tree with given sum P of their nodes (from the leftmost to the rightmost)
  • All subtrees with given sum S of their nodes (from the leftmost to the rightmost)
• Traverse Directory - Build a tree from directories and calculate the sum of file sizes.
• ***Calculate Arithmetic Expression - calculate arithmetic expressions using the Shunting Yard Algorithm

5.Trees Traversal Algorithms

In-depth analysis of DFS and BFS

Exercises

• Find Connected Components tests
• Find Nearest Exit From Labyrinth tests

Homework

• Find the Root - Figure out if the given graph is a tree and find it's root
• Round Dance - Find the longest 'round dance'
• Ride The Horse - Traverse matrix in a way a horse chesspiece would
• Longest Path In Tree - Find the longest path in a tree from leaf to leaf by the sum of the nodes.
• *Sorting - Each step, take K elements in the array and reverse them. Find the minimum number of such steps to completely sort the array.

6.Dictionaries and Hash Tables

Dictionary implementations, how hash-tables work (collision strategies) and set implementations.

Exercises

• Implement a Hash Table with Chaining

Homework (Use the Hash Table you created from the exercises)

• Count Character Occurrences In Text
• Phonebook
• Implement an Ordered Set
• **Balanced Ordered Set tests

7.Collection Data Structures and Libraries

Ordered dictionaries, multi-dictionaries, ordered multi-dictionaries, sets, ordered sets, bags, ordered bags, rope.

Exercises

• Simple String Editor Program
• Events in given range

Homework

• Products in price range
• String Editor
• **Trie Data Struccture
• ****Rope Data Structure

8.Advanced Tree Structures/

Learned about AA, AVL and Red-Black trees. Ropes.

Exercises

• Implement a Binary Heap Tests
• Implement an AVL Tree Tests

9.Advanced Tree Structures/

Learned about B-Trees, Heaps, Tries, Suffix Trees and Space-Partitioning Trees (Quad Tree, K-d Tree, etc.)

Exercises

• Implement a Quad Tree

Homework

• Sweep and Prune algorithm
• KD-Tree - *Mass Effect Galaxy Map