This class was created by Brainscape user michal wozniak. Visit their profile to learn more about the creator.
By:
michal wozniak
- decks
- flashcards
- learners
Decks in this class (43)
Lecture 1 - Time Complexity Revision
What is time complexity,
Why do we use the worst case of a...,
What is asymptotic behaviour
16
cards
Lecture 1 - ADTs
What methodology does a stack follow,
What are the basic operations of ...,
How can a stack be implemented
15
cards
Lecture 1 - Comparison Sorts
What comparison sorts have averga...,
What comparison sorts have,
What is the fastest comparison ba...
13
cards
Lecture 1 - Radix Sort
What do we have to do to do bette...,
What does radix sort do,
What is a disadvantage of radix c...
11
cards
Lecture 1 - Tries
Are binary search trees compariso...,
What are tries,
What are tries especially useful for
5
cards
Lecture 2 - Graph Basics
What is an undirected graph,
What does it mean if vertices are...,
What does it mean if a vertex is ...
16
cards
Lecture 2 - Graph Representations
How can graphs be represented,
What is a adjacency matrix,
What is an adjacency list
5
cards
Lecture 2 - BFS and DFS
What is dfs bfs categorised as,
How do we know if bfs dfs is effi...,
What are the steps of depth first...
11
cards
Lecture 2 - Weighted Graphs
What is a weighted graph,
What does a adjacency matrix turn...,
What will an adjacency list inclu...
3
cards
Lecture 2 - Dijkstra's
What does dijkstra s algorithm do,
Applications of dijkstra s
2
cards
Lecture 3 - Graph Recap
What is an undirected graph,
What is a directed graph,
Another name for a directed graph
6
cards
Lecture 3 - Spanning Trees
What is a spanning tree,
How is a spanning tree obtained,
What is the weight of a spanning ...
7
cards
Lecture 3 - Prim-Jarnik Algorithm
What kind of an algorithm is the ...,
What is the complexity of this al...,
What is a tv
5
cards
Lecture 3 - Dijkstra's Refinement
What needs to be added to dijkstr...,
What is the complexity of this al...,
Will proof of correctness be part...
3
cards
Lecture 3 - Topological Ordering
What is a dag,
Where is topological ordering used,
When does a graph have a topologi...
15
cards
Lecture 4 - Text Compression Intro
What is text compression,
What kind of a compression must t...,
What does lossless mean
8
cards
Lecture 4 - Huffman Encoding
What kind of a text compression m...,
What is each character replaced by,
What are characters represented by
21
cards
Lecture 4 - LZW Compression
What based method is this,
What is a dinctionary,
What is written to the compressed...
11
cards
Lecture 4 - String Difference
Applications of string distance,
What is string distance,
What are the 3 basic operations i...
23
cards
Lecture 5 - String/Pattern Search Intro
Applications of searching text fo...,
Variants of string pattern searching,
What are the typical sizes of n a...
3
cards
Lecture 5 - Brute Force Algorithm
What is another name for the brut...,
Steps of the naive brute force al...,
What is the complexity of the bru...
4
cards
Lecture 5 - KMP
What does kmp stand for,
What kind of an algorithm is kmp ...,
What is a border table
20
cards
Lecture 5 - BM
What does bm stand for,
How does bm perform compared to k...,
Are all characters in the text ch...
20
cards
Lecture 6 - NP Intro
What is an eulerian cycle,
When does a graph have a eulerian...,
What is the complexity of euleria...
16
cards
Lecture 6 - NP-Completeness
If one np complete problem s solv...,
If one of np complete problems is...,
What is the current belief about ...
11
cards
Lecture 6 - Hamiltonian Cycle
Is hamiltonian cycle np compllete,
What is a problem instance,
What is a problem
6
cards
Lecture 6 - Travelling Salesman Problem
What is the travelling salesman p...,
What is the distance path called,
Is this problem np complete
3
cards
Lecture 6 - Clique Problem
Abbreviation,
What is an instance of a clique p...,
What is the question of the cliqu...
5
cards
Lecture 6 - Graph Colouring Problem
Abbreviation,
What is an instance of gcp,
What is the question of gcp
4
cards
Lecture 6 - Satisfiability Problem
What is the abbreviation,
What is the instance of this problem,
What is the question
3
cards
Lecture 6 - Classes P and NP
What does the class p contain,
What does the class np contain,
What is a non determinisitc algor...
13
cards
Lecture 6 - Polynomial Time Reductions
What is a polynomial time reduction,
What is the way to write ptrs,
What is the transitivity property...
6
cards
Lecture 6 - What is NP-Complete? Formally?
When is a decision problem np com...,
Consequences of the definition,
How do we prove a problem is np c...
11
cards
Lecture 7 - Computability Intro
What is the model of a computer,
What is that something black box,
What is computability concerned with
13
cards
Lecture 7 - Halting Problem
The halting problem is,
What is the erratic program,
What does it mean for an algorith...
7
cards
Lecture 7 - Models Of Computation
What do models of computation att...,
What are the 3 models we will loo...,
Characteristics of fa
5
cards
Lecture 7 - DFA
What does a deterministic finite ...,
Why do we look at a determinisic fa,
How are accepting states denoted
28
cards
Lecture 8 - Intro
What can a dfa not recognise,
Why cannot dfa recognise this,
How to recognise a nb n
5
cards
Lecture 8 - Pushdown Automata
What does a pushdown automata con...,
What does q1 a w q2 v mean,
When does pda accept an input
13
cards
Lecture 8 - Turing Machines
What does a turing machine consis...,
What does the transition relation...,
What happens if we don t want to ...
18
cards
Lecture 8 - Turing Machines P and NP
Alternative way to think of p,
Alternative way to think of np
2
cards
Lecture 8 - Counter Programs
Fact about general purpose progra...,
What do counter programs have,
What unlabelled statements can we...
3
cards
Lecture 8 - Church-Turing Thesis
Is the tm an appropriate model fo...,
Is everything effectively computa...,
Is church turing a theorem
5
cards
More about
UOFG_Algorithmics_1
- Class purpose General learning
Learn faster with Brainscape on your web, iPhone, or Android device. Study michal wozniak's UOFG_Algorithmics_1 flashcards now!
How studying works.
Brainscape's adaptive web mobile flashcards system will drill you on your weaknesses, using a pattern guaranteed to help you learn more in less time.
Add your own flashcards.
Either request "Edit" access from the author, or make a copy of the class to edit as your own. And you can always create a totally new class of your own too!
What's Brainscape anyway?
Brainscape is a digital flashcards platform where you can find, create, share, and study any subject on the planet.
We use an adaptive study algorithm that is proven to help you learn faster and remember longer....
