Part 1 | Abstract data types, Complexity, Java Collections; Stacks, queues and linked lists

• Objectives
• To read
• Exercises A
  • Exercise 1.1.1
  • Exercise 1.1.2
  • Exercise 1.1.3
  • Exercise 1.1.4 (INGInious: Implement a stack with two queues)
  • Exercise 1.1.5
  • Exercise 1.1.6
  • Exercise 1.1.7
  • Exercise 1.1.8
  • Exercise 1.1.9
  • Exercise 1.1.10 (INGInious: SegmentedList and iterators)
• Exercises B
  • Exercise 1.2.1 (INGInious: Circular Linked List)
  • Exercise 1.2.2 (INGInious: Implement a stack with an Array)
  • Exercise 1.2.3
  • Exercise 1.2.4 (INGInious: Functional Lists)
  • Exercise 1.2.5
  • Exercise 1.2.6
• Complexity
  • Notation Big-Oh (\(\mathcal{O}\))
  • Notation Big-Omega (\(\Omega\))
  • Notation Big-Theta (\(\Theta\))
  • Notation Tilde (\(\mathcal{\sim}\))
  • Best case, worst case, average case
  • Amortized Complexity
  • Frequent complexities