rish-16

CS2040S Week 9 Lecture 2

Notes from Week 9 Lecture 2 on Graphs

BFS

Properties of parent edges

• They form a tree (shortest path tree)
  • There are no cycles – all nodes visited only once
• Parent edges are always shortest paths from starting node s
• For now, all edges have weight/distance 1

rish-16

CS2040S Week 9 Lecture 1

Notes from Week 9 Lecture 1 on Graphs

What are Graphs?

• Consists of at least one nodes/vertices and edges/arcs
• Each edge connects two nodes and are unique
• Types of other graphs (not tested)
  • Multigraph – many edges between two nodes
  • Hypergraph – edges connects >= 2 nodes

rish-16

CS2040S Week 7 Lecture 1

Notes on Hashing (contd.)

Midterm

• Asymptotic analysis
• Recurrences
• Probability
• Abstract Data Types
• Divide-and-Conquer Algorithms
• Sorting

rish-16

CS2040S Week 5 Lecture 1

Notes from CS2040S Week 5 Lecture 1 on Trees

Deletion in Trees

Three cases:

• No children – simply remove target node
• 1 child – remove target node and connect child of target node to parent of target node
• 2 children – find successor, delete the successor, remove the target node, connect successor to left/right/parent of target node

Doing this ensures that the BST property holds even after deletion. Worst-case time complexity of deletion is O(n).

rish-16

Essay Writing

1. Effective Thesis
2. Parenthetical Citation
3. Essay Structure
4. Editing Tips
5. Peer Editing

Effective Thesis

• Tells a reader how you will interpret the significance of the subject matter under discussion. Such a statement is a debatable, overarching claim organising an essay

rish-16

CS2040S Week 4 Lecture 2

Notes from CS2040S Week 4 Lecture 2 on Trees

Dictionary

A collection of (key, value) pairs

interface	IDictionary

void		insert
Value search

rish-16

CS2040S Week 4 Lecture 1

Notes from CS2040S Week 4 Lecture 1 on Quick Sort

Quick Sort

if n = 1 return
else:
	p = partition(A[1...n], n)
	x = quicksort(A[1...p-1], p-1)
	y = quicksort(A[p+1, n], n-p)

rish-16

CS2040S Week 3 Tutorial

Notes from CS2040S Week 3 Tutorial

Asymptiotic Analysis

• Big Theta
  • t(n) = Theta(g(n))
  • k1 * g(n) <= t(n) <= k2 * g(n)
• Big O (how bad it can be)
  • t(n) = O(g(n))
  • t(n) <= k * g(n)

rish-16

CS2040S Week 3 Lecture 2

Notes from CS2040S Week 3 Lecture 2 on Quick Sort

Merge Sort

Bottom Up

Start with whole array. In the first pass, merge the pairs. Repeat.

15 7 9 2 6 12 13 4
7 15 2 9 12 6 4 13
2 7 9 15 4 6 12 13

rish-16

CS2040S Week 3 Lecture 1

Notes from Week 3 Lecture 1 on Sorting

Sorting Algorithms

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Bogo Sort (non-examinable with run time of O(n . n!))